The Red-Black Tree

A binary search tree keeps smaller keys in a node’s left subtree and larger keys in its right subtree. Search, insertion, deletion, predecessor, and successor follow paths whose lengths are bounded by the tree’s height. A complete ordered traversal instead visits all n stored nodes and takes O(n) time.

Insertion order can make an unrestricted tree a chain. Inserting 10, 20, 30, 40, 50 in that order creates a search path containing all five stored nodes. A red-black tree adds one color bit per node and repairs the tree after updates, keeping single-key searches and updates within O(log n) worst-case time.

Each stored node is red or black. The root is black, absent children are represented conceptually by black NIL leaves, and a red stored node cannot have a red child. A stored node with no keys below it may therefore be red: its two children are the black NIL leaves.

For a node x, define its black height as the number of black nodes on any path from, but not including, x down to and including a descendant NIL leaf. Every such path must have the same count. Colors do not affect key order; they constrain how uneven the paths may become.

Let the root have black height b. Because a red node cannot have a red child, a longest root-to-NIL path can place at most one red stored node between consecutive black nodes. Its height is therefore at most 2b.

A subtree with black height b contains at least 2ᵇ − 1 stored nodes. For a tree with n stored nodes, b ≤ log₂(n + 1), so the height is at most 2 log₂(n + 1). Search and updates inherit a worst-case O(log n) bound.

Search ignores color. Starting at the root, compare the target key with the current key, continue left for a smaller target, and continue right for a larger target. Reaching an absent child proves that the key is not present.

The color invariants matter indirectly: they bound the number of comparisons. Minimum, maximum, predecessor, successor, lower-bound, and upper-bound queries use the same ordered paths and take O(log n) worst-case time.

Insertion first follows the ordinary search-tree path and replaces a black NIL leaf with the new stored node. The new node starts red and receives two black NIL children. This substitution does not change any path’s black height, so only the rule against a red parent with a red child can fail.

If the parent is black, insertion is complete. If the parent is red, the grandparent must be black before the insertion, and the repair depends on the color of the new node’s uncle.

When the parent and uncle are both red, recolor them black and recolor the grandparent red. Every path through the parent or uncle gains one black node and loses the black grandparent, so black height is unchanged.

The grandparent may now conflict with its own red parent. The algorithm continues upward from the grandparent. If the conflict reaches the root, coloring the root black completes the repair and increases every root-to-leaf black height equally.

Suppose the parent is the grandparent’s left child and the new node is the parent’s left child. The uncle is black. Rotate right at the grandparent, color the parent black, and color the former grandparent red. The right-right case uses the mirrored left rotation.

This single rotation removes the red-red edge. The promoted parent replaces the former black grandparent, so every path through the repaired subtree retains the same black height.

An inner configuration bends in opposite directions: left then right, or right then left. First rotate at the parent to convert it into an outer configuration. Then apply the outer-case rotation and recoloring at the grandparent.

Insertion therefore performs at most two rotations. Recoloring can propagate to the root, but every propagation step moves two levels upward, so the total repair remains O(log n).

Deletion first uses the ordinary binary-search-tree splice. For a node with two stored children, the algorithm uses its in-order successor, reducing the structural removal to a node with at most one stored child. An implementation may copy the successor’s key and value or transplant the successor node. Removing a red node cannot change black height. Replacing a black node with its red child only requires coloring that child black.

The difficult case removes a black node whose replacement is also black or NIL. Paths through that position have one fewer black node. Implementations often describe the missing contribution as an extra black or double black attached to the replacement position.

Repair examines the replacement’s sibling. A red sibling is rotated above the parent and recolored, producing a black sibling without changing black height. With a black sibling whose children are both black, color the sibling red. If the parent is red, coloring it black resolves the deficit; if the parent is black, the missing black contribution moves upward to the parent.

If the sibling has a red child, rotations and recoloring move one black node onto every path and terminate the repair. A red far child permits one rotation at the parent. A red near child is first rotated into the far position. Deletion uses at most three rotations, while recoloring may continue toward the root.

The numbers in 2-3-4 tree count children, not stored keys. A 2-node contains one key and divides the key space into two child ranges; a 3-node contains two keys and three child ranges; a 4-node contains three keys and four child ranges.

A red link joins its child with its black parent. A black node alone encodes a 2-node, one joined red child encodes a 3-node, and two joined red children encode a 4-node. Collapsing those links produces a 2-3-4 tree whose leaves all have the same depth. Recoloring splits a full 4-node, while rotations change the binary encoding used for the same multiway node.

Red-black trees provide a deterministic height bound with one bit of balance metadata. Search never changes the tree, unlike a splay tree, and updates avoid the probabilistic worst case of a treap. The standard bottom-up algorithms perform at most two rotations for insertion and three for deletion.

The height limit is looser than an AVL tree’s, so lookup paths can be longer. Nodes also require multiple pointers and usually separate allocations, which weakens cache locality compared with sorted arrays and page-oriented B-trees. Concurrent updates need synchronization because rotations change several links.

OpenJDK implements TreeMap as a red-black tree and guarantees logarithmic containsKey, get, put, and remove. Its HashMap can convert a sufficiently populated bucket into a tree bin. Those bins provide worst-case logarithmic operations when keys have distinct hashes or equal-hash keys are orderable.

The Linux kernel provides an intrusive red-black-tree implementation in which struct rb_node is embedded in the caller’s object. Its documentation cites high-resolution timers and scheduler queues as users and presents interval search as an augmented-tree example. Callers supply comparison and locking policy while the shared code supplies rotations and recoloring.

A red-black tree is a binary search tree constrained by equal black height and the absence of adjacent red stored nodes. Those rules limit height to 2 log₂(n + 1), giving worst-case O(log n) single-key ordered queries and updates.

Insertion replaces a NIL position with a red stored node and repairs any red-red conflict with recoloring and at most two rotations. Deletion restores a missing black contribution with sibling cases and at most three rotations. The result is deterministic balance with less rigid height control than an AVL tree.