How do you keep a dictionary fast when keys arrive in arbitrary order? A plain binary search tree can collapse into a linked list. Self-balancing trees repair that drift with tiny local rewrites, so lookup, insertion, and ordered traversal stay fast even under hostile insertion orders.
A binary search tree looks ideal on paper: go left for smaller keys, right for larger ones, and every step discards half the remaining search space. But that only holds when the tree stays roughly balanced.
If keys arrive in sorted order, a plain BST keeps inserting to the same side. The tree stops looking like a branching structure and starts looking like a spine. Search time drifts from O(log n) toward O(n).
An AVL tree stores one extra piece of local information: each node knows the height of its left and right subtrees. Their difference is the balance factor. If that factor ever leaves the range -1..1, the tree repairs itself with a rotation.
The important idea is that rotations are not magic. They preserve the in-order ordering of keys while changing the shape of the tree. The logic falls directly out of “which side got too tall?” and “did the child lean the same way or the opposite way?”
The rotation algorithm is a two-level diagnosis. First find the first ancestor whose balance factor left the safe range; that is the node you will repair. Then inspect its heavy child. If the child leans in the same direction as the parent imbalance, one rotation is enough: LL becomes a right rotation, RR becomes a left rotation. If the child leans the opposite way, you must straighten the child first and then rotate the parent: LR means left-rotate the left child, then right-rotate the parent; RL is the mirror image.
What makes this work is that the median of the three involved keys always rises into the middle. The in-order ordering of keys is preserved, but the subtree becomes shorter and more balanced. That is the whole trick: AVL rotations are local rewrites that fix shape without changing search order.
Red-black trees encode a looser balance rule. Instead of exact height differences, they color each node red or black and enforce a handful of invariants: no red node may have a red child, and every root-to-leaf path must contain the same number of black nodes.
That is harder to explain than AVL, but easier to live with in many production systems. The tree is not as tightly balanced, yet updates usually perform fewer structural repairs. Searches remain logarithmic, and the looser discipline often wins on implementation cost and mutation throughput.
Hash tables are the right default when all you need is exact key lookup. But the moment you care about order, a balanced tree starts doing things a hash table fundamentally does not want to do: range scans, predecessor/successor queries, sorted iteration, and stable worst-case behavior.
| Need | Hash Table | Balanced Tree |
|---|---|---|
| Exact lookup | Usually faster average case | Still O(log n) |
| Ordered iteration | No natural order | Built in |
| Range query | Scan everything | Start at lower bound, walk in order |
| Floor / ceiling | Not meaningful | Natural operation |
| Worst-case lookup | Depends on hashing and collision strategy | Guaranteed logarithmic height |
The implementation below uses AVL balancing to keep the code compact while still supporting the operations that make trees worth reaching for: exact lookup, insertion, deletion, ordered iteration, floor/ceiling, and range queries. The map is generic because you can supply a comparator.