Balance by coloring
A red black tree is a binary search tree where each node carries one bit of extra information, a color that is either red or black. A small set of color rules keeps the tree approximately balanced without demanding the strict height equality an AVL tree requires.
The core rules
The balance follows from a few invariants:
- The root is black.
- A red node cannot have a red child, so reds never chain.
- Every path from a node down to a leaf passes through the same number of black nodes.
Together these force the longest path to be at most twice the shortest, which keeps the height bounded and searches fast.
Why it is popular
After an insertion or deletion, the tree restores its invariants through recoloring and a small number of rotations, working up toward the root. Compared with AVL trees, red black trees allow slightly looser balance, so they perform fewer rotations on updates, which makes them a common choice for library maps and sets where insertions and deletions are frequent.
Key idea
A red black tree colors nodes and enforces that reds never chain and black counts match on all paths, bounding the height and trading slightly looser balance for fewer rotations than an AVL tree.