Red-Black Colouring as a Height Proxy

A red-black tree stores one bit per node and enforces four rules: every node is red or black, the root is black, every leaf (the null pointers) is black, red nodes have black children, and every path from a node to a descendant leaf contains the same number of black nodes. The rules look arbitrary until they are read as a description of a different structure. Each black node together with its red children is one node of a multiway tree, and the colour rules are exactly the constraints that make that reading consistent. Once the correspondence is visible, the repair cases stop being a table to memorise and become the node splits and merges of the underlying multiway tree, expressed in binary form.

Reading a red-black tree as a 2-3-4 tree

Contract each red node into its black parent. The result is a tree whose nodes hold one, two, or three keys: a black node with no red children holds one key (a 2-node), one with a single red child holds two keys (a 3-node), and one with two red children holds three keys (a 4-node). The in-order sequence is unchanged by the contraction, since each red child sits on the side its key ordering dictates.

The colour rules translate directly. “Red nodes have black children” becomes “a node holds at most three keys”, because a red node cannot itself absorb another red node. “Every path has the same black count” becomes “all leaves of the multiway tree are at the same depth”, because the black count is the number of multiway nodes on the path. The two rules together say: a search tree in which every node holds one to three keys and all leaves are level. That is precisely a 2-3-4 tree, the B-tree of order 4.

The contraction is not unique in one direction: several red-black shapes map to the same 2-3-4 tree, because a 4-node can be represented with the middle key black and the outer two red, or with a different key at the top. The freedom is why red-black trees can be repaired with recolouring alone in some cases — the same multiway node is being re-expressed in a different binary shape without any structural change to the multiway tree.

/* The four rules, checked in one pass. Returns 1 if the subtree is a valid
   red-black tree and reports its black height through *bh. */
int check(node *t, int *bh) {
    if (t == NULL) { *bh = 1; return 1; }          /* leaves are black */
    int lbh, rbh;
    if (!check(t->left, &lbh) || !check(t->right, &rbh)) return 0;
    if (lbh != rbh) return 0;                     /* equal black height */
    if (is_red(t) && (is_red(t->left) || is_red(t->right))) return 0;
    *bh = lbh + (is_red(t) ? 0 : 1);
    return 1;
}

A null leaf contributes a black height of one by convention so that the arithmetic works out; the exact offset does not matter as long as it is consistent. The check is O(n) and is the only practical way to validate an implementation, because a tree can satisfy the search property while violating the colour rules, and the violation shows up only as a height that grows past the bound.

The height bound, derived rather than quoted

Let bh be the black height of the root. By the equal-black-height rule every root-to-leaf path passes through exactly bh black nodes. By the no-red-red rule, at most half the nodes on any path can be red, so the longest path has at most 2bh nodes. The shortest path has at least bh nodes, and since the tree is a search tree with all leaves at the same black depth, the number of internal nodes is at least 2^bh − 1.

Combining, n ≥ 2^bh − 1 gives bh ≤ log₂(n + 1), and the height in edges is at most 2 bh − 1, so h ≤ 2 log₂(n + 1). The factor of two is not an artifact of a loose argument; it is the price of allowing a node to hold up to three keys while representing them as up to three binary levels. A 2-3-4 tree of height d has at most 4^d leaves and at least 2^d, so its height is between log₄ n and log₂ n; the binary representation stretches each multiway level into at most two binary levels.

Compare with the AVL bound of about 1.44 log₂ n. The bound is asymptotic and the gap between the two constants narrows at small n — for a few hundred keys both bounds are within a level or two of log₂ n — but in the limit the red-black tree can be up to about 39 percent taller, and its average depth for random trees is larger as well. The payoff is entirely in the update path.

Why insertion repair terminates after one rotation

Insertion attaches a red leaf, which preserves the black-height rule but may violate the no-red-red rule. The repair walks up from the new node, and the cases are the 2-3-4 node operations in disguise.

When the new node’s parent is black, nothing is violated and the walk ends. When the parent is red, the grandparent is black, and the colour of the parent’s sibling — the “uncle” — decides the case. If the uncle is red, the multiway node has overflowed: the grandparent now has two red children plus a red parent, which is four keys in one node. The fix is to split the 4-node, pushing its middle key up to the parent. In binary terms that is a recolouring: parent and uncle become black, grandparent becomes red, and the violation moves up two levels to the grandparent. No pointers change.

If the uncle is black or absent, the multiway node has not overflowed; the binary representation is just skewed. A rotation or a pair of rotations re-expresses the same multiway node in a legal binary shape, with a recolouring to match. After that rotation the root of the repaired subtree is black, its children are red, and no ancestor can be violated, so the walk stops.

The distinction matters for the cost model. Recolouring is cheap and propagates; rotations are more expensive but bounded. An insertion performs at most two rotations, and the recolouring walk is at most O(log n) steps, each touching three nodes. The total is O(log n) with a small constant, and crucially the rotation count is constant regardless of tree size.

Deletion is the harder direction, and the asymmetry is the same one that appears in AVL deletion cascades: removing a black node reduces the black height of one path, and the repair may have to propagate upward. In multiway terms, a node has underflowed and must borrow a key from a sibling or merge with it. Borrowing is a rotation plus recolouring; merging is a recolouring that pushes a key down from the parent and may leave the parent underfull. The propagation is therefore the merge cascade, and it can reach the root. The rotation count stays bounded at three, but the recolouring can touch every level.

Where implementations hide the colour bit

The colour needs one bit, and a node needs two child pointers plus a key. On a 64-bit machine with 8-byte alignment, the low three bits of a child pointer are always zero, so the colour is usually stored in the low bit of one of them and extracted with a mask on every access. The saving is real: a node with two pointers, an 8-byte key, and a separate colour field padded to 8 bytes occupies 32 bytes, while the packed version occupies 24. That is a 25 percent reduction in node size, which matters because a smaller node means more nodes per cache line and fewer cache misses per descent.

The cost is that every pointer read must mask the bit off before dereferencing, and every colour test is a mask and compare. On architectures where unaligned or tagged pointers are handled in hardware this is a single instruction; the technique is common in language runtimes that already tag pointers for other reasons. Implementations that store the colour separately trade 8 bytes per node for simpler code, and the choice is usually made by measuring the tree’s memory profile rather than by principle.

A third option stores the colour in the sign bit of a key when keys are known positive, which works but couples the node layout to the key domain and breaks as soon as negative keys are needed. The tag-in- pointer approach has no such coupling.

Where the correspondence stops being useful

The 2-3-4 reading explains the repair cases and the height bound, and it predicts the shape of the delete algorithm. It does not predict the constant factors, and it misleads in two places.

First, the contraction is not an implementation strategy. Storing 2-3-4 nodes directly and splitting them is a B-tree, and a B-tree packs multiple keys into one node so that a search touches far fewer cache lines. The red-black tree keeps the same keys in binary nodes, which is worse for cache behaviour and better for the simplicity of single-key updates. The two structures are related by the correspondence but are not interchangeable, and the trade between them is the subject of B-tree node occupancy and splits.

Second, the colour rules admit shapes that the 2-3-4 reading treats as equivalent but that differ in depth by a factor of two. A 4-node represented with the middle key at the top has two red children at the same level; represented with an outer key at the top, it has a red child and a red grandchild. The second shape is legal under the colour rules and one level deeper. Implementations that always push the middle key up avoid this, but the invariant does not require it, so a valid tree can be taller than the canonical representation of the same multiway tree. The 2 log₂(n+1) bound already accounts for the worst of these shapes.

The final limitation is that the correspondence says nothing about concurrency. Readers that traverse while a writer repairs must see a consistent shape, and the colour rules do not by themselves give a protocol for that. The techniques that do — copying the path, or locking nodes in descent order — are independent of the colouring, and they apply equally to AVL and weight-balanced trees.