Red-Black Trees: Balance Without Counting

Five invariants that bound the height

A red-black tree is a binary search tree where every node is coloured red or black, and four extra rules — on top of ordinary BST ordering — are maintained at all times:

1. Every node is red or black.
2. The root is black.
3. Every leaf (NIL / null) is considered black.
4. A red node never has a red child (no two reds in a row on any path).
5. Every path from a given node to any of its descendant NIL leaves
   passes through the same number of black nodes — the node's "black-height".

None of these rules mention height directly, which is the whole trick: rather than tracking and rebalancing on an exact height number (as an AVL tree does), a red-black tree enforces a local colour constraint that is cheap to check and cheap to repair after a single insert or delete, and that constraint happens to imply a global height bound.

Why the height stays O(log n)

Rule 4 says you can never have two red nodes in a row, so on any root-to-leaf path, at most every other node is red. That means the path's total length is at most twice its black-height. Rule 5 says every path from the root shares the same black-height bh. A subtree with black-height bh contains at least 2^bh − 1 internal nodes (a clean induction: doubling the black-height at least doubles the node count, since both children of a black node have black-height bh−1 or bh). Put together:

n >= 2^bh - 1        (n = number of internal nodes)
=> bh <= log2(n + 1)
=> height <= 2 * bh <= 2 * log2(n + 1)

So no matter what order keys are inserted or deleted in, the longest possible root-to-leaf path is never more than roughly twice the shortest, and both are O(log n). Search, insert and delete all walk at most one root-to-leaf path, so all three are O(log n) worst case — the same asymptotic guarantee as a perfectly balanced tree, at a fraction of the rebalancing cost.

Rotations and recolouring on insert

A newly inserted node is always coloured red first (this can never violate the black-height rule, since it adds no black nodes to any path) and then a fixup routine walks upward repairing any red-red violation it caused. The fixup has two very different personalities depending on the colour of the new node's uncle (the sibling of its parent):

uncle is RED:
  recolour parent and uncle black, grandparent red,
  then continue fixing up from the grandparent (may cascade to the root)

uncle is BLACK (or missing):
  1-2 tree rotations (LL, LR, RL or RR case) plus a recolour,
  which fixes the violation locally in O(1) rotations — no further
  cascading is needed

The recolour-only case can, in principle, propagate all the way to the root, but each rotation case terminates the fixup immediately, which is why insertion still costs O(1) amortised rotations even though the recolouring chain is O(log n) in the worst case.

Delete is the hard part

Deleting a node that turns out to be black can drop the black-height of one subtree below its siblings, creating a "double-black" deficiency that has to be pushed upward and resolved through a longer case analysis than insertion needs — the classic implementation has four distinct sibling-colour cases, each with its own rotation and recolour recipe. It is the single reason red-black tree implementations are notoriously fiddly to get right from scratch, and why most production code reaches for a well-tested library implementation rather than writing one from memory.

Where it actually gets used

C++'s std::map and std::set are, in every mainstream standard library implementation, red-black trees. Java's TreeMap and TreeSet are too. The Linux kernel's Completely Fair Scheduler keeps runnable processes in a red-black tree ordered by virtual runtime, so picking the next process to run and re-inserting a process after it runs are both O(log n) operations on a tree that stays balanced under an unpredictable, high-frequency stream of inserts and deletes — exactly the workload red-black trees are tuned for.

Frequently asked questions

Try it live

Everything above runs in your browser — open Red-Black Trees and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.