Red-black trees

A self-balancing BST that uses colors and rotations to guarantee O(log n). · 10 min read

A red-black tree is a binary search tree with one extra bit of information per node: the node is either red or black. Those colors enforce balance loosely enough that insertion is cheap, but strongly enough that height stays logarithmic.

The invariants

A red-black tree must satisfy these rules:

• Every node is red or black.
• The root is black.
• All nullptr leaves are considered black.
• A red node cannot have a red parent or red child.
• Every path from a node down to a nullptr leaf has the same number of black nodes. This is the black height.

Interactive visualization: Red-black insertion: recolor and rotate — step through it frame by frame on this page.

Insertion idea

Insertion starts exactly like BST insertion: find the empty spot. The new node is colored red because adding a red node does not immediately increase the black height of any path. The only possible problem is a red-red violation: the new red node might have a red parent.

If the parent and uncle are both red, we recolor: parent and uncle become black, grandparent becomes red, and the possible violation moves upward. If the uncle is black, we use one or two rotations to reshape the local subtree, then recolor parent/grandparent.

C++ node sketch

enum Color { RED, BLACK };

struct Node {
    int key;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

    Node(int k)
        : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

Production implementations use sentinels for nil leaves, but the pointer idea is the same as the linked-list chapter: rotations are careful pointer rewiring.

Why height is logarithmic