Red-Black Tree

A red-black tree is a binary search tree that paints every node red or black and follows a handful of coloring rules. Those rules guarantee the longest root-to-leaf path is at most twice the shortest, so the tree stays balanced and search, insert, and delete all run in O(log n) — no matter what order you insert keys.

The five invariants every red-black tree maintains:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (the implicit null children) is black.
4. A red node never has a red child (no two reds in a row).
5. Every root-to-leaf path passes through the same number of black nodes (the "black height").

Intuition

Invariant 5 is the balance engine: if every path has the same black height, and invariant 4 forbids stacking reds, then no path can be more than twice as long as another. Red nodes are the "slack" the tree uses to absorb an insert without immediately restructuring.

That is why we always insert red: a red leaf changes no path’s black-count, so invariant 5 is never touched. The only thing that can go wrong is invariant 4 — a red node landing under a red parent. Fixing that one local conflict is the whole job, and the uncle’s color tells us how: a red uncle means we can fix it by flipping colors (cheap, no structure change), while a black uncle forces a rotation to physically rebalance the subtree.

Walk through it

Step through the animation on the right. Dim nodes tagged B are black; glowing nodes tagged R are red. The z pointer marks the node we are currently fixing, and the label up top names the active case.

First we insert 4 as a red leaf under 5. To show the red-uncle case, focus on grandparent 10: it has a red child 15 on the other side — that is the uncle. Because the uncle is red, we apply Case 1 — recolor: flip parent 5 and uncle 15 to black, and push grandparent 10 to red. Nothing moves; only colors change. z then jumps up to 10, the loop ends, and the final rule repaints the root black.

Next we insert 3 as a red leaf under 4. Now 3 (red) sits under parent 4 (red) — a real violation. Its uncle is the missing sibling of 4, which counts as black. A black uncle means recoloring alone cannot fix the imbalance, so we apply Case 2 — rotate: 3, 4, and 5 form a left-left line, so we rotate right around grandparent 5. Node 4 rises to take 5’s place, 5 drops to become 4’s right child, and we recolor 4 black and 5 red. The subtree is balanced, no red has a red child, and every path still has the same black height.

The code, line by line

def insert(root, key):
    z = bst_insert(root, key)   # new node, colored RED
    z.color = RED
    fix_insert(z)
 
def fix_insert(z):
    # restore: no red node may have a red child
    while z.parent and z.parent.color == RED:
        uncle = sibling(z.parent)
        if uncle and uncle.color == RED:
            z.parent.color = BLACK   # Case 1: red uncle
            uncle.color = BLACK
            z.parent.parent.color = RED
            z = z.parent.parent      # move up, re-check
        else:
            rotate(z)                # Case 2: black uncle
            recolor(z.parent, z.parent.parent)
            break
    root.color = BLACK               # root is always black

• Lines 2–3: insert with the ordinary BST rule, then paint the new node red so no path’s black-count changes.
• Line 8: the fix-up loop runs only while there is a red-red conflict — z’s parent is red. A black parent means we are already legal.
• Line 9: find the uncle (the parent’s sibling). Its color is the entire decision.
• Lines 10–14: Case 1 — red uncle. Recolor parent and uncle black, grandparent red, then move z up to the grandparent and loop again — the conflict may have shifted upward.
• Lines 16–18: Case 2 — black uncle. A rotation physically rebalances, a recolor restores invariant 4, and we are done (break).
• Line 19: whatever happened, the root is always repainted black to satisfy invariant 2.

Complexity

The recolor case can ripple all the way to the root, doing O(log n) color flips — but recoloring is cheap and rotations are limited to at most two per insert. So every operation stays O(log n), which is what makes red-black trees the backbone of ordered maps and sets in standard libraries.

When to use / pitfalls

Practice