Red-black trees

What this chapter covers

The red-black tree is the balanced search tree you're actually using, usually without knowing it — it's what sits inside std::map, Java's TreeMap, and the Linux kernel's scheduler. Like the AVL tree it guarantees O(log n), but it enforces balance a cleverer way: it paints each node red or black and obeys four coloring rules that, together, keep the longest root-to-leaf path at most twice the shortest. That looser guarantee means it rebalances less often than an AVL tree, which is exactly why libraries prefer it for general-purpose ordered maps. This chapter builds insertion using Chris Okasaki's famously compact functional formulation — one balance function, four symmetric cases — and shows why "red-black" and "balanced" mean the same thing.

A bit of history

The red-black tree grew out of an insight by Rudolf Bayer, who in 1972 described "symmetric binary B-trees" — a way to represent a B-tree (the database structure of a later chapter) as a binary tree. In 1978 Leo Guibas and Robert Sedgewick reformulated Bayer's idea with the red/black coloring and the four rules we use today, and the name stuck. The choice of colors was, by Guibas and Sedgewick's own later account, partly because a two-color laser printer they had could render red and black nicely. In 1999 Chris Okasaki published the functional insertion this chapter uses, collapsing the notoriously fiddly case analysis into a single elegant balance function — a small masterpiece that made red-black trees teachable. The structure's real triumph, though, is adoption: it became the ordered-map implementation of choice across the software world, the balanced tree that quietly runs underneath enormous amounts of code.

The intuition

Think of the colors as a balance budget. The rules — root black, no two reds in a row, and every root-to-leaf path crossing the same number of black nodes — have a combined consequence: because black-heights are all equal and reds can't stack, the longest path (which alternates red and black) can be at most twice the shortest (all black). Twice is enough to keep the height O(log n), and looser than AVL's "differ by at most one," which is the whole point — a looser rule is violated less often, so you repair less often.

Insertion works by adding the new node red. Why red? Because a red node has the same black-height as no node at all, so inserting one can never break rule 4 (equal black-heights) — it can only break rule 3 (no two reds in a row), if the new red node's parent is also red. Fixing that red-red violation is the job of the balance function, and here's Okasaki's insight: in every one of the four ways a red-red violation can be arranged, the repair is the same — rewrite the little cluster into a red grandparent with two black children. That single rewrite pushes the redness up one level, where it might create a new red-red violation with its parent, which the next balance up handles, and so on until the root, which is simply forced black at the end. One rule, applied on the way back up, balances the whole tree.

Complexity: how it scales

The four rules bound the height at $2\log_2(n+1)$, so every operation is $O(\log n)$ guaranteed — search, insert, delete — for any input, exactly like AVL. What differs is the constant on updates: a red-black insert does at most two rotations (and some recoloring), where AVL may do a rotation at every level; empirically red-black trees rotate noticeably less. The trade shows in height. Against the unbalanced BST on sorted input, the red-black tree stays flat where the plain one goes quadratic:

And the height stays comfortably under its bound — but is a touch taller than an AVL tree would be, which is the looser balance made visible:

At 8000 sorted insertions the red-black tree built in 32 ms against the plain BST's 2179 ms — 68× faster. And at 100000 nodes its height was 22, under the bound of 33 and only a little above the AVL tree's 17 from last chapter. That five-level difference is the price of rebalancing less often, and for most workloads it's a price worth paying.

What it's good at, what it isn't

The red-black tree is the right default for an ordered map or set. It gives all the ordered-query power — sorted iteration, ranges, min, max, successor — with guaranteed O(log n), and it handles inserts and deletes cheaply because its loose balance rule fires rarely. That balance of guarantees and low update cost is why it, not the AVL tree, is the standard-library choice almost everywhere. If you reach for a TreeMap, a std::set, or an ordered dictionary in a systems language, you're using one.

Where it isn't ideal is the same place any balanced BST isn't: for pure membership with no ordered queries, a hash table's O(1) beats it; and for read-heavy workloads where lookups vastly outnumber updates, an AVL tree's tighter balance (shorter tree) can edge it out. Delete is also genuinely intricate — more so than insert — which is one reason the functional formulation here focuses on insertion. But as a general-purpose ordered container, the red-black tree is the pragmatic winner, and its ubiquity is the proof.

The data, or the inputs

Both charts feed sorted input, the worst case for a plain BST and the clearest proof that red-black balancing works. The animation inserts 1 through 7 in sorted order and colors each node by its rule, so you can watch the red and black nodes rearrange to keep the tree short.

Build it, one function at a time

The heart of it is Okasaki's balance — the one function that repairs all four red-red configurations into the same balanced, recolored shape:

def _balance(color, value, left, right):
    """Okasaki's balance. Whenever a BLACK node has a red child that itself has a red
    child — a red-red violation, in any of four configurations — rewrite that little
    three-node cluster into a red parent with two black children. The same rebalanced
    shape results from all four cases; only which node ends up on top differs. This one
    rule, applied on the way back up, is the entire rebalancing logic."""
    if color == BLACK:
        if _red(left) and _red(left.left):          # left-left
            return Node(RED, left.value,
                        Node(BLACK, left.left.value, left.left.left, left.left.right),
                        Node(BLACK, value, left.right, right))
        if _red(left) and _red(left.right):         # left-right
            return Node(RED, left.right.value,
                        Node(BLACK, left.value, left.left, left.right.left),
                        Node(BLACK, value, left.right.right, right))
        if _red(right) and _red(right.left):        # right-left
            return Node(RED, right.left.value,
                        Node(BLACK, value, left, right.left.left),
                        Node(BLACK, right.value, right.left.right, right.right))
        if _red(right) and _red(right.right):       # right-right
            return Node(RED, right.value,
                        Node(BLACK, value, left, right.left),
                        Node(BLACK, right.right.value, right.right.left, right.right.right))
    return Node(color, value, left, right)

And insert is almost trivial on top of it: add the node red, balance on the way up, force the root black:

def insert(self, value):
    """Insert the new node RED (adding a red node can't change any black-height,
    so rule 4 stays intact), fix any red-red violation on the way back up with
    `balance`, and finally force the root black. That's the whole insert — the
    recoloring keeps the height within 2·log₂(n+1)."""
    inserted = [False]

    def ins(node):
        if node is None:
            inserted[0] = True
            return Node(RED, value, None, None)
        if value < node.value:
            return _balance(node.color, node.value, ins(node.left), node.right)
        if value > node.value:
            return _balance(node.color, node.value, node.left, ins(node.right))
        return node

    self.root = ins(self.root)
    self.root.color = BLACK
    if inserted[0]:
        self._n += 1

Watch it work

Here's a red-black tree built from the sorted sequence 1 through 7, with each node colored by the rules — red or black. Step through it and watch the colors do the balancing: new nodes arrive red, and when a red-red violation would form, the tree recolors and restructures to push the redness upward and keep every path's black count equal. Notice there are never two red nodes in a row, the root is always black, and the tree never grows into the chain that a plain BST would build from this exact input. The colors are doing the same job AVL's balance factors did, just with a looser, cheaper rule:

The complete code

Both versions in one place — flip between them. The from-scratch tab is the red-black tree and Okasaki's balance. The library tab is the plain unbalanced BST — the baseline that degenerates on sorted input — because Python doesn't expose a red-black tree directly (the ordered maps in C++ and Java are red-black trees in C; in Python you'd use the third-party sortedcontainers).

"""The red-black tree — the balanced binary search tree that actually runs inside most
standard-library ordered maps. It guarantees O(log n) like the AVL tree, but enforces
balance with a looser rule based on node COLORS, so it rotates less on updates.

Every node is red or black, and four rules together keep the tree from getting more
than twice as tall as a perfectly balanced one:
  1. every node is red or black;
  2. the root is black;
  3. a red node's children are both black (no two reds in a row);
  4. every path from a node down to a leaf passes through the same number of black
     nodes (equal "black-height").

This chapter builds insertion using Chris Okasaki's beautifully compact functional
formulation: one `balance` function, four symmetric cases, and the red-red violation
bubbles up the tree until the root absorbs it.
"""

RED = "R"
BLACK = "B"


class Node:
    __slots__ = ("color", "value", "left", "right")

    def __init__(self, color, value, left=None, right=None):
        self.color = color
        self.value = value
        self.left = left
        self.right = right


def _red(node):
    return node is not None and node.color == RED


# region: balance
def _balance(color, value, left, right):
    """Okasaki's balance. Whenever a BLACK node has a red child that itself has a red
    child — a red-red violation, in any of four configurations — rewrite that little
    three-node cluster into a red parent with two black children. The same rebalanced
    shape results from all four cases; only which node ends up on top differs. This one
    rule, applied on the way back up, is the entire rebalancing logic."""
    if color == BLACK:
        if _red(left) and _red(left.left):          # left-left
            return Node(RED, left.value,
                        Node(BLACK, left.left.value, left.left.left, left.left.right),
                        Node(BLACK, value, left.right, right))
        if _red(left) and _red(left.right):         # left-right
            return Node(RED, left.right.value,
                        Node(BLACK, left.value, left.left, left.right.left),
                        Node(BLACK, value, left.right.right, right))
        if _red(right) and _red(right.left):        # right-left
            return Node(RED, right.left.value,
                        Node(BLACK, value, left, right.left.left),
                        Node(BLACK, right.value, right.left.right, right.right))
        if _red(right) and _red(right.right):       # right-right
            return Node(RED, right.value,
                        Node(BLACK, value, left, right.left),
                        Node(BLACK, right.right.value, right.right.left, right.right.right))
    return Node(color, value, left, right)
# endregion


class RedBlackTree:
    def __init__(self):
        self.root = None
        self._n = 0

    # region: insert
    def insert(self, value):
        """Insert the new node RED (adding a red node can't change any black-height,
        so rule 4 stays intact), fix any red-red violation on the way back up with
        `balance`, and finally force the root black. That's the whole insert — the
        recoloring keeps the height within 2·log₂(n+1)."""
        inserted = [False]

        def ins(node):
            if node is None:
                inserted[0] = True
                return Node(RED, value, None, None)
            if value < node.value:
                return _balance(node.color, node.value, ins(node.left), node.right)
            if value > node.value:
                return _balance(node.color, node.value, node.left, ins(node.right))
            return node

        self.root = ins(self.root)
        self.root.color = BLACK
        if inserted[0]:
            self._n += 1
    # endregion

    def __contains__(self, value):
        node = self.root
        while node is not None:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

    def __len__(self):
        return self._n

    def height(self):
        def h(node):
            return 0 if node is None else 1 + max(h(node.left), h(node.right))
        return h(self.root)

    def inorder(self):
        out = []

        def rec(node):
            if node is not None:
                rec(node.left)
                out.append(node.value)
                rec(node.right)

        rec(self.root)
        return out

"""Red-black trees are what real ordered maps use — but in Python they're behind the
C implementation, not exposed directly, so there's no stdlib red-black tree to call.
`dict`/`set` are hash tables (unordered); the third-party `sortedcontainers` is the
practical ordered structure. To show what the color rules buy, the baseline here is the
unbalanced BST from two chapters ago — the same insert without any balancing, which
degenerates on sorted input where the red-black tree stays O(log n).
"""


# region: plain_bst
class PlainBSTNode:
    __slots__ = ("value", "left", "right")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class PlainBST:
    """An unbalanced BST — the same ordering, no color rules, no rebalancing. On
    sorted input it becomes a linked list; the red-black tree's recoloring is what
    prevents exactly that."""

    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return PlainBSTNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node

    def height(self):
        def h(node):
            return 0 if node is None else 1 + max(h(node.left), h(node.right))
        return h(self.root)
# endregion

Scratch vs library

Like the AVL chapter, this face-off pits balanced against unbalanced rather than Python against C, and balance wins by 68× on sorted input at 8000 nodes, with the gap widening quadratically. The more interesting number is the comparison to the previous chapter: at 100000 sorted nodes, the red-black tree stood 22 levels tall to the AVL tree's 17. Both are O(log n), both are worlds better than the plain BST's 100000, but the red-black tree is deliberately a little taller because it rebalances less aggressively. That five-level difference is the entire AVL-versus-red-black trade in one measurement: AVL buys shorter trees and faster lookups by rotating more; red-black buys cheaper updates by tolerating a bit more height. The software industry, needing a general-purpose ordered map that handles reads and writes alike, overwhelmingly chose red-black — which is why it's the balanced tree you're most likely to be using right now.

Where you'll actually meet it

You are almost certainly running red-black trees right now. std::map and std::set in C++, TreeMap and TreeSet in Java, and ordered associative containers across many languages are red-black trees. The Linux kernel uses them pervasively — the completely fair scheduler orders runnable tasks in one, and virtual-memory areas are tracked in another. Any time software keeps keys ordered under frequent insertion and deletion — a priority index, an interval set, a symbol table that must iterate in order — a red-black tree is the likely engine. It's the most-deployed balanced search tree in existence.

Takeaways

A red-black tree balances a BST with node colors and four rules that bound its height at $2\log_2(n+1)$, guaranteeing $O(\log n)$ operations while rebalancing less often than an AVL tree — the trade that made it the standard-library ordered map. Okasaki's functional insertion reduces the whole rebalancing story to one balance function over four symmetric red-red cases, and the structure turns out to be a binary encoding of a 2-3-4 tree, tying it directly to the B-trees ahead.

That's the balanced-BST family: AVL for tight balance and fast lookups, red-black for cheap updates and ubiquity, both descendants of the plain BST plus a rule to keep it short. The next chapter steps sideways to a different kind of tree entirely. The binary heap gives up search-tree ordering for a weaker "parent beats child" rule, and in exchange makes one operation — always grab the maximum (or minimum) — as fast as possible. It's the priority queue, and you already met its array-as-tree trick back in heapsort.