AVL Tree Rotations — Single and Double Rotations Explained
Learn how AVL trees maintain balance through four types of rotations: left rotation, right rotation, left-right rotation, and right-left rotation with visual diagrams.
Detailed Explanation
AVL Tree Rotations
AVL trees maintain balance by performing rotations whenever an insertion or deletion causes the height difference between left and right subtrees to exceed 1. There are four rotation cases.
Balance Factor
The balance factor of a node is: BF(node) = height(left) - height(right)
- BF = -1, 0, or 1 — balanced (no rotation needed)
- BF > 1 — left-heavy (needs right rotation or left-right rotation)
- BF < -1 — right-heavy (needs left rotation or right-left rotation)
Case 1: Right Rotation (Left-Left Case)
When a node is left-heavy and its left child is also left-heavy:
Before (BF=2): After right rotation:
30 20
/ / \
20 10 30
/
10
Case 2: Left Rotation (Right-Right Case)
Mirror of right rotation — node is right-heavy and right child is right-heavy:
Before (BF=-2): After left rotation:
10 20
\ / \
20 10 30
\
30
Case 3: Left-Right Rotation (Left-Right Case)
When a node is left-heavy but its left child is right-heavy — requires two rotations:
Before: After left rotate(10): After right rotate(30):
30 30 20
/ / / \
10 20 10 30
\ /
20 10
Case 4: Right-Left Rotation (Right-Left Case)
Mirror of left-right — node is right-heavy but right child is left-heavy:
Before: After right rotate(30): After left rotate(10):
10 10 20
\ \ / \
30 20 10 30
/ \
20 30
Complexity
Each rotation takes O(1) time — it only rearranges a constant number of pointers. After an insertion, at most one rotation (single or double) is needed. After a deletion, rotations may propagate up to the root, but this is still O(log n) total.
Use Case
AVL rotations are fundamental to understanding self-balancing trees. They appear in coding interviews (implement an AVL tree), database internals (B-tree rebalancing uses similar concepts), and compiler construction (balanced parse trees). The rotation concept also extends to Red-Black trees, treaps, and splay trees.