Past exam question: 2077 Chaitra (Regular), Q10(b)
Open in the Padhaiko appQuestion
Construct an AVL tree from following sequence of data: 10, 20, 15, 25, 30, 16, 18, 19.
Solution
Insert 10, 20, 15 (RL Rotation at 10):
- Insert
10, then20(right of10), then15(left of20). - , RL Rotation (right-rotate
20, left-rotate10):
15 (0)
/ \
10 (0) 20 (0)Insert 25, 30 (RR Rotation at 20):
- Insert
25(right of20), then30(right of25). - RR (Left) Rotation at
20:
15 (-1)
/ \
10 (0) 25 (0)
/ \
20 (0) 30 (0)Insert 16 (RL Rotation at 15), 18, and 19 (RR Rotation at 16):
- Insert
16: left child of20. .- RL Rotation at
15(right-rotate25around20, then left-rotate15around20):20becomes root!
- RL Rotation at
20 (0)
/ \
15 (0) 25 (-1)
/ \ \
10 (0) 16 (0) 30 (0)
- Insert
18: right child of16. . Balanced. - Insert
19: right child of18.- RR (Left) Rotation at
16:18becomes right child of15with children16and19.
- RR (Left) Rotation at
20 (+1)
/ \
15 (-1) 25 (-1)
/ \ \
10 (0) 18 (0) 30 (0)
/ \
16 (0) 19 (0)Answer:
The final AVL tree has root 20, left subtree 15 (left 10; right 18 with children 16, 19), and right subtree 25 (right 30).