Fixing the balance problem
An AVL tree is a binary search tree that repairs itself to stay short. Each node tracks the heights of its subtrees, and the tree enforces a balance condition: for every node, the heights of its left and right subtrees differ by at most one. This strict rule keeps the tree height proportional to the logarithm of the number of nodes, so search, insert, and delete stay fast.
Rotations restore balance
After an insertion or deletion, a node may become unbalanced. The tree fixes this with rotations, local rearrangements that preserve the search order while reducing height.
- A single rotation handles a straight line imbalance, leaning all left or all right.
- A double rotation, two rotations combined, handles a bent imbalance where the heavy grandchild is on the inside.
Only nodes along the path back to the root need checking, so rebalancing is cheap.
The trade
AVL trees are rigorously balanced, giving excellent worst case lookup. The price is more frequent rotations during updates than looser schemes accept, which is why read heavy workloads favor AVL while write heavy ones may prefer alternatives.
Key idea
An AVL tree keeps every node's subtree heights within one of each other, using single and double rotations after updates to guarantee a shallow tree and fast worst case search, insert, and delete.