Red-Black Trees, One Repair at a Time

This is the first entry in a series on computer science data structures and algorithms. I want the series to be practical, not only correct. Red-black trees are a good starting point because the hard part is not the binary search tree. The hard part is watching a local violation move through the tree until the invariants hold again.

The demo below uses XState as the source of truth for the tutorial state. Phaser renders the current snapshot. Press Random to generate a new insertion order, then step through it manually or let Auto loop through the trace every second. The values, step, and autoplay option are encoded in the URL so a specific run can be shared.

Jump to the interactive tree.

What a red-black tree promises

A red-black tree is a binary search tree with one extra bit per node: red or black. The colors enforce enough balance that search, insert, and delete stay logarithmic. The tree is not perfectly balanced like an AVL tree. It accepts some slack so updates are cheaper.

The rules are small. The root is black. Every leaf sentinel is black. A red node cannot have a red child. Every path from a node to its descendant leaves has the same number of black nodes. That last number is the black-height. It is the quiet invariant behind the whole structure.

Insertion starts red

When a new value is inserted, it starts as red. That choice is deliberate. Adding a black node would immediately change the black-height of one path and force a broader repair. Adding a red node leaves black-height alone and only risks one local problem: a red parent with a red child.

If the parent is black, the tree is done. If the parent is red, the repair logic looks at the uncle. The uncle is the sibling of the parent. Its color decides whether we recolor or rotate.

Red uncle means recolor

When the parent and uncle are both red, rotation is unnecessary. Paint the parent and uncle black, paint the grandparent red, then continue checking from the grandparent. The violation may move upward, but the black-height stays balanced because both sides of the grandparent gained the same black node.

Randomized insertions make this case easier to learn because the same rule shows up in different parts of the tree. The numbers change, but the repair stays the same: parent and uncle black, grandparent red, then continue upward.

Black uncle means rotate

When the parent is red and the uncle is black, recoloring alone cannot fix the shape. The tree needs a rotation. If the new node forms a triangle, such as left-right or right-left, rotate at the parent first. That converts the shape into a line. Then recolor and rotate at the grandparent.

In one run the triangle may be left-right. In another it may be right-left. That variation is the point. Watch for the inner child first, then the line case after the first rotation normalizes the shape.

Why the state machine helps

A red-black insertion is a sequence of constrained states. Empty tree. Insert node. Check parent. Check uncle. Recolor, rotate, or stop. XState makes that sequence explicit. The tutorial cannot skip from the red-uncle case into the final rotation because that transition does not exist.

That is also how I prefer to teach algorithms with animation. The animation is useful only if the underlying model is honest. Phaser can make the movement legible, but the state machine keeps the explanation precise.

What to watch for

Step through the demo twice. The first pass should be about the colors: new nodes enter red, red uncles trigger recoloring, and the root repair is a special case. The second pass should be about shape: rotations preserve binary-search order while moving the local root of a subtree.

Once those two ideas separate, red-black trees become less mysterious. The colors decide whether the tree is allowed to keep its shape. The rotations decide which shape restores the rules.