Red-Black Tree

A self-balancing binary search tree that keeps height logarithmic using node colors and a small set of rotation rules.

Balance by coloring

A red-black tree is a binary search tree in which every node is colored red or black, subject to invariants that force the longest root-to-leaf path to be at most twice the shortest. This keeps height O(log n) and guarantees O(log n) search, insert, and delete in the worst case.

The invariants

Kronos motion — classical

Every node is red or black; the root is black.
Red nodes have black children (no two reds in a row).
Every root-to-null path passes through the same number of black nodes (the black-height).
New nodes are inserted red, then rotations and recolorings restore the invariants.

Why the height is bounded

Because every path has the same black-height b, and reds cannot be adjacent, the shortest path (all black) has length b and the longest (alternating) has length at most 2b. A tree with n nodes therefore has height at most 2 log2(n+1). Insertion fixes violations by recoloring or at most two rotations; deletion by at most three.

python

# left rotation about x
def left_rotate(x):
    y = x.right
    x.right = y.left
    if y.left: y.left.parent = x
    y.parent = x.parent
    # ... splice y in place of x, then y.left = x

Where it is used

Red-black trees back many standard library ordered maps and sets (C++ std::map, Java TreeMap) and the Linux kernel's scheduler and memory maps. They balance with fewer rotations on average than AVL trees, trading slightly greater height for cheaper updates.

Alternatives

AVL trees are more rigidly balanced (faster lookups, more rotations). Skip lists and treaps achieve similar expected bounds with randomization and simpler code. B-trees and B+ trees generalize the balancing idea for disk-based storage.