- 2074 Bhadra · 6 marks
AVL rotations with examples
Short answer
When an AVL node's balance factor becomes ±2, rotations restore balance: LL case requires a right rotation; RR requires a left rotation; LR uses left rotation on left child then right rotation; RL uses right rotation on right child then left rotation. Example: inserting 30,20,10 creates LL imbalance fixed by right rotation at 30.
Discuss about AVL rotations with suitable examples.
An AVL tree is a height-balanced BST where, for every node, the heights of the left and right subtrees differ by at most 1. When an insertion or deletion breaks this (balance factor becomes +2 or −2), the tree is repaired by rotations. There are four cases, in two groups.
1. Single rotations
LL case → right rotation. New node goes into the left subtree of the left child.
Insert 30, 20, 10: 30 (bf +2) 20
/ / \
20 ==> 10 30
/
10
The left child 20 becomes the root, 30 becomes its right child (20's old right subtree, if any, becomes 30's left subtree).
RR case → left rotation. New node goes into the right subtree of the right child.
Insert 10, 20, 30: 10 (bf -2) 20
\ / \
20 ==> 10 30
\
30
2. Double rotations
LR case → left rotation on the left child, then right rotation on the root.
Insert 30, 10, 20: 30 30 20
/ / / \
10 ==> 20 ==> 10 30
\ /
20 10
(left at 10) (right at 30)
RL case → right rotation on the right child, then left rotation on the root.
Insert 10, 30, 20: 10 10 20
\ \ / \
30 ==> 20 ==> 10 30
/ \
20 30
(right at 30) (left at 10)
Summary
| Case | Imbalance | Rotation |
|---|---|---|
| LL | bf = +2, left child bf ≥ 0 | right |
| RR | bf = −2, right child bf ≤ 0 | left |
| LR | bf = +2, left child bf = −1 | left, then right |
| RL | bf = −2, right child bf = +1 | right, then left |
Each rotation takes O(1) time and keeps the in-order sequence unchanged, so the tree is still a valid BST.
✓ Answer checked by Claude Opus 5.5 (high effort)