Past exam question: 2078 Chaitra (Regular), Q6(b)
Open in the Padhaiko appQuestion
Construct an AVL balanced tree with given set of data: 15, 20, 24, 10, 13, 7, 30, 36, 25
Solution
Insert 15, 20, 24 (RR Rotation at 15): Balance factor is .
- Insert
15: root(15). - Insert
20: right child of15. . - Insert
24: right child of20. , RR (Single Left) rotation at15.
20 (0)
/ \
15 (0) 24 (0)Insert 10 and 13 (LR Rotation at 15):
- Insert
10: left child of15. , . Balanced. - Insert
13: right child of10.- , .
- Node
15has and left child10has LR rotation (left-rotate10, then right-rotate15):
20 (+1)
/ \
13 (0) 24 (0)
/ \
10 (0) 15 (0)Insert 7 (LL Rotation at 20):
- Insert
7: left child of10.- , , .
- Node
20has and left child13has LL (Single Right) rotation at20:13becomes the new root,20becomes right child of13, and15transfers as left child of20.
13 (0)
/ \
10 (+1) 20 (0)
/ / \
7 (0) 15 (0) 24 (0)Insert 30, 36 (RR Rotation at 24) and 25 (RL Rotation at 20):
- Insert
30: right child of24. . Balanced. - Insert
36: right child of30.- , RR (Single Left) rotation at
24(30becomes parent of24and36).
- , RR (Single Left) rotation at
- Insert
25: right child of24.- Now , , .
- Node
20has and right child30has RL rotation at20:- Right-rotate
30:24moves up,25attaches as left child of30. - Left-rotate
20:24becomes right child of13, with left child20(left15) and right child30(children25,36).
- Right-rotate
13 (-1)
/ \
10 (+1) 24 (0)
/ / \
7 (0) 20 (+1) 30 (0)
/ / \
15 (0) 25 (0) 36 (0)Answer:
The final balanced AVL tree has root 13, left subtree 10 (left child 7), and right subtree 24 (left child 20 with left child 15; right child 30 with children 25 and 36). In-order traversal: 7, 10, 13, 15, 20, 24, 25, 30, 36.