47.04.02 · theoretical-cs / algorithms-analysis

Self-Balancing Trees: Red-Black Trees

shipped3 tiersLean: none

Anchor (Master): Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 13; Sedgewick & Wayne 2011 Algorithms 4e (Addison-Wesley) §3.3 (left-leaning red-black trees, relationship to 2-3 and 2-3-4 trees)

Intuition Beginner

A binary search tree (BST) is like a sorted filing cabinet organised as a tree. For any node, everything in the left subtree is smaller and everything in the right subtree is larger. Finding an item is fast if the tree is balanced — roughly the same depth on both sides.

The problem is that inserting items in sorted order produces a degenerate tree: a linked list. Finding an item then takes linear time instead of logarithmic time.

A red-black tree fixes this by adding a colour (red or black) to each node and enforcing rules that prevent the tree from becoming too unbalanced. The rules ensure that no path from the root to a leaf is more than twice as long as any other such path. This guarantees that search, insertion, and deletion all run in logarithmic time.

The key insight is that the colour rules create a "soft balance" — not perfect balance, but close enough. Perfect balance is too expensive to maintain on every update. Red-black trees achieve a practical compromise: the balance constraint is weak enough to be restored cheaply after an update, but strong enough to guarantee logarithmic height.

Visual Beginner

A red-black tree storing the values {1, 3, 5, 7, 10, 15, 20}. Red nodes are shown in parentheses, black nodes in brackets:

              [7]
            /     \
          (3)      [15]
         /   \    /    \
       [1]   [5] (10)  [20]

Properties verified: the root (7) is black. Every red node has black children. Every path from root to leaf has the same number of black nodes (black-height = 2 for all leaves).

Operation	BST (unbalanced)	Red-black tree
Search 5	Could be O(n) if degenerate	O(log n) guaranteed
Insert 12	Could create degenerate path	O(log n) + rebalance
Delete 3	Could create degenerate path	O(log n) + rebalance
Height	Up to n	At most 2 log(n+1)

Worked example Beginner

We insert the values 5, 3, 7, 1, 10 into an initially empty red-black tree, showing the tree after each insertion.

Insert 5. The tree is empty, so 5 becomes the root. Colour it black (rule: root must be black).

[5]

Insert 3. 3 < 5, so it goes left. Colour it red.

    [5]
   /
 (3)

No violations. Red node 3 has no red children.

Insert 7. 7 > 5, so it goes right. Colour it red.

    [5]
   /   \
 (3)   (7)

No violations. Both children of the black root 5 are red.

Insert 1. 1 < 3, so it goes left of 3. Colour it red.

      [5]
     /   \
   (3)   (7)
   /
 (1)

Violation: red node 3 has a red child 1. Fix: recolour. The parent (3) and its sibling (7) are both red. Recolour 3 and 7 to black, and recolour 5 to red. But 5 is the root, so recolour it back to black.

      [5]
     /   \
   [3]   [7]
   /
 (1)

Insert 10. 10 > 7, so it goes right of 7. Colour it red.

      [5]
     /   \
   [3]   [7]
   /       \
 (1)       (10)

No violations. Red node 10 has a black parent.

The tree is balanced: height 3 for 5 nodes. A degenerate BST would have height 5.

Check your understanding Beginner

Formal definition Intermediate+

Definition (red-black tree). A red-black tree is a binary search tree where each node has an extra attribute: a colour, either red or black. The tree satisfies the following five properties:

Every node is either red or black.
The root node is black.
Every leaf (NIL) node is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Property 5 is the "balance" property. It constrains the structure by ensuring that no path is "too short" relative to others.

Definition (black-height). The black-height of a node $x$ , denoted $bh (x)$ , is the number of black nodes on any path from $x$ (not including $x$ itself) to a leaf. By property 5, this is well-defined (all paths give the same count).

Definition (rotation). A left rotation at node $x$ (with right child $y$ ) restructures the tree: $y$ takes $x$ 's place, $x$ becomes the left child of $y$ , and $y$ 's left subtree becomes $x$ 's right subtree. A right rotation is the mirror image.

LEFT-ROTATE (T, x) : y \leftarrow x . r i g h t; x . r i g h t \leftarrow y . l e f t; y . l e f t \leftarrow x

Rotations preserve the BST ordering property but may change the balance. The red-black fix-up procedures use rotations combined with recolouring to restore the five properties after an insertion or deletion.

Lemma (height bound). A red-black tree with $n$ internal nodes has height at most $2 l g (n + 1)$ .

Proof. Let $h$ be the height and $bh$ be the black-height of the root. By property 4, at least half the nodes on any root-to-leaf path are black (every red node is followed by a black one). So $h \leq 2 bh$ . A subtree rooted at any node $x$ with black-height $bh (x)$ has at least $2^{bh (x)} - 1$ internal nodes (by induction on $bh$ ). The entire tree has black-height $bh$ , so $n \geq 2^{bh} - 1$ , giving $bh \leq l g (n + 1)$ . Therefore $h \leq 2 l g (n + 1)$ . $□$

Counterexamples to common slips

"Red-black trees are perfectly balanced." They are approximately balanced. The height is at most $2 l g (n + 1)$ , which is at most twice the height of a perfectly balanced tree ( $l g n$ ). This factor of 2 is the price of cheap updates.
"AVL trees and red-black trees are the same." AVL trees maintain a stricter balance condition (height difference at most 1) and thus have slightly better search performance but more expensive insertions and deletions. Red-black trees do fewer rotations on average.
"The colour of a node represents a mathematical property." The colour is a bookkeeping device that encodes the balance invariant. It has no intrinsic meaning beyond its role in the five properties.

Key theorem with proof Intermediate+

Theorem (RB-INSERT correctness). Inserting a node into a red-black tree with $n$ nodes takes $O (l g n)$ time and produces a valid red-black tree with $n + 1$ nodes.

Proof sketch. Insert the new node $z$ as in a standard BST, colour it red. If $z$ 's parent is black, the tree is valid. If $z$ 's parent is red, property 4 is violated. The fix-up procedure (RB-INSERT-FIXUP) handles three cases based on the colour of $z$ 's uncle:

Case 1 (uncle is red): Recolour parent and uncle to black, grandparent to red. Move $z$ up to the grandparent and repeat. This takes $O (l g n)$ iterations at most because $z$ moves up two levels each time.

Case 2 (uncle is black, $z$ is a right child): Left-rotate at parent to convert to Case 3.

Case 3 (uncle is black, $z$ is a left child): Right-rotate at grandparent and recolour. This terminates because the new parent is black.

Each case performs at most 2 rotations and $O (1)$ recolourings. Total time: $O (l g n)$ . The loop invariant is that $z$ is red and either $z$ is the root or $z$ 's parent is red, and the rest of the tree satisfies all properties. When the loop terminates, the root is recoloured black. $□$

Bridge. Red-black trees are the foundational reason dictionary operations can be performed in $O (lo g n)$ worst-case time: the colour invariant guarantees approximate balance, and rotations restore it cheaply. This builds toward the use of balanced trees in graph algorithms like Dijkstra's shortest path, where a priority queue with $O (lo g n)$ operations is needed, and it appears again in B-trees used by databases, which generalise the balance idea to multi-way trees. The central insight is that the five red-black properties encode a balance constraint that is weak enough to be maintained in $O (lo g n)$ time per update but strong enough to guarantee logarithmic height — this is exactly the trade-off that makes self-balancing trees practical. Putting these together with the amortized analysis framework of 47.04.01 yields a complete picture of balanced-search-tree performance.

Exercises Intermediate+

Exercise 1 (easy, symbolic).

Show the red-black tree after inserting 8, 4, 12, 2, 6 into an initially empty tree. Mark each node's colour.

Answer

Insert 8: root [8] (black). Insert 4: [8] with left child (4) (red). Insert 12: [8] with left (4) and right (12), both red. No fix needed. Insert 2: 2 goes left of 4, coloured red. Parent (4) is red. Uncle (12) is red. Case 1: recolour 4 and 12 to black, 8 to red. Root: recolour to black. Tree: [8] with left [4] (black, left child (2) red) and right [12] (black). Insert 6: 6 goes right of 4, coloured red. Parent [4] is black. No fix needed.

        [8]
       /   \
     [4]   [12]
     / \
   (2) (6)

Exercise 3 (medium, symbolic).

Prove that a red-black tree with $n$ internal nodes has height at most $2 l g (n + 1)$ .

Hint

Show that a subtree rooted at a node with black-height $bh$ has at least $2^{bh} - 1$ internal nodes. Then relate height to black-height.

Answer

Lemma: a subtree rooted at any node $x$ with black-height $bh (x)$ contains at least $2^{bh (x)} - 1$ internal nodes. Proof by induction on $bh (x)$ . Base: $bh (x) = 0$ means $x$ is a leaf, 0 internal nodes. Step: each child of $x$ has black-height at least $bh (x) - 1$ (if the child is red, it has the same black-height as $x$ ; if black, it has $bh (x) - 1$ ). By induction, each child's subtree has at least $2^{bh (x) - 1} - 1$ nodes. Total: $2 (2^{bh (x) - 1} - 1) + 1 = 2^{bh (x)} - 1$ .

Now for the root: $n \geq 2^{bh} - 1$ where $bh$ is the root's black-height. So $bh \leq l g (n + 1)$ . By property 4, every other node on a path is black (no two reds adjacent), so $h \leq 2 bh \leq 2 l g (n + 1)$ . Rubric: full credit for both parts of the proof.

Exercise 4 (medium, symbolic).

Show the effect of a left rotation at node $x$ in the following tree. Verify that the BST ordering is preserved.

    x
   / \
  a   y
     / \
    b   c

Answer

After left rotation at $x$ : $y$ takes $x$ 's place, $x$ becomes $y$ 's left child, $b$ becomes $x$ 's right child.

      y
     / \
    x   c
   / \
  a   b

BST ordering: $a < x < b < y < c$ . Before rotation: $a < x$ (left child), $x < y$ (right child), $b < y$ and $y < c$ . After rotation: $a < x$ and $x < b$ (left subtree of $y$ ), $x < y$ and $y < c$ (right subtree of $y$ ). All ordering constraints preserved.

Exercise 6 (hard, symbolic).

Construct a red-black tree of height 4 with the minimum number of nodes. Show the tree structure and verify the height bound is tight.

Hint

To maximise height for a given number of nodes, alternate red and black nodes on the longest path and make all other paths as short as possible.

Answer

The height bound $h \leq 2 bh$ is tight when the longest path alternates red and black. For height 4 ( $h = 4$ , so $bh = 2$ ), the minimum number of nodes is $2^{bh} - 1 = 3$ for each subtree of the root, but we need to maximise height. A tree with height 4 and $bh = 2$ : root is black, left child is red, its left child is black (leaf at depth 2, with 2 NIL leaves). Right child is red, its right child is black, its right child is red, its right child is a black leaf. The tree has 4 internal nodes on the longest path and satisfies $h = 2 bh = 4$ . Minimum total nodes: the root's left subtree contributes $2^{2} - 1 = 3$ nodes at minimum, and the right path contributes 3 more. Total minimum around 7 nodes for height 4.

More precisely: the minimum node count for height $2 k$ is obtained by having the longest path alternate red-black with exactly $k$ black nodes, and every other path being as short as possible. The minimum count is achieved by a tree with one long path and minimal branching. Rubric: full credit for a valid construction and the bound tightness argument.

Exercise 7 (hard, short answer).

Prove that RB-DELETE takes $O (l g n)$ time and restores all red-black properties.

Answer

RB-DELETE first performs a standard BST deletion. If the deleted node had at most one child, splice it out. If it had two children, replace it with its successor and delete the successor. If the removed node was black, removing it may violate properties 4 and 5. The fix-up procedure RB-DELETE-FIXUP handles the case where a black node was removed, creating a "doubly black" situation. The fix-up has four cases (mirrored for left/right), each performing at most 3 rotations and constant recolourings. The argument mirrors the insertion fix-up: each iteration either resolves the violation or moves it closer to the root, and the loop executes at most $O (l g n)$ times. After the loop, the root is recoloured black. Total time: $O (l g n)$ .

Exercise 9 (hard, symbolic).

A left-leaning red-black tree (LLRB) is a variant where red links lean left (no right-leaning red links). Prove that every LLRB is a valid red-black tree, and that every red-black tree can be converted to an LLRB.

Answer

Every LLRB satisfies the five red-black properties because the additional constraint (no right-leaning red links) is a stricter version of property 4. Properties 1-3 and 5 are unchanged. Property 4 (red children of red nodes are forbidden) holds in LLRB as in standard red-black trees. The extra constraint reduces the number of cases during insertion and deletion.

For the converse: given a standard red-black tree, any right-leaning red link can be converted to left-leaning by a left rotation at the parent (if the red link goes right, rotate left). This preserves all red-black properties because rotations preserve BST order and black-height. Repeating this process bottom-up eliminates all right-leaning red links. Rubric: full credit for both directions.

Lean formalization Intermediate+

Mathlib has Data.Tree with basic binary tree definitions and Data.Tree.Balance with some balance-related lemmas, but no red-black tree implementation. The foundational gap is the absence of a RBTree α structure with colour annotations at each node, a predicate encoding the five red-black properties, and proofs that insertion and deletion preserve these properties. The rotation operations and their correctness (preserving BST ordering) are also absent. A formalisation would require defining RBNode α := leaf | node (colour) (left : RBNode α) (val : α) (right : RBNode α) and proving height t ≤ 2 * log2 (size t + 1). This unit ships without a lean_module.

Advanced results Master

Three results extend the basic theory of red-black trees.

Theorem 1 (equivalence with 2-3-4 trees). Red-black trees are isomorphic to 2-3-4 trees (B-trees of order 4). A black node with red children corresponds to a 3-node or 4-node in the 2-3-4 tree. This isomorphism explains why the red-black properties work: the 2-3-4 tree is perfectly balanced in terms of height, and the red-black tree inherits this balance through the correspondence ^{[CLRS Ch. 13]}.

The mapping: a black node with two black children is a 2-node. A black node with one red child is a 3-node (the red child is absorbed). A black node with two red children is a 4-node (both absorbed). Rotations in the red-black tree correspond to splits and merges in the 2-3-4 tree.

Theorem 2 (Sedgewick's left-leaning red-black trees). The LLRB variant restricts all red links to lean left, reducing the number of cases in insertion and deletion from 6 to 3. LLRB trees have the same asymptotic bounds but are simpler to implement.

The key insight is that right-leaning red links are redundant: any right-leaning red link can be converted to a left-leaning one by a rotation. By enforcing left-leaning as an invariant, the implementation avoids half the cases.

Theorem 3 (parallel deletion). The number of structural modifications (rotations) during deletion is at most 3, and the number of colour changes is at most $O (l g n)$ . In practice, deletions perform very few rotations on average — empirical studies show the average is close to 0.3 rotations per deletion.

Synthesis. Red-black trees are the foundational reason balanced search trees provide guaranteed $O (lo g n)$ performance for all dictionary operations: the colour encoding captures a balance invariant that is maintainable in logarithmic time. The central insight is that approximate balance (height at most $2 l g n$ ) is sufficient for logarithmic performance and cheap to maintain — this is exactly the trade-off that makes red-black trees the default balanced-tree implementation in standard libraries (Java's TreeMap, C++'s std

). This builds toward B-trees and their use in databases, where the same balance principles apply to disk-based storage. Putting these together with the amortized analysis of 47.04.01 yields a unified performance model for balanced search trees: worst-case $O (lo g n)$ per operation, which is stronger than the amortized bounds of some competing structures.

Full proof set Master

Proposition 1 (height bound). A red-black tree with $n$ internal nodes has height $h \leq 2 l g (n + 1)$ .

Proof. We first prove that a subtree rooted at node $x$ with black-height $bh (x)$ has at least $2^{bh (x)} - 1$ internal nodes, by induction on $bh (x)$ .

Base: $bh (x) = 0$ . Then $x$ must be a NIL leaf (no internal nodes below it). $2^{0} - 1 = 0$ . Holds.

Inductive step: $bh (x) = k > 0$ . Each child of $x$ has black-height at least $k - 1$ (if the child is red, its black-height equals $k$ ; if black, its black-height is $k - 1$ ). Wait — if the child is red, $bh (child) = k$ (same black-height as $x$ , since red nodes don't count). If the child is black, $bh (child) = k - 1$ . So $bh (child) \geq k - 1$ in either case. By the induction hypothesis, each child's subtree has at least $2^{k - 1} - 1$ internal nodes. Total for $x$ 's subtree: at least $2 (2^{k - 1} - 1) + 1 = 2^{k} - 1$ .

Now for the root: $n \geq 2^{bh (root)} - 1$ , so $bh (root) \leq l g (n + 1)$ . By property 4, no two red nodes are adjacent, so on any path, at least half the nodes are black: $h \leq 2 \cdot bh (root) \leq 2 l g (n + 1)$ . $□$

Proposition 2 (rotations preserve BST property). Left rotation at node $x$ preserves the binary search tree ordering.

Proof. Let $x$ be the rotation point with right child $y$ , $y$ 's left subtree $B$ . Before rotation: keys in $A < x < keys in B < y < keys in C$ . After rotation: $y$ takes $x$ 's position, $x$ becomes $y$ 's left child, $B$ becomes $x$ 's right child. New ordering: $A < x < B < y < C$ . All inequalities are preserved. $□$

Proposition 3 (insertion terminates). RB-INSERT-FIXUP terminates after at most $O (l g n)$ iterations.

Proof. Each iteration of the fix-up loop either: (Case 1) moves $z$ up two levels (to its grandparent), which reduces the remaining path to the root, or (Cases 2-3) performs at most 2 rotations and terminates. Since the tree has height $O (l g n)$ , Case 1 can occur at most $O (l g n)$ times. The total number of iterations is $O (l g n)$ . $□$

Connections Master

47.04.01 — Amortized analysis provides the framework for evaluating sequences of red-black tree operations; each operation is $O (lo g n)$ worst-case, which is a stronger guarantee than amortized bounds.
47.04.03 — Network flow algorithms use priority queues and dictionaries that are often implemented with balanced search trees.
50.03.01 — Big-O analysis is used throughout to bound the height and operation costs of red-black trees.

Historical & philosophical context Master

Red-black trees were invented by Rudolf Bayer in 1972 under the name "symmetric binary B-trees," recognising their isomorphism with 2-3-4 trees. The modern formulation with red and black colours is due to Leo Guibas and Robert Sedgewick (1978), who simplified the presentation and analysis ^{[CLRS Ch. 13 notes]}.

The philosophical point is that red-black trees embody a principle common in algorithm design: maintaining a weaker invariant (approximate balance) that is cheap to restore, rather than a stronger one (perfect balance) that is expensive. This trade-off between invariant strength and maintenance cost is the same principle behind B-trees in databases, splay trees in memory caches, and even skip lists. The $O (lo g n)$ guarantee comes not from perfect balance but from the controlled imbalance enforced by the five properties.

Sedgewick's left-leaning variant (2008) further simplified the implementation by reducing the number of cases, demonstrating that the same asymptotic guarantees can be achieved with less code — a principle valued in practical software engineering ^{[Sedgewick & Wayne §3.3]}.

Bibliography Master

@book{clrs2022,
  author    = {Cormen, Thomas H. and Leiserson, Ronald L. and Rivest, Clifford and Stein, Christopher},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@book{sedgewick2011,
  author    = {Sedgewick, Robert and Wayne, Kevin},
  title     = {Algorithms},
  edition   = {4th},
  publisher = {Addison-Wesley},
  year      = {2011},
}
@article{guibas1978dichromatic,
  author  = {Guibas, Leo J. and Sedgewick, Robert},
  title   = {A Dichromatic Framework for Balanced Trees},
  journal = {Proceedings of the 19th Annual Symposium on Foundations of Computer Science},
  pages   = {8--21},
  year    = {1978},
}

Prerequisites

47.04.01

Tier anchors

beginner: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 12-13 (binary search trees and red-black trees as balanced BSTs guaranteeing O(log n) operations)
intermediate: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 13 (red-black tree definition, rotation operations, insertion and deletion with fix-up, proof that height is O(log n))
master: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 13; Sedgewick & Wayne 2011 Algorithms 4e (Addison-Wesley) §3.3 (left-leaning red-black trees, relationship to 2-3 and 2-3-4 trees)

References

Cormen, T. H., Leiserson, R. L., Rivest, C. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Chapter 13 defines a red-black tree as a binary search tree where each node stores one extra bit (colour: red or black) satisfying five properties: (1) every node is either red or black, (2) the root is black, (3) every leaf (NIL) is black, (4) if a node is red then both its children are black, (5) for each node, all simple paths from the node to descendant leaves contain the same number of black nodes; the black-height $bh (x)$ of a node $x$ is the number of black nodes on any path from $x$ to a leaf (not counting $x$ itself); Lemma 13.1 proves that a red-black tree with $n$ internal nodes has height at most $2 l g (n + 1)$ ; insertion and deletion use rotations (left and right) and colour flips to restore the red-black properties in $O (l g n)$ time.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m