PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q5

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Balanced binary tree · Introduction to red-black tree · B-Tree: Need…

Question

Define AVL balance tree and create AVL tree using AVL balancing algorithm for given sequence of data 3, 15, 21, 2, 7, 5, 13, 10, 8, 4, 19, 24, 1. Show inorder traversal of tree after each rotation clearly.

Solution

Definition of AVL Tree: An AVL tree is a self-balancing Binary Search Tree in which every node's balance factor lies in , maintained via LL, RR, LR, and RL rotations.

Insert 3, 15, 21 (RR Rotation at 3) and 2, 7, 5 (LR Rotation at 15):

Insert 13, 10, 8 (LL Rotation at 13) and 4, 19, 24, 1:

                      7 (0)
                  /            \
              3 (0)            15 (0)
             /     \          /      \
          2 (+1)   5 (+1)  10 (0)    21 (0)
          /        /       /    \    /    \
        1 (0)    4 (0)   8 (0) 13(0) 19(0) 24(0)
Answer:

Final AVL tree has root 7, left subtree 3 (2->1, 5->4), and right subtree 15 (10->{8, 13}, 21->{19, 24}). Final inorder traversal: 1, 2, 3, 4, 5, 7, 8, 10, 13, 15, 19, 21, 24.

All past exam questions for Data Structure and Algorithms