Red-Black Trees

Motivation

A standard BST degenerates to $O(n)$ height when keys are inserted in sorted order. Red-black trees (RBTs) are binary search trees that maintain approximate balance through an extra colour attribute per node, guaranteeing $O(\log n)$ worst-case height with simple insertion and deletion algorithms.

They generalise 2-3-4 trees into binary form: the structural logic of a multi-way tree is encoded in node colours rather than variable child counts.

The Five Red-Black Properties

A valid red-black tree satisfies:

1. Every node is either red or black.
2. The root is black.
3. The leaves (NIL sentinels) are black and contain no keys.
4. Both children of a red node are black (no two consecutive red nodes on any path).
5. For each node, all simple paths to descendant leaves contain the same number of black nodes (the black-height is balanced).

Properties 4 and 5 are the crucial ones: Property 4 limits how unbalanced paths can be (you cannot have long chains of nodes), and Property 5 forces uniform black-node depth across all paths.

Black-Height

The black-height bh(x) of a node x is the number of black nodes on any path from x (excluding x itself) to a leaf. By Property 5, all such paths have the same count.

Example: in a tree with root=black, two black children, and red grandchildren, the root’s black-height is 2. The leaves (NIL) have black-height 0.

Height Bound

Lemma: A red-black tree with $n$ internal (non-leaf) nodes has height $h \le 2\log(n+1)$.

Proof sketch: For any node $x$, the subtree rooted at $x$ has at least $2^{bh(x)} - 1$ internal nodes (minimum when all nodes are black, forming a complete binary tree down to black-height depth). The root’s black-height is at least $h/2$ (by Property 4, at most half the nodes on any path can be red). Thus:

$n \ge 2^{h/2} - 1 \quad\Rightarrow\quad h \le 2\log(n+1)$

This guarantees $O(\log n)$ worst-case height, hence $O(\log n)$ search, insert, and delete.

Example: Insertion into a RBT

Insert keys [N, D, A] into an initially empty red-black tree:

• Insert N as the root (black, by Property 2).
• Insert D < N: add as left child, coloured red. No violation (parent is black).
• Insert A < D < N: add as left child of D, coloured red. Violation! A (red) has red parent D.

The fix depends on the colour of the uncle (the parent’s sibling): D’s sibling is NIL (black leaf). Since the uncle is black, a rotation at N (right-rotate) and recolouring restores balance. Result: D becomes black root, A and N are red children.

Connection to 2-3-4 Trees

The red-black properties are an Oulipo-style characterisation: they describe valid trees without mentioning 2-3-4 trees. But the underlying reason they work is the isomorphism with 2-3-4 trees:

• A black node anchors its 2-3-4 node.
• Red nodes are “glued” to their black parent, representing extra keys in the same 2-3-4 node.
• The black-height equals the 2-3-4 tree height.

This provides both intuition and correctness: RBT insert/delete correctness follows from 2-3-4 tree correctness, since each operation translates.

Summary

Property	Requirement
1	Every node red or black
2	Root is black
3	Leaves (NIL) are black
4	Red node → black children
5	All paths have same black count
Height bound	$h \le 2\log(n+1)$
Search/Insert/Delete	$O(\log n)$ worst case
Isomorphic to	2-3-4 tree (B-tree with $t=2$)