Red-Black Tree, in depth: invariants, the height proof, insertion and deletion case by case, and how to test them

Why balance matters

Search cost in a BST is the depth of the node, and depth depends on insertion order. Real workloads are rarely random: timestamps, auto-increment ids and sorted imports arrive in order. A balanced tree removes the dependency on luck by maintaining a structural invariant that forces logarithmic height, and by restoring it in O(log n) time after every change.

Among balanced trees, the red-black tree's niche is a cheap, deterministic worst case with very little restructuring per update, which is why standard libraries and kernels pick it for in-memory ordered maps. The alternatives are compared near the end.

Five invariants and the height bound

Treat every missing child as a real leaf node called nil, coloured black. Then a red-black tree is a BST that satisfies five rules:

1. Every node is red or black.
2. The root is black.
3. Every nil leaf is black.
4. A red node has two black children, so two reds are never adjacent on a path.
5. Every path from a node down to its nil leaves contains the same number of black nodes. That number, not counting the node itself, is the node's black-height.

Why do these bound the height? A subtree whose root has black-height bh contains at least 2^bh - 1 internal nodes; a short induction proves it, because each child has black-height at least bh - 1. Rule 4 means at least half the nodes on any root-to-leaf path are black, so the black-height of the root is at least h/2. Combining the two, n is at least 2^h/2 - 1, which rearranges to h at most 2 log₂(n + 1). For a million keys that is a height of at most 39.9; the measured tree built from a million sequential keys has height 37.

A useful mental model: collapse every red node into its black parent and you get a 2-3-4 tree, a B-tree of order 4 with all leaves at the same depth. The fix-up cases below are that tree's node splits and merges in binary form.

Rotations

All rebalancing uses two primitives: recolouring and rotation. A rotation pivots a parent and child around the edge between them. It preserves in-order order, touches a constant number of pointers, and changes the depth of the subtrees involved by one level in opposite directions. The code uses one shared black sentinel for nil, which removes most null checks.

RED, BLACK = True, False

class Node:
    __slots__ = ("key", "color", "left", "right", "parent")
    def __init__(self, key, color, nil):
        self.key, self.color = key, color
        self.left = self.right = self.parent = nil

class RBTree:
    def __init__(self):
        self.nil = Node(None, BLACK, None)   # one shared black sentinel leaf
        self.root = self.nil

    def _rotate_left(self, x):
        y = x.right
        x.right = y.left
        if y.left is not self.nil:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is self.nil:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left, x.parent = x, y
    # _rotate_right is the mirror image: swap every left and right.

Insertion: three cases

Insert the key exactly as in a plain BST and colour the new node red. Colouring it red keeps rule 5 intact, because no path gained a black node; the only rule that can break is rule 4, if the new node's parent is also red (or rule 2, for a new root). The repair loop looks at the uncle, the parent's sibling:

• Case 1, red uncle. Colour the parent and uncle black and the grandparent red. Black-heights are unchanged, but the grandparent may now clash with its own red parent, so the loop continues two levels up.
• Case 2, black uncle, zig-zag. If the new node is an inner grandchild, rotate at the parent to turn it into an outer grandchild, then fall through.
• Case 3, black uncle, straight line. Swap colours of parent and grandparent and rotate at the grandparent. The red-red pair is gone and the loop ends.

Cases 2 and 3 terminate immediately, so an insert performs at most two rotations. Case 1 can repeat up the tree, but it only recolours, and its amortised cost over a sequence of inserts is constant.

    def insert(self, key):
        z = self._bst_insert(Node(key, RED, self.nil))   # BST descent as in a plain BST; node is red
        if z is not None:                                # None means a duplicate key
            self._insert_fixup(z)

    def _insert_fixup(self, z):
        while z.parent.color == RED:          # the only possible violation: red-red
            g = z.parent.parent               # exists: a red parent is never the root
            if z.parent is g.left:
                uncle = g.right
                if uncle.color == RED:        # case 1: recolour and move the problem up
                    z.parent.color = uncle.color = BLACK
                    g.color = RED
                    z = g
                else:
                    if z is z.parent.right:   # case 2: turn the zig-zag into a line
                        z = z.parent
                        self._rotate_left(z)
                    z.parent.color = BLACK    # case 3: one rotation at the grandparent
                    g.color = RED
                    self._rotate_right(g)
            else:
                ...                           # mirror image with left and right swapped
        self.root.color = BLACK

Worked example

Insert 10, 20, 30, 15, 25, 5 and 1 into an empty tree. The trace below is the output of the article's code, with R and B for colour and a dot for an empty child:

insert 10: rotations+0  10B
insert 20: rotations+0  10B(. 20R)
insert 30: rotations+1  20B(10R 30R)
insert 15: rotations+0  20B(10B(. 15R) 30B)
insert 25: rotations+0  20B(10B(. 15R) 30B(25R .))
insert  5: rotations+0  20B(10B(5R 15R) 30B(25R .))
insert  1: rotations+0  20B(10R(5B(1R .) 15B) 30B(25R .))
delete 20: rotations+0  25B(10R(5B(1R .) 15B) 30B)
delete 10: rotations+1  25B(5R(1B 15B) 30B)

Inserting 30 creates a straight red line 10, 20, 30 with no uncle, so case 3 rotates left at 10 and 20 becomes the root. Inserting 15 finds a red parent (10) and a red uncle (30): case 1 recolours both black and the root red, and the final line restores the root to black. Inserting 1 triggers case 1 again at 5 and 15, which turns 10 red; its parent 20 is black, so the loop stops. Deleting 20 swaps in its red successor 25 with no repair; deleting 10 costs one rotation.

Deletion and the extra black

Deletion is the hard half. First do a standard BST delete: a node with two children is replaced by its in-order successor, so the node physically removed always has at most one child. If the removed node was red, no rule can break. If it was black, every path through its old position is now one black short. The child x that moved into its place is said to carry an extra black, and the fix-up loop pushes that extra black upward or absorbs it, looking at x's sibling w:

• Case 1, red sibling. Rotate and recolour so the sibling is black, reducing to another case.
• Case 2, black sibling with two black children. Colour the sibling red and move the extra black up to the parent; a red parent simply turns black and the loop ends.
• Case 3, black sibling, near child red, far child black. Rotate at the sibling so the red child is on the far side, then fall into case 4.
• Case 4, black sibling with a red far child. Rotate at the parent and recolour; the extra black is absorbed and the loop ends.

Only case 2 can repeat, and it rotates nothing, so a delete performs at most three rotations. The fix-up is the part that needs care:

    def _delete_fixup(self, x):               # x carries an "extra black"
        while x is not self.root and x.color == BLACK:
            if x is x.parent.left:
                w = x.parent.right            # sibling; never the sentinel here
                if w.color == RED:            # case 1: make the sibling black
                    w.color, x.parent.color = BLACK, RED
                    self._rotate_left(x.parent)
                    w = x.parent.right
                if w.left.color == BLACK and w.right.color == BLACK:
                    w.color = RED             # case 2: push the extra black up
                    x = x.parent
                else:
                    if w.right.color == BLACK:    # case 3: far nephew must be red
                        w.left.color, w.color = BLACK, RED
                        self._rotate_right(w)
                        w = x.parent.right
                    w.color = x.parent.color      # case 4: rotate, absorb, finish
                    x.parent.color = w.right.color = BLACK
                    self._rotate_left(x.parent)
                    x = self.root
            else:
                ...                           # mirror image
        x.color = BLACK

Testing an implementation

Red-black bugs rarely crash: a wrong colour in a mirror case leaves a correct but unbalanced BST, so example-based tests pass while the guarantee is gone. Test invariants, not outputs. Write a validator that checks BST order, the red-red rule and equal black-heights, then run thousands of random inserts and deletes against a reference set and validate after every single operation:

def check(t):
    """Return black nodes per path, counting the node and the nil leaf; raise on any broken invariant."""
    assert t.root.color == BLACK and t.nil.color == BLACK
    def walk(n, lo, hi):
        if n is t.nil:
            return 1
        assert (lo is None or n.key > lo) and (hi is None or n.key < hi), "BST order"
        if n.color == RED:
            assert n.left.color == BLACK and n.right.color == BLACK, "red-red"
        bl, br = walk(n.left, lo, n.key), walk(n.right, n.key, hi)
        assert bl == br, "black-height mismatch"
        return bl + (n.color == BLACK)
    return walk(t.root, None, None)

A loop of 200 trials of 400 random inserts and deletes over keys 0 to 299, checking membership against a Python set and validating after every operation, passed for this code. Also test the adversarial shapes: sequential keys in both directions, deleting the root repeatedly, and deleting until empty. For sequential inserts the measured heights were 17 for 1,000 keys and 37 for 1,000,000, under the bounds of 19.9 and 39.9. If you implement a mirror case by copy and paste, deliberately break one assignment and confirm the validator fails; a validator that never fails proves nothing.

Red-black trees in production and the alternatives

You probably already use red-black trees. Java's TreeMap and TreeSet are red-black trees, and since Java 8 a HashMap bin that grows past 8 entries (once the table has at least 64 buckets; smaller tables resize instead) becomes a red-black tree of TreeNode objects, which bounds hash-flooding damage at O(log n) per bin when keys are Comparable, as String is. The common C++ standard library implementations build std::map and std::set on red-black trees. The Linux kernel ships an intrusive rbtree, with node fields embedded in the caller's struct, used by schedulers, memory management and timers.

The weakness of every binary tree is memory layout: each level is a dependent pointer load and a likely cache miss, so for large in-memory sets a B-tree with wide nodes often beats a red-black tree by a wide margin despite more comparisons. Augmentation is the strength: a subtree size per node gives the k-th smallest key in O(log n), if rotations maintain it.

Failure modes

• Inconsistent comparators. A comparator that is not a strict total order silently corrupts search paths.
• Mutating keys in place. Changing a field that the comparator reads while the object sits in the tree strands it at the wrong position; remove, modify, reinsert.
• Mirror-case typos. The commonest implementation bug; only an invariant checker run after every operation finds it.
• Forgetting parent pointers in rotations. A rotation changes six pointers; missing one corrupts later fix-ups far from the bug.
• Unsynchronised concurrent access. A half-finished rotation exposes a broken tree; lock, or use a concurrent skip list.
• Augmented fields not updated. Subtree sizes or interval maxima must be recomputed bottom-up inside each rotation and along the update path.

What to do next

1. Implement insert from the rules above without looking at the code, then run the validator loop against it.
2. Add deletion, and break one mirror-case assignment on purpose to prove the validator catches it.
3. Augment each node with a subtree size and implement select(k) and rank(key), updating sizes inside rotations.
4. Benchmark your tree against a sorted array with binary search and against a skip list for 10⁶ keys, and note where cache misses dominate.
5. Compare with treaps and revisit plain BST operations to see exactly what balancing buys.
6. Read how interval trees reuse the same rotations, and how B-trees and LSM trees solve ordered storage on disk.