Red–black trees

One colour per node keeps a binary tree nearly balanced. Watch which insertions recolour and which rotate.

⋯51static void fix_after_insert(struct rb *z)52{53    while (z->parent != NULL && z->parent->colour == RED) {54        struct rb *p = z->parent;55        struct rb *g = p->parent;56        if (p == g->left) {57            struct rb *u = g->right;58            if (u != NULL && u->colour == RED) {59                p->colour = BLACK;60                u->colour = BLACK;61                g->colour = RED;62                recolourings++;63                z = g;64            } else {65                if (z == p->right) {66                    rotate_left(p);67                    z = p;68                    p = z->parent;69                }70                p->colour = BLACK;71                g->colour = RED;72                rotate_right(g);73            }74        } else {75            struct rb *u = g->left;76            if (u != NULL && u->colour == RED) {77                p->colour = BLACK;78                u->colour = BLACK;79                g->colour = RED;80                recolourings++;81                z = g;82            } else {83                if (z == p->left) {84                    rotate_right(p);85                    z = p;86                    p = z->parent;87                }88                p->colour = BLACK;89                g->colour = RED;90                rotate_left(g);91            }92        }93    }94    root->colour = BLACK;95}⋯143    for (int i = 0; i < 8; i++)144        rb_insert(keys[i]);145    preorder(root);

Glued to their parents

AVL trees store a height in every node. A red–black tree stores one bit instead, a colour, and keeps four rules:

1. Every node is red or black.
2. The root is black.
3. A red node never has a red child.
4. Every path from a node down to an empty child passes the same number of black nodes.

The rules mean more than they seem to. Think of a red node as a key glued to its parent, part of the same node. Then a black node with no red children is a node with one key; with one red child, a node with two keys; with two red children, three keys. Rule 3 says the glue goes only one level. Rule 4 says every path meets the same number of these combined nodes: all leaves are level. That is a 2-3-4 tree, a 2-3 tree that also allows nodes with three keys, drawn with binary nodes.

Set “View” to 2-3-4 and watch the same insertions with each red key pulled up into its parent. The final tree is 10 20 at the root over 1 5, 15 and 25 27 30, every leaf one level down.

The code and its cost

The node

The full program, rb.c, gives each node a colour and a pointer to its parent, so that the fix-up can climb:

enum colour { RED, BLACK };

struct rb {
    int key;
    enum colour colour;
    struct rb *left, *right, *parent;
};

The root, root, and the two counters are static variables outside any function. Each node is 32 bytes: the key and the colour (an enum, 4 bytes here) then three pointers.

Inserting

rb_insert inserts as in Binary search trees: walk down from the root, hang the new node where the walk falls off, and set its parent. The new node is red, because a red node adds no black node to any path, so rule 4 still holds. Only rule 3 can break: if the new node’s parent is red too. fix_after_insert repairs that.

The fix-up

while (z->parent != NULL && z->parent->colour == RED) {
    struct rb *p = z->parent;
    struct rb *g = p->parent;
    if (p == g->left) {
        struct rb *u = g->right;
        if (u != NULL && u->colour == RED) {
            p->colour = BLACK;
            u->colour = BLACK;
            g->colour = RED;
            recolourings++;
            z = g;
        } else {
            if (z == p->right) {
                rotate_left(p);
                z = p;
                p = z->parent;
            }
            p->colour = BLACK;
            g->colour = RED;
            rotate_right(g);
        }
    } else {
        /* the mirror image, left and right swapped */
    }
}
root->colour = BLACK;

z is the red node, p its red parent, g the grandparent (black, since the tree was valid before), and u the uncle, g’s other child. Two cases:

• The uncle is red. In 2-3-4 terms, g with its two red children was a full node, and z would make a fourth key. Recolouring splits it: p and u turn black and g turns red, which pushes g up into the node above. That may make red under red one level higher, so the loop goes on with z = g, two levels up. No pointer changes.
• The uncle is black or empty. g’s node had room. One rotation at g, with p turned black and g red, makes p the top of the three. If z is on the inside (a right child under a left child, or the mirror), a first rotation at p turns it into the outside case. Either way the loop ends.

At the end the root is made black: a red root only adds one black node to every path.

rotate_left and rotate_right are the rotations of AVL trees, with the parent pointers kept up to date as well.

What it costs

Rule 4 gives every path the same number of black nodes, and rule 3 lets at most one red node follow each black one, so the longest path from the root is at most twice the shortest. From that, a red–black tree with n nodes has height below 2 log₂(n + 1). Search, insertion and removal each cost a number of steps proportional to log n. An insertion makes at most two rotations; recolouring may climb, two levels at a time, towards the root.

Against AVL trees, the balance is looser: up to twice the shortest path, not about 1.44 times log₂ n. In exchange, an insertion or a removal changes fewer pointers, which is why many libraries choose red–black trees for maps that change often. Removal follows the same idea, with more cases, and is not shown here.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic rb.c -o rb
./rb

It prints the tree in preorder with each colour, 20B 10R 5B 1R 15B 27B 25R 30R, then 3 rotations, 2 recolourings.

Worked example

Insert 3 into the final tree. The walk goes left of 20, left of 10, left of 5 and right of 1: 3 hangs as 1’s right child, red under red. Its uncle, 5’s right child, is empty, and 3 is on the inside (a right child of a left child). So: rotate 1 left, which lifts 3 above 1; then 3 turns black, 5 turns red, and 5 rotates right, which lifts 3 above 5. 3 is black over 1 and 5, both red. Two more rotations, and the preorder becomes 20B 10R 3B 1R 5R 15B 27B 25R 30R. Every path still passes 2 black nodes.

The height bound. For n = 8, 2 log₂ 9 ≈ 6.3, so no red–black tree of 8 nodes is taller than 6. The clip’s tree has height 3.

The 2-3-4 reading. A black node with two red children is a node with three keys, a 4-node: the final tree’s 27 with 25 and 30.

Two checks. Can a red–black tree have a red root? (No: rule 2.) What is the black height of the final tree, counting the root? (2: 20 and 5 on the way to 1, 20 and 27 on the way to 25.)

Where it’s used

Ordered maps and sets. Many standard libraries implement their ordered maps and sets as red–black trees.

Schedulers. CFS, Linux’s scheduler until version 6.6, kept runnable tasks in a red–black tree ordered by the processor time each had used, and always ran the leftmost.

B-trees. The 2-3-4 reading points the other way too: B-trees keep many keys in a node on purpose, sized to a disk block.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.