Red-black trees

A plain binary search tree has a wonderful average case and no floor under its worst one: feed it sorted input and it degenerates into a list, quietly turning every operation linear. Red-black trees are one of the answers to that, and the interesting thing about them is not how the balancing works but what using one actually asks of you.

The colours are a height bound#

The problem to solve is that a search tree’s cost is its height, and nothing about the ordering rule constrains height. Insert keys in ascending order into an unbalanced tree and every node becomes the right child of the last, producing a structure with the shape of a list and the overhead of a tree.

The colouring is a way to bound the height without ever measuring it. Each node carries one bit, and two rules govern them: a red node may not have a red child, and every path from a given node down to its leaves passes through the same number of black nodes. The second rule makes all paths equal in black nodes; the first stops reds from padding any one path by more than doubling it. Together they force the longest root-to-leaf path to be at most twice the shortest, which is what makes the height logarithmic.

What makes this practical is that the rules are local. An insertion or deletion can only break them near where it happened, so repair is a handful of recolourings and rotations in that neighbourhood rather than a pass over the tree. That is the actual trick — not the specific rules, but that a global property about height is maintained entirely by local checks. Java’s TreeMap is documented as a Red-Black tree based implementation and converts that into the promise callers care about: guaranteed log(n) time for containsKey, get, put and remove. Guaranteed, not typical, which is the whole point of the colouring — and it holds however the keys arrive, unlike an unbalanced tree whose shape is decided by insertion order.

The word repair is carrying weight in that sentence, so it is worth saying what the repair actually is. A rotation is the primitive: take a node and one of its children, swap which of the two is the parent, and reattach the subtree caught between them. Java’s TreeMap implements it as rotateLeft and rotateRight, each a handful of pointer assignments — four apiece — and each marked in the source as taken from CLR. The fixed count is the point: a rotation costs the same whether the tree holds a hundred nodes or a hundred million.

What makes a rotation legal is what it leaves alone. Reparenting changes which node sits above which, and therefore the height of that corner of the tree — that is the whole reason to do it. It does not change the left-to-right order of the values, so a tree that satisfied the search-tree rule before the rotation still satisfies it after. That is why balancing can be bolted onto an ordered structure at all, and it is checkable in one line: an in-order walk reads out the same sequence before and after.

Insertion is easy, deletion is not#

The two operations get named in one breath, as though repairing the tree after a delete were the mirror of repairing it after an insert. It is not, and the asymmetry is visible in any implementation you open. In TreeMap, fixAfterInsertion handles two symmetric cases — whether the new node’s parent is a left or a right child — each branching on the colour of its uncle. fixAfterDeletion is around two and a half times longer and carries four major cases with two or three sub-cases apiece.

The reason is what each operation is capable of breaking. An insert adds a red node, so it cannot change any path’s black count; the only rule it can violate is the one forbidding a red node under a red parent, and that violation is local to wherever the node landed. A delete can remove a black node, which changes the black count on every path running through it — a violation of the rule requiring all those paths to agree, and one that propagates upward until it finds a red node to absorb it or runs out of tree.

Which is the honest answer to whether you should ever write one. The rules are short enough to recite from memory, and the deletion fix-up is where a hand-written implementation quietly goes wrong — not with a crash, but with a tree that is still a correct search tree and no longer a balanced one, so it keeps returning right answers while the guarantee you adopted it for has gone.

What the structure charges for that guarantee is worth stating, because everything above describes what it buys. Every node carries a colour — in TreeMap a single boolean field per entry, defaulted to black — alongside the parent pointer the rotations need in order to work upward. And every write may do rebalancing work a plain search tree would skip. Reads pay none of it. That is the trade in one line: the write path does a bounded amount of extra work so the read path stops depending on the order the data happened to arrive in.

The ordering is the equality#

Here is the part that catches people, and it has nothing to do with balancing. A sorted map never calls equals. It finds keys by comparison, descending left or right until the comparison returns zero, and it treats that zero as meaning this is the key.

Java’s documentation states the consequence carefully: the Map interface is defined in terms of the equals operation, while a sorted map performs all key comparisons using compareTo or compare, so two keys deemed equal by that method are, from the standpoint of the sorted map, equal. The ordering must therefore be consistent with equals if the map is to implement Map correctly.

Give it a comparator that disagrees — one that sorts people by surname, say, while equals compares an identifier — and nothing throws. Two distinct people with the same surname compare as zero, so the second silently replaces the first, and the map now holds fewer entries than you put into it. It is the same fault line a search that consults only ordering and never equality exposes, arriving here as a data-loss bug rather than a lookup miss.

Where it goes wrong#

The first mistake is reaching for a sorted map when a hash map would do. A guaranteed logarithmic lookup is a fine thing and it is still slower than an average-case constant one, so if you never ask for order — no range scans, no nearest key, no iteration in sequence — you are paying for a guarantee you never use. The question is not which structure is faster in the abstract but whether ordering is part of what you need at all, which is where the constant-time lookup and its condition is usually the better trade.

The second is a mutable key. The tree placed the key by comparing it once, at insertion, and never revisits that decision. Change a field the comparison depends on and the key now sits in a position the comparison would never lead to — the entry is present, iteration lists it, and lookup cannot find it. No structure that decides placement from a value can survive that value changing underneath it, which is why keys are conventionally values that never change.