Past exam question: 2065 Shrawan (Regular / Back), Q5(b)
Open in the Padhaiko appQuestion
Create AVL tree using following data sets. 14, 12, 20, 18, 23, 4, 44, 64, 66 Show all the steps including rotation where ever needed clearly.
Solution
Insert 14, 12, 20, 18, 23, 4, 44:
- Insert
14(root),12(left of14),20(right of14): . - Insert
18(left of20),23(right of20),4(left of12),44(right of23):- Check balance factors: , , , . All (no rotation yet).
Insert 64 (RR Rotation at 23) and 66 (RR Rotation at 20):
- Insert
64: right child of44.- RR (Single Left) Rotation at
23:44replaces23with left child23and right child64.
- RR (Single Left) Rotation at
- Insert
66: right child of64.- .
- Node
20has and right child44has RR (Single Left) Rotation at20:44becomes right child of14,20becomes left child of44, and23moves as right child of20.
14 (-1)
/ \
12 (+1) 44 (0)
/ / \
4 (0) 20 (0) 64 (-1)
/ \ \
18 (0) 23 (0) 66 (0)Answer:
Final AVL tree has root 14, left subtree 12 (left 4), and right subtree 44 (left 20 with children 18, 23; right 64 with right 66).