Balance through coloring
A red black tree is a self balancing binary search tree that keeps itself short using a clever set of color rules rather than exact height tracking. Every node is painted red or black, and the colors must satisfy a few invariants that together bound the height.
The invariants
The rules look arbitrary but work in concert.
- The root is black, and leaf sentinels are black.
- A red node cannot have a red child, so reds never appear consecutively on a path.
- Every path from a node down to its leaf sentinels passes through the same number of black nodes, called the black height.
Equal black heights plus no two reds in a row force the longest path to be at most twice the shortest, keeping the tree approximately balanced.
Why it is popular
Compared to the strict AVL tree, a red black tree allows a slightly taller shape, which means it needs fewer rotations during insertion and deletion. Updates instead do local recoloring first, rotating only when recoloring cannot fix a violation. This makes red black trees a favorite for libraries with mixed read and write workloads, such as ordered maps and sets.
Key idea
A red black tree enforces color rules, no two reds in a row and equal black heights on every path, to keep the longest path within twice the shortest, achieving approximate balance with fewer rotations than an AVL tree.