1. One-Liner
AVL rotations are local tree surgeries (left/right) that restore balance while keeping BST order after inserts or deletes.
2. The Problem It Solves
After updating an AVL tree, a node’s balance factor (left height − right height) can become ±2. Rotations rehang subtrees so heights differ by at most 1 again—keeping O(log n) height.
3. The Core Idea
A right rotation at unbalanced node y with heavy left child x promotes x to root of this subtree; x’s old right becomes y’s new left. Left rotation is mirror. LR/RL double rotations compose two singles on the grandchild path.
4. How It Works (Step-by-Step)
| Step | Action | ||
|---|---|---|---|
| 1 | Detect imbalance: ` | balance | > 1` at node z. |
| 2 | If left-heavy and left child left-heavy → right rotate(z). | ||
| 3 | If left-heavy and left child right-heavy → left rotate(left child), then right rotate(z). | ||
| 4 | Mirror cases for right-heavy. | ||
| 5 | Update heights from leaves up after each rotation. |
5. Dry Run Example
Insert into left-left pattern: imbalance at A, heavy left B, B’s left C. Single right(A) makes B root, A right child, BST order preserved.
6. Key Properties
| Property | Detail |
|---|---|
| Inorder | Unchanged across rotation |
| Height | Drops at the problem spot |
| Cases | LL, RR, LR, RL |
7. Where It Is Used
| Context | Use |
|---|---|
| Databases / maps | Guaranteed worst-case log n ops |
| Real-time | Predictable latency vs unbalanced BST |
8. Interview Tips
Draw before/after pointers. State balance factor definition. Know four cases by pattern (not memorizing letters only). Compare with red-black (looser balance, fewer rotations amortized).
9. Comparison with Other Algorithms
| Structure | Height | Rotation cost |
|---|---|---|
| AVL | Stricter O(log n) | More rotations on insert |
| Red-black | ≤ 2× black height | Fewer rotations typical |
| Treap | Randomized expected log | Heap key + BST |
10. Complexity
| -- | -- |
|---|---|
| Rotation | O(1) pointer changes |
| Insert/Delete overall | O(log n) find + O(1)–O(log n) rebalancing |
Implementation Example (PYTHON)
class AVLNode:
def __init__(self, k):
self.key, self.h = k, 1
self.left = self.right = None
def height(n): return 0 if not n else n.h
def rotate_right(y):
x = y.left
t2 = x.right
x.right, y.left = y, t2
y.h = 1 + max(height(y.left), height(y.right))
x.h = 1 + max(height(x.left), height(x.right))
return x