AVL trees solve the BST-degenerates-to-a-list problem with a strict height invariant. They work, but the strictness has a cost: deletion can trigger up to O(log n) rotations, and every node stores a 4-byte height.

Red-black trees take a different approach. They relax the balance requirement just enough that any insertion or deletion can be repaired with at most 2 or 3 rotations and some color flips, regardless of tree size. The height is no longer the tightest possible, but every operation has bounded rebalancing work. That predictability is why almost every production sorted map, Java's TreeMap, C++'s std::map, the Linux kernel's process scheduler and epoll, ships a red-black tree internally.

In this chapter, we'll cover:

The rotations used here are the same left and right rotations introduced in the AVL Tree chapter, applied with a different rebalancing rule.

A red-black tree is a BST where every node carries one extra bit, its color, either red or black. The colors are chosen so the tree satisfies these five rules at all times:

Property 4 prevents long red-red chains. Property 5 forces every root-to-leaf path to have the same black structure. Together they guarantee that the longest path is at most twice the shortest one, which is exactly what bounds the height.

Here is a small valid red-black tree:

Every property checks out:

Let bh(x) denote the black-height of node x: the number of black nodes on any path from x to a null descendant (excluding x itself, by convention).

A subtree rooted at x contains at least 2^bh(x) - 1 internal nodes. The argument is by induction. The base case is a node whose children are both null: its black-height is 0, and 2^0 - 1 = 0 internal descendants. For the inductive step, each child has black-height bh(x) or bh(x) - 1 depending on its own color, so by induction each child's subtree holds at least 2^(bh(x) - 1) - 1 internal nodes, and the two subtrees plus x itself give 2 · (2^(bh(x) - 1) - 1) + 1 = 2^bh(x) - 1.

Property 4 says at least half the nodes on any root-to-leaf path are black, so for a tree of height h, bh(root) ≥ h / 2. Combine the two:

n ≥ 2^(h/2) - 1, which gives h ≤ 2 · log2(n + 1).

The height is at most twice that of a perfectly balanced tree. Tighter than that is what AVL gives you. Looser than that is what red-black gives up to keep rebalancing cheap.

Both structures end up at O(log n) for every operation. The choice between them comes down to rebalancing cost.

The delete row is the one that matters in practice. An AVL delete may cascade rotations all the way to the root. A red-black delete never does more than three. For a workload with frequent inserts and deletes, that bounded cost is more valuable than the slightly shorter tree.

This is also why nearly every system standard library picks red-black:

You almost never need to write one from scratch. You should still understand how it works because the underlying ideas (insert as red, fix only what is broken, push violations up the tree) show up in many balanced data structures.

A new key is always inserted as a red leaf with two null (black) children. Why red? A red insert can only violate property 4 (no two reds in a row) and only at the new node's parent. It cannot violate property 5 (equal black-heights), because adding a red leaf does not change any black-height. Fixing one property is easier than fixing several.

If the parent of the new node is black, you are done immediately. If the parent is red, you have a red-red violation to fix. The fix-up routine walks up the tree from the new node, handling one of three cases at each step.

Case 1: Uncle is Red

The new node's parent P is red and the grandparent's other child (the "uncle" U) is also red.

Before:

Fix:

After:

The red-red conflict between P and Z is gone. The grandparent has turned red, which can create a new red-red conflict with its parent further up the tree. So the loop continues.

This case is the only one that pushes the problem upward instead of resolving it on the spot, which is why fix-up may walk O(log n) levels even though each level is O(1).

Case 2: Uncle is Black, New Node is "Zigzag" Child

P is red, U is black, and Z is on the opposite side of P from P's position relative to G (left-right or right-left).

Fix:

After the left rotation around P (in this left-right example), Z and P swap roles: Z becomes the child of G and P becomes the left child of Z. The result is a "straight" red-red chain, ready for Case 3.

Case 3: Uncle is Black, New Node is "Straight" Child

P is red, U is black, and Z is on the same side of P as P is of G (left-left or right-right).

Fix:

After:

No more red-red violation. The rotation does not change any black-height, so property 5 still holds. The loop terminates.

The last step of insert-fixup, regardless of which case ran, is to force the root color back to black. This handles the corner case where the loop bubbled all the way up.

Walkthrough: Insert 10, 20, 30

The same sequence that broke a plain BST.

After inserting 10 (forced black as root) and 20 (red):

(Note: BST order places 20 to the right of 10. The diagram above shows it as A's child, where B = 20 sits on the right.)

Insert 30 as red, child of 20:

Red-red violation between 20 and 30. Uncle of 30 is null (black). The configuration is right-right (straight), so this is Case 3:

Result:

The root color is forced back to black if needed (here 20 is already black). Inserting 40 next would hit Case 1 (uncle 10 is red), recolor 10 and 30 to black and 20 to red, then force the root back to black.

Deletion is the harder operation. The BST deletion step itself is standard, replace the deleted node with its in-order successor when it has two children. The interesting work happens when the node actually removed from the tree is black, because that removal shortens every path through that node by one black, which violates property 5.

The standard trick is to assign the "extra black" to the child that takes the deleted node's place, treating it as if it carried a phantom extra black token. This temporary state is called double-black. The fix-up loop pushes the double-black token up the tree, resolving it through one of four cases at each step.

If the deleted node was red, no fix-up is needed: black-heights are unchanged.

Case 1: Sibling is Red

The double-black node's sibling S is red. Recolor S black and the parent red, then rotate the parent toward the double-black side. This transforms the problem into one of cases 2 through 4, where the sibling is black.

Case 2: Sibling is Black with Two Black Children

Recolor S red and move the double-black token up to the parent. The subtree's overall black-height drops by one, and the parent now carries the double-black. Continue the loop one level higher.

Case 3: Sibling is Black, Its Near Child is Red, Far Child is Black

Rotate S away from the double-black, swap colors between S and its (formerly) near red child. This transforms the configuration into Case 4.

Case 4: Sibling is Black, Its Far Child is Red

Color the sibling with the parent's color, color the parent black, color the far child black. Rotate the parent toward the double-black. The token is consumed and the loop terminates.

The two takeaways from delete-fixup: the deepest cases (3 and 4) terminate the loop, and Case 2 is the only one that propagates the violation. So the total number of rotations is bounded by 3, regardless of how many recoloring steps happen.

This implementation uses a sentinel NIL node for all nulls, which is the trick from CLRS that keeps the case analysis clean: NIL.color = BLACK and every leaf points at the same NIL, so you can dereference NIL.parent and NIL.color without null checks.

A few notes on the implementation:

The same algorithm sits behind a surprising amount of infrastructure:

The reason for this dominance is the deletion bound. A system that runs for months under sustained insert/delete load cannot afford an O(log n) worst-case rotation on every delete. Red-black trees keep that at 3, regardless of tree size.

The point of writing a red-black tree from scratch is to understand how it works, not to use it in production. If you need a sorted map in real code, use the library:

These are tuned and tested far better than anything you can reasonably write under interview time pressure. The mental model from this chapter is what carries over: insert is O(log n) with at most 2 rotations, and delete is bounded at 3.