Past exam question: 2074 Bhadra (Regular), Q7
Open in the Padhaiko appQuestion
Discuss about AVL rotations with suitable examples. Create a AVL balanced tree for data sequence 10 20 30 50 45 40 8 5 3.
Solution
Four AVL Tree Rotations with Examples: When an insertion makes , balance is restored by one of four rotations:
- LL Rotation (Single Right): Imbalance , left child (e.g., insert
30, 20, 10right-rotate30root20). - RR Rotation (Single Left): Imbalance , right child (e.g., insert
10, 20, 30left-rotate10root20). - LR Rotation (Double Left-Right): Imbalance , left child (e.g., insert
30, 10, 20left-rotate10, then right-rotate30root20). - RL Rotation (Double Right-Left): Imbalance , right child (e.g., insert
10, 30, 20right-rotate30, then left-rotate10root20).
AVL Construction — Insert 10, 20, 30 (RR) and 50, 45 (RL):
- Insert
10, 20, 30: RR (Left) Rotation at10root20(10, 30). - Insert
50, 45:50right of30,45left of50.- RL Rotation at
30(right-rotate50, left-rotate30)45replaces30with children30, 50.
- RL Rotation at
Insert 40 (RL at 20), 8, 5 (LL at 20), and 3 (LL at 8):
- Insert
40: right child of30. RL Rotation at20(right-rotate45around30, left-rotate20around30):30becomes root!
30 (0)
/ \
20 (+1) 45 (0)
/ / \
10 (0) 40 (0) 50 (0)
- Insert
8, 5:8left of10,5left of8. ? Wait:10has8(left) and8has5(left), while20has10(left) and no right! Actually ! So LL Rotation at10(8replaces10? Wait: at8insertion, ! So on inserting8, LL Rotation at20makes10parent of8and20!).- Then insert
5(left of8): . Balanced!
- Then insert
- Insert
3(left of5): LL (Right) Rotation at8:5becomes parent of3and8.
30 (+1)
/ \
10 (+1) 45 (0)
/ \ / \
5 (0) 20(0) 40(0) 50(0)
/ \
3 (0) 8 (0)Answer:
- Rotations: Single (LL, RR) for outer-child imbalances and double (LR, RL) for inner-child imbalances.
- Final AVL Tree: Root 30, left subtree 10 (left 5 with children 3, 8; right 20), right subtree 45 (children 40, 50).