Past exam question: 2079 Ashwin (Back), Q6
Open in the Padhaiko appQuestion
Create an AVL balanced tree for following sequence of elements:
Solution
AVL Tree Definition and Balance Factor: An AVL tree is a self-balancing binary search tree where the Balance Factor (BF) of every node is defined as:
When an insertion causes , balance is restored using one of four rotations:
- LL Rotation (Single Right): when inserted into the left subtree of the left child.
- RR Rotation (Single Left): when inserted into the right subtree of the right child.
- LR Rotation (Left-Right Double): left rotate left child, then right rotate unbalanced node.
- RL Rotation (Right-Left Double): right rotate right child, then left rotate unbalanced node.
Step-by-Step Insertions of 5, 18, 35, 65, 25:
- Insert 5: Tree is
(5). Balanced (). - Insert 18:
(5)with right child(18). . Balanced. - Insert 35: Inserted as right child of
18. (RR unbalance at node 5).- Perform RR (Single Left) rotation on node 5:
18 (0) / \ 5 (0) 35 (0)
- Perform RR (Single Left) rotation on node 5:
- Insert 65: Inserted as right child of
35. . Balanced. - Insert 25: Inserted as left child of
35. . Balanced.18 / \ 5 35 / \ 25 65
Insertions of 15 and 10:
- Insert 15: Inserted as right child of
5. . Balanced. - Insert 10: Inserted as left child of
15.- Balance factors: , .
- Node 5 is right-heavy (), and its right child 15 is left-heavy ().
- This requires an RL rotation at node 5:
- Right rotate on 15: 10 becomes parent of 15.
- Left rotate on 5: 10 becomes parent of 5. All nodes currently have .
18 / \ 10 35 / \ / \ 5 15 25 65
Insertions of 12 and 14:
- Insert 12: Inserted as left child of
15. . Balanced. - Insert 14: Inserted as right child of
12.- Balance factors: , .
- Node 15 has with left child 12 having LR rotation at node 15:
- Left rotate on 12: 14 becomes parent of 12.
- Right rotate on 15: 14 becomes parent of 15. Subtree at 10 becomes: Entire tree is balanced (, ).
10 / \ 5 14 / \ 12 15
Insertions of 3 and 2:
- Insert 3: Inserted as left child of
5. . Balanced. - Insert 2: Inserted as left child of
3.- Balance factors: , .
- Node 5 has and left child 3 has LL (Single Right) rotation at node 5:
- Right rotate on 5: 3 becomes the parent of 2 (left) and 5 (right).
- Subtree at 10 becomes:
10 / \ 3 14 / \ / \ 2 5 12 15
Final Balanced AVL Tree Architecture: The final balanced tree containing all 11 keys:
18 (BF = +1)
/ \
10 (BF = 0) 35 (BF = 0)
/ \ / \
3 (0) 14 (0) 25 (0) 65 (0)
/ \ / \
2 (0) 5 (0) 12 (0) 15 (0)
Verification: In-order traversal yields the strictly sorted sequence:
Every node's balance factor is strictly within .
Answer:
The resulting AVL balanced tree has root 18:
- Left subtree of 18: Rooted at 10, with left child 3 (children: left 2, right 5) and right child 14 (children: left 12, right 15).
- Right subtree of 18: Rooted at 35, with left child 25 and right child 65.
Total height is 4, and every node satisfies .