BSTs that rebalance themselves on every change so they never degrade into a slow line.
after each insert/delete, rotate subtrees to keep height ~ log n
Frequently asked questions
How is a self-balancing tree like a well-run tournament bracket?
Think of a tournament bracket that keeps reshuffling so no side becomes lopsided - every player reaches the final in the same few rounds. AVL and red-black trees do this automatically: after each insertion or deletion they rotate themselves so no branch grows much deeper than another. That guarantees the path from top to bottom stays around log(n), so lookups are always fast - unlike a plain BST, which can become a lopsided, slow bracket if entries arrive in a bad order.
What does it mean for a tree to be 'balanced', and why does it matter?
Balanced means no part of the tree is allowed to grow much deeper than another, so the overall height stays close to log(n). Height is what determines search speed, because a search walks one path from root to leaf. A balanced tree of a million keys is only about 20 levels deep, so searches take about 20 steps. An unbalanced tree could be a million levels deep in the worst case. Balancing turns the BST's 'usually fast' into 'always fast'.
How do AVL and red-black trees actually keep themselves balanced?
Through rotations - small, local restructurings that swap a parent and child while preserving the search ordering. After each insert or delete, the tree checks a balance condition and, if violated, performs one or two rotations to restore it. AVL trees keep a height difference of at most one between siblings, making them very strictly balanced. Red-black trees use colour rules (each node red or black, with constraints) that allow slightly looser balance but cheaper rebalancing. Both guarantee height stays around log(n).
What is the difference between AVL and red-black trees in practice?
AVL trees are more strictly balanced, so they are slightly faster for lookups but do more rotation work on inserts and deletes. Red-black trees are a bit less balanced but rebalance more cheaply, making them better when writes are frequent. As a rule of thumb: AVL for read-heavy workloads, red-black for write-heavy or general-purpose use. That is why red-black trees are the common choice in standard libraries (C++ std::map, Java TreeMap) and the Linux kernel, where mixed workloads are the norm.
Does the balancing slow down inserts compared to a plain BST?
Slightly, yes - each insert or delete may trigger a rotation or two, which is extra work a plain BST skips. But the cost is small and constant per operation, and it buys a guarantee: the tree can never degrade into the O(n) line that cripples a plain BST. So you pay a little on every update to guarantee that no operation is ever catastrophically slow. For systems that need predictable worst-case performance, that trade is almost always worth it.
When would you NOT use a self-balancing tree?
When you do not need ordered operations, a hash table gives O(1) average lookup and is simpler - so for pure exact-key lookup, prefer a hash table. When data lives on disk rather than in memory, a B-tree or B+ tree is better because it minimises slow disk reads by packing many keys per node. And when you want tree-like performance with simpler code, a skip list achieves similar guarantees using randomness instead of rotations. Self-balancing BSTs shine specifically for in-memory ordered data with frequent changes and a need for guaranteed log-time operations.