Red-Black Tree

Red-black tree is a self-balancing binary search tree data structure within computation and algorithms that maintains dynamic ordered sets and associative maps in O(log n) worst-case time per search, insertion, and deletion. Whereas an ordinary unbalanced binary search tree degenerates into a linear chain of height Θ(n) when keys arrive in sorted order, a red-black tree attaches a single 1-bit color attribute—either red or black—to every node and enforces structural invariants that prevent any root-to-leaf path from exceeding twice the length of any other root-to-leaf path.

Introduced by Rudolf Bayer in 1972 as the symmetric binary B-tree and reformulated under the bichromatic "red-black" framework by Leo J. Guibas and Robert Sedgewick in 1978, the red-black tree establishes a direct structural isomorphism with a B-tree of order 4 (a 2–3–4 tree) within computational complexity theory. Because rebalancing after an insertion requires at most two pointer rotations and rebalancing after a deletion requires at most three pointer rotations (with O(1) amortized color flips and rotations per update), red-black trees serve as the standard ordered dictionary implementation across systems software, including the Linux kernel's CFS process scheduler and virtual memory manager, the C++ Standard Template Library (std::map and std::set), Java's TreeMap, and genomic interval-overlap trees for sequence alignment and coordinate indexing in bioinformatics.

Node Representation and the Five Color Properties

Each internal node x of a red-black tree stores a comparable key x.key, a color bit x.color ∈ {RED, BLACK}, a parent pointer x.p, and left and right child pointers x.left and x.right. All missing child links at the bottom of the tree point to a shared sentinel leaf node T.nil, which is permanently colored black.

In addition to the binary search tree ordering property (all keys in x.left are ≤ x.key and all keys in x.right are ≥ x.key), a red-black tree satisfies five color invariants:

1. Dichotomy Property: Every node is colored either red or black.
2. Root Property: The root node T.root is black.
3. External Sentinel Leaf Property: Every external sentinel leaf (T.nil) is black.
4. Red-Parent (No Double-Red) Property: If a node is red, then both of its children are black (no root-to-leaf path contains two consecutive red nodes).
5. Black-Height Property: For each node x, every simple downward path from x to any descendant sentinel leaf T.nil contains the same number of black nodes.

The number of black nodes on any simple path from node x down to a sentinel leaf—excluding x itself—is called the black-height of x, denoted bh(x). By Property 5, bh(x) is well-defined for every node.

Inductive Proof of the Height Bound h ≤ 2 log₂(n + 1)

The logarithmic worst-case performance of a red-black tree follows from two lemmas linking internal node count n, black-height bh(T), and height h:

• Lemma 1 (Subtree Size Bound): The subtree rooted at any node x contains at least 2^bh(x) − 1 = exp(bh(x) ln 2) − 1 internal nodes.

Proof by Induction: If x = T.nil, bh(x) = 0 and its subtree has 2⁰ − 1 = 0 internal nodes. For an internal node x, each child c has black-height bh(c) = bh(x) (if c is red) or bh(c) = bh(x) − 1 (if c is black); by the induction hypothesis, each child's subtree has at least 2^bh(x)−1 − 1 internal nodes, so x's subtree contains at least 2(2^bh(x)−1 − 1) + 1 = 2^bh(x) − 1 internal nodes.

• Lemma 2 (Height Upper Bound): A red-black tree with n internal nodes has height h ≤ 2 log₂(n + 1).

Proof: Along any root-to-leaf path of length h, Property 4 forbids consecutive red nodes, so at least ⌈h / 2⌉ nodes (excluding the root) are black, giving bh(T.root) ≥ h / 2. Applying Lemma 1 to the root yields n ≥ 2^bh(T.root) − 1 ≥ 2^h/2 − 1, so log₂(n + 1) ≥ h / 2, or h ≤ 2 log₂(n + 1).

Isomorphism with 2–3–4 B-Trees and Left-Leaning Red-Black Trees

Guibas and Sedgewick (1978) showed that every red-black tree is an isometric binary encoding of a 2–3–4 B-tree in which all leaves lie at the same depth:

• A 2-node (1 key, 2 children) corresponds to a single black node with two black children.
• A 3-node (2 keys, 3 children) corresponds to a black parent node with one red child (leaning left or right).
• A 4-node (3 keys, 4 children) corresponds to a black parent node with two red children.

In 2008, Robert Sedgewick introduced Left-Leaning Red-Black (LLRB) trees, restricting 3-nodes so their single red link always leans left to simplify bottom-up rebalancing.

Local Pointer Rotations: Left-Rotate and Right-Rotate

Rebalancing alters local topology using two inverse O(1) pointer operations—Left-Rotate(T, x) and Right-Rotate(T, y)—that preserve inorder key ordering. If x has right child y (with subtrees α = x.left, β = y.left, γ = y.right), a left rotation promotes y into x's position, makes x the left child of y, and re-attaches β as x.right in six pointer updates.

Insertion Fixup (At Most Two Rotations) and Deletion Fixup (At Most Three Rotations)

A newly inserted leaf node z is colored red, preserving Property 5 (black-height uniformity). If z's parent z.p is also red, a red–red violation occurs below black grandparent g = z.p.p, and the fixup loop inspects z's uncle u:

• Case 1 (Uncle u is Red — 4-Node Split): Recolor z.p and u to black, recolor g to red, and advance z ← g up two levels (zero rotations).
• Case 2 (Uncle u is Black, Zig-Zag Triangle): Rotate z.p to straighten (z, z.p, g) into a colinear line, entering Case 3.
• Case 3 (Uncle u is Black, Colinear Line): Recolor z.p black and g red, then rotate g toward u. The loop terminates after at most two rotations.

During deletion, removing a red node leaves all invariants intact; removing a black node assigns a temporary "extra black" token to its replacement child x and resolves it via sibling-color cases in at most three rotations. Because rotations are O(1) in the worst case, red-black trees support persistent functional snapshots and augmented interval trees (caching subtree maximum endpoints) for genomic feature intersection queries.

When should a red-black tree be preferred over an AVL tree?

AVL trees maintain a tighter height bound (~1.44 log₂ n vs. 2.00 log₂ n) for slightly faster read-only lookups, but an AVL deletion can trigger Θ(log n) rotations to the root. Because red-black trees cap worst-case rotations at 2 per insertion and 3 per deletion, they are preferred for mutable maps, kernel schedulers, and persistent trees with frequent insertions and deletions.

Why are newly inserted nodes colored red instead of black?

Inserting a black leaf would add one extra black node to paths through that leaf, violating Property 5 (uniform black-height) on every insertion. Coloring the new leaf red preserves every path's black-height, and whenever its parent is black, the insertion finishes with zero rotations or recolorings.

1. Bayer, R. (1972). "Symmetric binary B-Trees: Data structure and maintenance algorithms." Acta Informatica, 1(4), 290–306. https://doi.org/10.1007/BF00289509
2. Guibas, L. J., & Sedgewick, R. (1978). "A dichromatic framework for balanced trees." 19th Annual Symposium on Foundations of Computer Science (FOCS), 8–21. https://doi.org/10.1109/SFCS.1978.3
3. Tarjan, R. E. (1983). "Updating a balanced search tree in O(1) rotations." Information Processing Letters, 16(5), 253–257. https://doi.org/10.1016/0020-0190(83)90099-690099-6)
4. Sen, S., Tarjan, R. E., & Kim, D. H. K. (2016). "Deletion without rebalancing in balanced binary trees." ACM Transactions on Algorithms, 12(4), 57:1–57:31. https://doi.org/10.1145/2903142