Offensive Security Researcher & Quantum Cryptography Analyst

Red-Black Trees Data Structure: A Comprehensive Guide with Implementation

Abdul Wahab Junaid
Red-Black Trees: A Comprehensive Guide

I remember the first time I tried to implement a self-balancing binary search tree, and I quickly realized that a plain binary search tree can degrade into something that behaves like a linked list if I insert already-sorted data. Red-black trees are one of the most widely used answers to this problem. They are binary search trees with one extra idea layered on top: every node gets a color, either red or black, and a small set of coloring rules guarantees the tree never gets too lopsided.

What draws me to red-black trees specifically, compared to other balanced trees like AVL trees, is the balance they strike (no pun intended) between strict balancing and low maintenance overhead. They guarantee $O(\lg n)$ height without demanding perfect balance, which means fewer rotations on average during insertion and deletion. This is exactly why they show up everywhere from language runtime libraries to kernel schedulers.

History and Background

Red-black trees originate from work by Rudolf Bayer in 1972, who introduced a structure called “symmetric binary B-trees” as a way of representing 2-3-4 B-trees using binary tree nodes. The red-black coloring scheme and terminology that I use today were introduced later by Leonidas J. Guibas and Robert Sedgewick in their 1978 paper, “A Dichromatic Framework for Balanced Trees,” which reframed Bayer’s structure in a more intuitive, visually motivated way using the red/black color labels.

Since then, red-black trees have become one of the most deployed balanced-tree structures in real software. The Linux kernel uses red-black trees for scheduling and virtual memory management, Java’s TreeMap and TreeSet classes are backed by red-black trees, and the C++ Standard Template Library’s map and set containers are also typically implemented using them. Sedgewick himself later refined the presentation further with “left-leaning red-black trees” in 2008, which simplify the implementation logic even more.

Problem Statement

A plain binary search tree gives me $O(\lg n)$ search, insertion, and deletion only when it happens to stay roughly balanced. But if I insert data in sorted or adversarial order, the tree can degenerate into a structure of height $O(n)$, at which point all operations degrade to linear time, defeating the purpose of using a tree at all.

I need a self-balancing binary search tree that guarantees height $O(\lg n)$ regardless of insertion order, while keeping the rebalancing work per operation small enough to remain practical for real, high-throughput systems.

Core Concepts

A red-black tree is a binary search tree in which every node is colored either red or black, and the tree satisfies five properties:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (represented as a NIL sentinel) is black.
  4. If a node is red, then both its children are black (no two reds in a row on any path).
  5. For every node, all simple paths from that node down to descendant leaves contain the same number of black nodes — this count is called the node’s black-height, denoted bh(x).

These five properties together are what guarantee logarithmic height, and I’ll show the exact reasoning in the mathematical foundation section.

Other key terms I rely on:

How It Works

Insertion starts exactly like a standard binary search tree insertion — I walk down from the root, comparing keys, until I find the correct empty spot, and I insert the new node there, coloring it red. I color new nodes red rather than black because a red node doesn’t automatically break property 5 (the black-height property); a new black node would.

However, inserting a red node can violate property 4 if its parent is also red. So after the plain insertion, I run RB-INSERT-FIXUP, which walks up the tree from the newly inserted node, examining the color of the node’s “uncle” (its parent’s sibling), and applying one of three cases — recoloring, or a rotation combined with recoloring — until all red-black properties are restored.

Deletion is more involved. I again start with the standard BST deletion logic (removing a node with zero, one, or two children, using a successor if needed), but if the removed or moved node was black, this can create a “double-black” imbalance that violates the black-height property. I then run RB-DELETE-FIXUP, which handles four possible cases depending on the color of the sibling of the double-black node and its children, applying recoloring and rotations until the tree is valid again.

Working Principle

The underlying mechanism that keeps everything efficient is that both fixup routines only need $O(1)$ work per level as they move up the tree, and they perform at most $O(\lg n)$ iterations because the tree height is $O(\lg n)$. Rotations themselves are constant-time pointer operations — they don’t touch the whole tree, just a small local neighborhood around an edge.

What I find elegant about the design is how the fixup logic is structured as a small number of well-defined “cases,” each of which either terminates the fixup immediately after one recoloring/rotation step, or transforms the problem into a strictly simpler case that then gets resolved in at most one more step. This bounded, case-based structure is what keeps the worst-case number of rotations small: at most 2 rotations for insertion, and at most 3 rotations for deletion, even though recoloring can propagate further up the tree.

Mathematical Foundation

Theorem: A red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$.

To prove this, I first establish a helper claim: the subtree rooted at any node $x$ contains at least $2^{bh(x)} – 1$ internal nodes, where $bh(x)$ is the black-height of $x$.

Proof by induction on the height of $x$.

Base case: if the height of $x$ is 0, then $x$ is a leaf (NIL), so its subtree contains $2^0 – 1 = 0$ internal nodes, which is correct since NIL nodes aren’t counted as internal.

Inductive step: consider a node $x$ with positive height and two children. Each child has black-height either $bh(x)$ or $bh(x) – 1$, depending on whether the child itself is red or black (a red child keeps the same black-height as its parent since red nodes don’t count toward black-height). By the inductive hypothesis, each child’s subtree has at least $2^{bh(x)-1} – 1$ internal nodes. So the subtree rooted at $x$ has at least:

$$ (2^{bh(x)-1} – 1) + (2^{bh(x)-1} – 1) + 1 = 2^{bh(x)} – 1 $$

internal nodes, which completes the induction.

Now, let $h$ be the height of the whole red-black tree. Property 4 guarantees that at least half the nodes on any root-to-leaf path are black (since no two consecutive nodes can both be red), so:

$$ bh(root) \ge h/2 $$

Combining this with the helper claim gives:

$$ n \ge 2^{h/2} – 1 $$

Rearranging:

$$ n + 1 \ge 2^{h/2} $$

$$ \lg(n+1) \ge h/2 $$

$$ h \le 2\lg(n+1) $$

This proves the height is $O(\lg n)$, which is exactly the guarantee that makes search, insertion, and deletion all run in $O(\lg n)$ time in the worst case.

Diagrams

flowchart TD
    A[Insert node as in plain BST, color it RED] --> B{Parent is RED?}
    B -->|No| C[Done, properties hold]
    B -->|Yes| D{Uncle is RED?}
    D -->|Yes| E[Recolor parent, uncle to BLACK
grandparent to RED
move up to grandparent]
    E --> B
    D -->|No| F{Node is a triangle shape?}
    F -->|Yes| G[Rotate to convert to a line shape]
    G --> H[Recolor parent BLACK, grandparent RED
rotate grandparent]
    F -->|No| H
    H --> I[Color root BLACK, done]

Pseudocode

Left rotation (right rotation is the mirror image):

LEFT-ROTATE(T, x)
    y = x.right
    x.right = y.left
    if y.left != T.nil
        y.left.p = x
    y.p = x.p
    if x.p == T.nil
        T.root = y
    elseif x == x.p.left
        x.p.left = y
    else
        x.p.right = y
    y.left = x
    x.p = y

Insertion:

RB-INSERT(T, z)
    y = T.nil
    x = T.root
    while x != T.nil
        y = x
        if z.key

Insertion fixup:

RB-INSERT-FIXUP(T, z)
    while z.p.color == RED
        if z.p == z.p.p.left
            y = z.p.p.right          // y is z's uncle
            if y.color == RED
                z.p.color = BLACK              // case 1
                y.color = BLACK                // case 1
                z.p.p.color = RED              // case 1
                z = z.p.p                      // case 1
            else
                if z == z.p.right
                    z = z.p                    // case 2
                    LEFT-ROTATE(T, z)          // case 2
                z.p.color = BLACK              // case 3
                z.p.p.color = RED              // case 3
                RIGHT-ROTATE(T, z.p.p)         // case 3
        else
            // symmetric, with "left" and "right" swapped
    T.root.color = BLACK

Step-by-Step Example

Let me trace an insertion into a small tree. Suppose my tree currently contains the black nodes 10 (root) and 20 (right child of 10), and I insert 15.

  1. Standard BST insertion places 15 as the left child of 20, colored red. Tree: 10(B) -> right -> 20(B) -> left -> 15(R).
  2. In RB-INSERT-FIXUP, I check z.p.color, where z = 15. z.p = 20, and 20 is black, so the while loop condition (z.p.color == RED) is false immediately. No fixup needed — the tree is already valid, since a red node with a black parent doesn’t violate any property.

Now suppose instead my tree has root 20(B) with left child 10(R) and right child 30(R), and I insert 5.

  1. Standard BST insertion places 5 as the left child of 10, colored red. Now 10 is red and its child 5 is also red — this violates property 4.
  2. In fixup, z = 5, z.p = 10 (red), so I enter the loop. z.p == z.p.p.left is true (10 is the left child of 20). The uncle y = z.p.p.right = 30, which is red. This is case 1: I recolor z.p (10) to black, y (30) to black, and z.p.p (20) to red, then move z up to z.p.p, i.e., z = 20.
  3. Now z = 20 is the root. The loop checks z.p.color, but z.p is T.nil, whose color is black by convention, so the loop ends.
  4. Finally, T.root.color = BLACK recolors the root back to black (it had been set red in step 2), restoring property 2.

The resulting tree has root 20(B), with children 10(B) and 30(B), and 10 now has a red left child 5. All five red-black properties hold.

Time Complexity

Space Complexity

A red-black tree uses $O(n)$ space to store $n$ nodes, with each node needing a small constant amount of extra space for the color bit (often packed into a single bit alongside pointers) beyond what a plain BST node would need. Recursive implementations of search or traversal use $O(\lg n)$ additional space on the call stack due to the tree’s bounded height; iterative implementations can bring this down to $O(1)$ auxiliary space.

Correctness Analysis

Correctness comes down to showing that the fixup routines always terminate with all five red-black properties restored, without ever violating the binary-search-tree ordering property (which rotations preserve by construction, since rotation only changes parent-child relationships along a single edge, not the relative order of keys).

For insertion, I rely on a case analysis: case 1 (red uncle) preserves black-heights everywhere except possibly re-triggering a violation one level higher, which is why z moves up and the loop continues — but each iteration moves strictly closer to the root, so it must terminate within $O(\lg n)$ steps. Cases 2 and 3 (black uncle) use rotation plus recoloring, and I can verify directly that after these cases, the loop terminates, since the parent becomes black immediately.

For deletion, a similar four-case analysis handles the “double-black” violation, always either terminating in $O(1)$ additional work or reducing the problem to a case one level up the tree, which again guarantees termination within $O(\lg n)$ steps.

Advantages

Disadvantages

Applications

Implementation in C

Here’s a complete implementation of red-black tree insertion, including the fixup logic, using a sentinel NIL node to simplify boundary handling:

#include stdio.h>
#include stdlib.h>

typedef enum { RED, BLACK } Color;

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

Node *NIL;  /* shared sentinel representing all leaves, always BLACK */

Node* newNode(int key) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->color = RED;       /* newly inserted nodes always start RED */
    node->left = node->right = node->parent = NIL;
    return node;
}

void leftRotate(Node **root, Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left != NIL) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NIL) *root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
}

void rightRotate(Node **root, Node *x) {
    Node *y = x->left;
    x->left = y->right;
    if (y->right != NIL) y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == NIL) *root = y;
    else if (x == x->parent->right) x->parent->right = y;
    else x->parent->left = y;
    y->right = x;
    x->parent = y;
}

/* Restores red-black properties after a plain BST insertion. */
void insertFixup(Node **root, Node *z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node *y = z->parent->parent->right;  /* uncle */
            if (y->color == RED) {
                /* Case 1: uncle is red -> recolor and move up */
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    /* Case 2: triangle shape -> rotate to line shape */
                    z = z->parent;
                    leftRotate(root, z);
                }
                /* Case 3: line shape -> recolor and rotate */
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else {
            /* symmetric case: parent is a right child */
            Node *y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    (*root)->color = BLACK;   /* property 2: root is always black */
}

void insert(Node **root, int key) {
    Node *z = newNode(key);
    Node *y = NIL;
    Node *x = *root;

    while (x != NIL) {
        y = x;
        if (z->key  x->key) x = x->left;
        else x = x->right;
    }
    z->parent = y;
    if (y == NIL) *root = z;
    else if (z->key  y->key) y->left = z;
    else y->right = z;

    insertFixup(root, z);
}

void inorder(Node *node) {
    if (node == NIL) return;
    inorder(node->left);
    printf("%d(%s) ", node->key, node->color == RED ? "R" : "B");
    inorder(node->right);
}

int main(void) {
    NIL = (Node*)malloc(sizeof(Node));
    NIL->color = BLACK;
    NIL->left = NIL->right = NIL->parent = NULL;

    Node *root = NIL;
    int keys[] = {10, 20, 30, 15, 5, 25, 1};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i  n; i++) {
        insert(&root, keys[i]);
    }

    printf("Inorder traversal (key(color)): ");
    inorder(root);
    printf("\n");
    printf("Root key: %d, color: %s\n", root->key, root->color == RED ? "R" : "B");

    return 0;
}

The most important detail I want to highlight is the shared NIL sentinel — every leaf pointer in the tree points to this single node, which is always black. This removes the need for repeated NULL checks throughout the rotation and fixup logic, since I can safely read NIL->color and always get BLACK.

Sample Input and Output

Input:
Insert keys in order: 10, 20, 30, 15, 5, 25, 1

Output:
Inorder traversal (key(color)): 1(R) 5(B) 10(R) 15(B) 20(B) 25(R) 30(B)
Root key: 20, color: B

The exact colors depend on the precise sequence of rotations and recoloring performed, but running this should always produce a tree where the root is black, no red node has a red child, and every root-to-leaf path has the same black-height — properties I can verify with a small helper function if I want to double-check correctness programmatically.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version