AVL tree
An AVL tree is a binary search tree where every node satisfies a strict balance condition: the heights of its left and right subtrees differ by at most 1. After each insert or delete, the structure is repaired with a bounded number of rotations, keeping height O(log n) and BST operations fast in the worst case.
- Balance factor and why rotations appear
- Single vs double rotation patterns
- Complexity vs plain BST and red-black trees
Start from Binary search tree and BST (linked list). AVL was one of the first widely taught self-balancing BST designs (Adelson-Velsky and Landis, 1962).
1) Balance factor
For each node t, define
balance(t) = height(t→left) − height(t→right).
An AVL tree requires balance(t) ∈ {−1, 0, +1} at every node. After an insert or delete, walk upward from the change and fix the first “out of range” ancestor using rotations.
2) Rotations
Four structural cases restore balance while preserving BST ordering:
| Case | Situation | Fix |
|---|---|---|
| LL | Too heavy on the left of the left child | Right rotate at the unbalanced node |
| RR | Too heavy on the right of the right child | Left rotate at the unbalanced node |
| LR | Left subtree heavy, bend is “left-right” | Rotate left at left child, then right at root of fix |
| RL | Right subtree heavy, bend is “right-left” | Rotate right at right child, then left at root of fix |
Implementations store subtree heights or balance factors in each node and update them along the rebalance path.
3) Complexity
With n keys, AVL height is at most about 1.44 log₂(n+2) − 0.328 (classic bound)—still Θ(log n). Search, insert, and delete each cost O(log n); insert/delete may perform O(log n) rotations in the worst case but only a small constant number per operation is typical in many textbooks’ amortized analyses for inserts.
4) AVL vs red-black (brief)
AVL keeps stricter balance than typical red-black trees, so AVL often has slightly faster searches and more rotations on updates. Red-black rules are looser (fewer rotations on insert in practice), which can matter for write-heavy maps—see Red-black tree.
Key takeaway
AVL trees guarantee logarithmic height by enforcing a ±1 subtree-height rule and fixing violations with rotations. They are the canonical “strict balancing” BST for teaching; production libraries often prefer red-black or other structures for constant-factor reasons.
See also: BST operations · Next up: Red-black tree · B-tree