Learn Zig Series (#109) - Red-Black Trees

scipio

Published: 15 Jul 2026 › Updated: 15 Jul 2026 Learn Zig Series (#109) - Red-Black Trees

Learn Zig Series (#109) - Red-Black Trees

What will I learn?

Why a red-black tree is the exact same balancing idea as last episode's B-tree, only squeezed back down onto a binary node -- one key, two children -- by smuggling the "how full is this node" bookkeeping into a single colour bit;
Why a red link means "glue these two nodes into one fat B-tree node", and how that one mental model turns every red-black rule from an arbitrary incantation into something you can derive;
How to build a working left-leaning red-black tree from scratch in Zig, where insertion is a plain recursive BST insert followed by three tiny fix-up lines -- rotate, rotate, flip -- and nothing else;
Why rotation and recolouring are the binary-side equivalents of the B-tree's split, and why they cost O(1) each while keeping the height pinned at roughly 2 log2(n);
How to test a balanced tree so the test proves the load-bearing invariant -- equal black-height on every path, no two red links in a row -- and proves zero leaks via std.testing.allocator (episode 12);
Where red-black trees genuinely live -- the Linux kernel scheduler, std::map, Java's TreeMap -- and when the B-tree or a plain skip list is the better call;
How this maps onto the equivalents in C, Rust, and Go, and why the recursive left-leaning variant is the one that spares you the pointer-juggling nightmare the classic textbook version is infamous for.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org);
Episode 108 fresh in your head -- a red-black tree is a B-tree of minimum degree 2 wearing a binary disguise, so if "split a full node, promote the median" is fuzzy, re-read that one first;
Comfort with generics via comptime (episode 14) and allocators (episodes 7 and 26), plus the recursive BST shape we have leaned on since the B-tree;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#109) - Red-Black Trees

Last episode ended on a promise that sounds almost too tidy to be true: take the B-tree, the fat-node structure whose whole power came from packing many keys into one node, and squeeze that node all the way back down to a single key -- a plain binary node -- yet somehow keep the guaranteed balance. I said the trick was to tag each node with a single bit, think of it as a colour, and enforce a couple of rules about how those colours may sit next to each other. Today we cash that promise. The structure is the red-black tree, and by the end you will see that it is not a different idea from the B-tree at all -- it is literally a B-tree of minimum degree 2, redrawn one key at a time. But first, the small debt from episode 108.

Solutions to Episode 108 Exercises

Exercise 1 -- min and max. Every leaf of a B-tree sits at the same depth, and the smallest key lives at the far-left leaf, the largest at the far-right. So both are a straight descent -- no comparisons, no branching, just follow children[0] (or children[n]) until you hit a leaf and read off the edge key. Handle the empty tree by returning null.

// Add inside BTree(comptime T, comptime t, comptime lessThan). Smallest key: keep taking
// children[0] to the far-left leaf, return keys[0]. Largest mirrors it down children[n].
fn min(self: *Self) ?T {
    var node = self.root orelse return null;
    while (!node.leaf) node = node.children[0];
    return node.keys[0];
}

fn max(self: *Self) ?T {
    var node = self.root orelse return null;
    while (!node.leaf) node = node.children[node.n];
    return node.keys[node.n - 1];
}

The key insight is that a B-tree needs no special "find the minimum" machinery -- the sorted-node, all-leaves-level invariant means the extremes are always at the two corners, reachable by a single loop with no back-tracking.

Exercise 2 -- height. Same invariant, cashed differently: because every leaf is at the identical depth, you can measure the tree by walking one spine and counting hops. Descend children[0] until you reach a leaf, incrementing as you go. No recursion, no max-of-subtrees -- one path tells you the height of the whole tree.

// Every leaf is at the same depth, so one spine measures the tree. Empty -> 0, single node -> 1.
fn height(self: *Self) usize {
    var node = self.root orelse return 0;
    var h: usize = 1;
    while (!node.leaf) : (h += 1) node = node.children[0];
    return h;
}

This is the concrete payoff of guaranteed balance. Insert a few hundred sequential integers with t = 2 and this returns something close to log_2(n), never the linear disaster an unbalanced BST would give you.

Exercise 3 -- delete, the hard one. Deletion is the genuinely fiddly B-tree operation, and it is fiddly for one reason: a node can underflow below t - 1 keys and must repair itself by borrowing a key from a sibling or merging with one -- which is the split from episode 108 run in reverse. The discipline that keeps it clean is the mirror image of insert's "split full nodes on the way down": here we guarantee, before we ever descend into a child, that the child holds at least t keys. That way an underflow is always fixable at the level we are on, and we never have to walk back up. Here is the whole thing -- it slots into the same BTree struct, and it reuses episode 108's searchNode so we only touch the tree when the key is actually present.

// Deletion keeps insert's top-down promise in reverse: before descending into a child we
// guarantee it has at least t keys (borrow from a sibling, or merge), so a delete never
// has to walk back up to repair an underflow.
fn delete(self: *Self, value: T) bool {
    const r = self.root orelse return false;
    if (searchNode(r, value) == null) return false; // reuse ep108 search; act only if present
    self.removeKey(r, value);
    if (r.n == 0) { // root emptied by a merge: its lone child becomes the new root
        self.root = if (r.leaf) null else r.children[0];
        self.allocator.destroy(r);
    }
    self.len -= 1;
    return true;
}

// removeKey precondition: `node` has >= t keys, or is the root. Locate `value` relative to
// this node's keys and dispatch.
fn removeKey(self: *Self, node: *Node, value: T) void {
    var idx: usize = 0;
    while (idx < node.n and lessThan(node.keys[idx], value)) : (idx += 1) {}

    if (idx < node.n and !lessThan(value, node.keys[idx])) {
        // The key is IN this node.
        if (node.leaf) {
            var i = idx;
            while (i + 1 < node.n) : (i += 1) node.keys[i] = node.keys[i + 1]; // close the hole
            node.n -= 1;
        } else {
            self.removeFromInternal(node, idx);
        }
        return;
    }
    if (node.leaf) return; // not present

    const in_last = (idx == node.n); // was the target subtree the rightmost child?
    if (node.children[idx].n < t) self.fill(node, idx);
    // A tail merge can shrink `node`, sliding our subtree one slot left.
    if (in_last and idx > node.n) {
        self.removeKey(node.children[idx - 1], value);
    } else {
        self.removeKey(node.children[idx], value);
    }
}

// Removing a key that sits in an INTERNAL node: replace it with its predecessor or
// successor (whichever subtree can spare a key), else merge the two children and recurse.
fn removeFromInternal(self: *Self, node: *Node, idx: usize) void {
    const key = node.keys[idx];
    if (node.children[idx].n >= t) {
        var cur = node.children[idx];
        while (!cur.leaf) cur = cur.children[cur.n];
        const pred = cur.keys[cur.n - 1];   // rightmost key of the left subtree
        node.keys[idx] = pred;
        self.removeKey(node.children[idx], pred);
    } else if (node.children[idx + 1].n >= t) {
        var cur = node.children[idx + 1];
        while (!cur.leaf) cur = cur.children[0];
        const succ = cur.keys[0];           // leftmost key of the right subtree
        node.keys[idx] = succ;
        self.removeKey(node.children[idx + 1], succ);
    } else {
        self.merge(node, idx);              // both neighbours minimal: fuse and recurse
        self.removeKey(node.children[idx], key);
    }
}

// fill: children[idx] is one key short. Borrow from a sibling that can spare one, else merge.
fn fill(self: *Self, node: *Node, idx: usize) void {
    if (idx != 0 and node.children[idx - 1].n >= t) {
        borrowFromPrev(node, idx);
    } else if (idx != node.n and node.children[idx + 1].n >= t) {
        borrowFromNext(node, idx);
    } else if (idx != node.n) {
        self.merge(node, idx);
    } else {
        self.merge(node, idx - 1);
    }
}

// Rotate a key through the parent: parent's separator drops into child's front, the left
// sibling's largest key rises to become the new separator.
fn borrowFromPrev(node: *Node, idx: usize) void {
    const child = node.children[idx];
    const sib = node.children[idx - 1];
    var i: usize = child.n;
    while (i > 0) : (i -= 1) child.keys[i] = child.keys[i - 1];       // open child's front
    if (!child.leaf) {
        var j: usize = child.n + 1;
        while (j > 0) : (j -= 1) child.children[j] = child.children[j - 1];
    }
    child.keys[0] = node.keys[idx - 1];
    if (!child.leaf) child.children[0] = sib.children[sib.n];
    node.keys[idx - 1] = sib.keys[sib.n - 1];
    child.n += 1;
    sib.n -= 1;
}

// Mirror image: parent's separator drops onto child's tail, right sibling's smallest rises.
fn borrowFromNext(node: *Node, idx: usize) void {
    const child = node.children[idx];
    const sib = node.children[idx + 1];
    child.keys[child.n] = node.keys[idx];
    if (!child.leaf) child.children[child.n + 1] = sib.children[0];
    node.keys[idx] = sib.keys[0];
    var i: usize = 1;
    while (i < sib.n) : (i += 1) sib.keys[i - 1] = sib.keys[i];       // close sibling's front
    if (!sib.leaf) {
        var j: usize = 1;
        while (j <= sib.n) : (j += 1) sib.children[j - 1] = sib.children[j];
    }
    child.n += 1;
    sib.n -= 1;
}

// merge: fuse children[idx], the separator keys[idx], and children[idx+1] into one full
// node, then close the gap they leave in the parent. The freed sibling is destroyed.
fn merge(self: *Self, node: *Node, idx: usize) void {
    const child = node.children[idx];
    const sib = node.children[idx + 1];
    child.keys[t - 1] = node.keys[idx];                              // separator drops down
    var i: usize = 0;
    while (i < sib.n) : (i += 1) child.keys[i + t] = sib.keys[i];
    if (!child.leaf) {
        i = 0;
        while (i <= sib.n) : (i += 1) child.children[i + t] = sib.children[i];
    }
    i = idx + 1;
    while (i < node.n) : (i += 1) node.keys[i - 1] = node.keys[i];
    i = idx + 2;
    while (i <= node.n) : (i += 1) node.children[i - 1] = node.children[i];
    child.n += sib.n + 1;
    node.n -= 1;
    self.allocator.destroy(sib);
}

That is a lot of moving parts, and it is exactly why deletion is where hand-rolled B-trees go to die. Notice the load-bearing idea though: every repair is a rotation through the parent (borrow) or a fusion with the separator pulled down (merge), and both keep the "every leaf at the same depth" invariant intact. Test it by deleting an interior separator key and asserting the in-order walk is still sorted, len is right, and std.testing.allocator reports zero leaks after the merges free their nodes. Debt paid -- and hold on to the phrase "rotation through the parent", because it is about to reappear as the entire mechanism of today's structure ;-)

The one idea: a red link glues two nodes into one

Here is the mental model that makes red-black trees stop being a pile of arbitrary rules. Take a B-tree of minimum degree 2 -- what people call a 2-3-4 tree, because every node holds 1, 2, or 3 keys and thus has 2, 3, or 4 children. Now redraw each fat node using only binary nodes, one key apiece, and colour the links between them. A black link is a real parent-child edge of the original B-tree. A red link means "these two binary nodes were actually the same fat node -- I only split them apart for drawing". A 3-key node becomes three binary nodes chained by two red links; a 2-key node becomes two nodes joined by one red link; a 1-key node is just a single black-linked node.

That is the whole secret. Every red-black rule you have ever seen memorised is a direct consequence of "a red link is really glue inside one B-tree node":

No node has two red links in a row -- because a B-tree node of degree 2 holds at most 3 keys, so at most 2 red links can chain, and they cannot stack straight down without implying a 4-key node that should have split.
Every root-to-null path has the same number of black links -- because black links are the real B-tree edges, and every leaf of a B-tree is at the same depth. This is the invariant. It is the binary-side spelling of "perfectly balanced".
The root is black, and null links count as black.

Because red links are free (they live inside a conceptual B-tree node), the tree's real height is measured only in black links -- and that black-height is log(n). The reds can at most double the path length, which is why a red-black tree's worst-case height is about 2 log2(n): still O(log n), still guaranteed, just with a factor-of-two slack the fat B-tree node didn't need. Same balance guarantee as episode 108, reached from the binary side.

The node in Zig

I am going to build the left-leaning red-black tree (LLRB), Robert Sedgewick's refinement that adds one extra rule -- red links always lean left -- and in exchange collapses the insertion logic down to something you can hold in your head. The classic Cormen-Leiserson-Rivest-Stein version with parent pointers and a five-case fix-up is a genuine rite of passage to get right; the LLRB does the same job in a fraction of the code, and it corresponds to a 2-3 tree (degree-2 B-tree capped at 2 keys) rather than 2-3-4. The node is about as lean as it gets: a key, a colour, two optional children.

const std = @import("std");

fn RedBlackTree(comptime T: type, comptime lessThan: fn (a: T, b: T) bool) type {
    return struct {
        const Self = @This();
        const Color = enum { red, black };

        // One key, one colour bit, two children. The colour describes the link from this
        // node's PARENT to it -- red means "glued into the parent's B-tree node".
        const Node = struct {
            key: T,
            color: Color,
            left: ?*Node = null,
            right: ?*Node = null,
        };

        root: ?*Node = null,
        allocator: std.mem.Allocator,
        len: usize = 0,

        fn init(allocator: std.mem.Allocator) Self {
            return .{ .root = null, .allocator = allocator, .len = 0 };
        }
    };
}

Compared to the B-tree node's fixed-capacity arrays, this is almost quaint -- back to one key and two pointers, the humble BST shape from the very start. The entire cleverness lives in the color field and the three fix-up moves that maintain it. Note that we treat null as black, which is why the isRed helper below has to guard against it in stead of assuming a node exists.

Rotations and colour flips: the O(1) toolkit

Where the B-tree had one operation that mattered (split), the LLRB has three, and all of them are O(1) pointer surgery. Rotate left takes a node whose right link is red and swings it to the left, so the red leans the way LLRB demands. Rotate right is the mirror, used to fix a moment where two reds briefly stack. Flip colours handles the case where a node has two red children -- which is our binary picture of a 4-key B-tree node that must split -- by recolouring both children black and the node itself red, pushing the "split" one level up. That last one is the recolouring that stands in for the B-tree's promote-the-median.

// A null link is black. Only a real node can be red.
fn isRed(node: ?*Node) bool {
    const n = node orelse return false;
    return n.color == .red;
}

// rotateLeft: h's right link is red; pivot it up so the red leans left. h keeps its colour
// role via x, and the freshly-formed internal link goes red. Returns the new subtree root.
fn rotateLeft(h: *Node) *Node {
    const x = h.right.?;   // guaranteed non-null: we only rotate an existing red right link
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = .red;
    return x;
}

// rotateRight: the mirror image, used to unstack two left-leaning reds in a row.
fn rotateRight(h: *Node) *Node {
    const x = h.left.?;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = .red;
    return x;
}

The colour bookkeeping inside a rotation is the part people fumble, so read it slowly: the pivot x inherits h's old colour (it is taking h's place as the subtree's top), and h goes red because it is now glued below x. Get those two lines right and rotations compose without ever breaking the black-height count -- a rotation moves nodes around but never adds or removes a black link on any path, which is precisely why it is a legal balancing move.

// flipColors: h has two red children -- our binary picture of a B-tree node that is one key
// too fat and must split. Recolour both children black and h red, pushing the split upward.
fn flipColors(h: *Node) void {
    h.color = .red;
    h.left.?.color = .black;
    h.right.?.color = .black;
}

Insert: a BST insert plus three lines

Now the payoff. Insertion into an LLRB is an ordinary recursive binary-search-tree insert -- go left or right, create a red node at the bottom -- followed by three fix-up lines applied on the way back up the recursion. Those three lines, in this exact order, restore all the red-black invariants no matter what the insert disturbed. Rotate left if the right link is red but the left isn't (kill a right-leaning red). Rotate right if we have two left reds in a row (unstack them). Flip colours if both children are red (split the 4-node upward). That is the entire algorithm.

// insertNode: recursive BST insert of a RED node, then restore invariants on the way back
// up with three fix-ups. Returns the (possibly new) root of this subtree.
fn insertNode(self: *Self, node: ?*Node, key: T) !*Node {
    const h = node orelse {
        const fresh = try self.allocator.create(Node);
        fresh.* = .{ .key = key, .color = .red }; // new nodes are always red
        self.len += 1;
        return fresh;
    };

    if (lessThan(key, h.key)) {
        h.left = try self.insertNode(h.left, key);
    } else if (lessThan(h.key, key)) {
        h.right = try self.insertNode(h.right, key);
    } else {
        // Equal key: set semantics, nothing to do. A map would overwrite a value here.
    }

    var x = h;
    if (isRed(x.right) and !isRed(x.left)) x = rotateLeft(x);        // lean the red left
    if (isRed(x.left) and isRed(x.left.?.left)) x = rotateRight(x);  // unstack two left reds
    if (isRed(x.left) and isRed(x.right)) flipColors(x);            // split a 4-node upward
    return x;
}

// insert: delegate, then force the root black (its colour is meaningless, and black keeps
// the black-height honest). This is the one recolour that can raise the whole tree's height.
fn insert(self: *Self, key: T) !void {
    self.root = try self.insertNode(self.root, key);
    self.root.?.color = .black;
}

Trace 10, 20, 30 with the B-tree picture in mind. Insert 10 (red, forced black as root). Insert 20: it lands as a red right child, so the first fix-up rotates left -- 20 becomes the top, 10 its red left child. That red link is our drawing of a single 2-key B-tree node holding [10, 20]. Now insert 30: it goes red-right off 20, rotate-left makes... no wait, 20's left (10) is already red, so instead we hit the third fix-up -- both children red -- and flip colours. That flip is the binary picture of the 2-3 tree splitting a full node and pushing the middle up, exactly the B-tree move from last episode, executed as one recolour. Everything you learned about splitting fat nodes is happening here, one bit at a time.

Search, in-order, and teardown

Searching ignores colour entirely -- a red-black tree is a binary search tree, so lookup is the plain descent you have written a dozen times. Reading the keys back sorted is the standard in-order walk, and teardown is the same post-order free from episode 108, since we still own every node (episode 7's rule).

fn contains(self: *Self, key: T) bool {
    var node = self.root;
    while (node) |n| {
        if (lessThan(key, n.key)) {
            node = n.left;
        } else if (lessThan(n.key, key)) {
            node = n.right;
        } else {
            return true;
        }
    }
    return false;
}

fn inorder(node: ?*Node, out: *std.ArrayList(T)) !void {
    const n = node orelse return;
    try inorder(n.left, out);
    try out.append(n.key);
    try inorder(n.right, out);
}

fn collect(self: *Self, out: *std.ArrayList(T)) !void {
    try inorder(self.root, out);
}

// post-order: free both subtrees before the node itself.
fn freeNode(self: *Self, node: ?*Node) void {
    const n = node orelse return;
    self.freeNode(n.left);
    self.freeNode(n.right);
    self.allocator.destroy(n);
}

fn deinit(self: *Self) void {
    self.freeNode(self.root);
    self.root = null;
}

Testing: prove balance, sorted order, and zero leaks

The B-tree test asserted "in-order output is sorted" and leaned on std.testing.allocator for leaks. For a red-black tree we want more, because the whole reason to write one rather than a plain BST is the balance guarantee -- so the test must actually verify balance, not take it on faith. The cleanest way is a single recursive check that returns the black-height of a subtree, or -1 if any invariant is violated (a red node with a red child, or two sides with unequal black-height). One number, one comparison, and the entire structure is validated.

// blackHeight: number of black links on any root-to-leaf path, or -1 if this subtree
// breaks a red-black rule (a red node with a red child, or unequal black-heights).
fn blackHeight(node: ?*Node) i32 {
    const n = node orelse return 1; // null link is a black leaf
    if (isRed(n) and (isRed(n.left) or isRed(n.right))) return -1; // red-red violation
    const lh = blackHeight(n.left);
    const rh = blackHeight(n.right);
    if (lh == -1 or rh == -1 or lh != rh) return -1;
    return lh + (if (n.color == .black) @as(i32, 1) else 0);
}

fn u32Less(a: u32, b: u32) bool {
    return a < b;
}

test "red-black tree: balanced, sorted, no leaks" {
    var tree = RedBlackTree(u32, u32Less).init(std.testing.allocator);
    defer tree.deinit(); // testing.allocator fails the test if freeNode misses a subtree

    const values = [_]u32{ 50, 20, 80, 10, 30, 60, 90, 5, 25, 35, 70, 85, 95, 15, 40 };
    for (values) |v| try tree.insert(v);
    try std.testing.expectEqual(@as(usize, values.len), tree.len);

    // Membership: everything inserted is found, a gap value is not.
    try std.testing.expect(tree.contains(35));
    try std.testing.expect(!tree.contains(999));

    // The root is always black, and the whole tree obeys the red-black invariants.
    try std.testing.expect(tree.root.?.color == .black);
    try std.testing.expect(blackHeight(tree.root) != -1);

    // The invariant shared with every ordered structure: in-order output is ascending.
    var out = std.ArrayList(u32).init(std.testing.allocator);
    defer out.deinit();
    try tree.collect(&out);
    try std.testing.expectEqual(values.len, out.items.len);
    var i: usize = 1;
    while (i < out.items.len) : (i += 1) {
        try std.testing.expect(out.items[i - 1] < out.items[i]);
    }
}

That blackHeight(tree.root) != -1 line is the one I would defend hardest in review. It is not testing that the code runs -- it is testing that the code produced a genuinely balanced tree, which is the only reason this structure exists. A plain BST would pass the sorted-output assertion and fail this one the instant you fed it sorted input. And like the B-tree, an LLRB is fully deterministic -- no coin flips like the skip list -- so this test does the identical thing on every run without a seed in sight.

Performance: the honest numbers

Search, insert, and delete are all O(log n) worst-case, guaranteed, because the black-height is log(n) and the reds can only double the path. That factor of two is the visible cost versus a B-tree: a red-black tree over a million keys is roughly 40 levels of pointer chasing where a t = 64 B-tree was three node fetches. Every one of those 40 hops is a potential cache miss, and this is the honest reason the fat B-tree wins decisively whenever the data is large or lives across a slow boundary like disk. The red-black tree is a memory-resident structure; it makes no attempt to be cache- or disk-friendly, and it doesn't need to be for its niche.

So why use one at all? Because when your data lives in RAM and you need an ordered map with fast, worst-case-bounded single-key insert, delete, and lookup -- and you do not especially need bulk range scans -- the red-black tree's per-operation cost is lower constant-factor than a B-tree's (no array shuffling within fat nodes, just a rotation or two), and it wastes no space on half-empty node capacity. It is the structure you reach for when you want guaranteed balance and you are not paying a disk tax. Having said that, if you profiled and found your workload was range-scan-heavy, you would go back to the B-tree; and if you wanted dead-simple code and could tolerate expected rather than guaranteed bounds, the skip list from episode 107 is genuinely competitive and far easier to get correct.

Where red-black trees actually live

The reach here rivals the B-tree, just on the other side of the memory boundary. The Linux kernel uses red-black trees all over -- the Completely Fair Scheduler keeps runnable tasks in one (keyed by virtual runtime, so the leftmost node is always the next task to run), and the virtual-memory subsystem indexes memory regions with them. In C++, std::map and std::set are red-black trees in every mainstream standard library implementation. Java's TreeMap and TreeSet are red-black trees, and since Java 8 even HashMap converts an over-full hash bucket into a little red-black tree to bound worst-case collision cost. The .NET SortedDictionary is one too. Anywhere you have seen an "ordered map" that lives in memory and promises log-time everything, odds are overwhelming a red-black tree is underneath.

The interesting contrast with episode 108 is which side of the fence each structure fell on. Databases and filesystems -- data on disk, range scans everywhere -- chose B-trees. In-memory ordered maps in language runtimes and kernels chose red-black trees. Same balancing idea, same B-tree ancestry, split by whether the expensive operation is a disk seek (favours fat nodes) or a pointer dereference (favours the leaner binary node with lower per-op constants). That fork is worth remembering the next time you pick an ordered container.

How this compares to C, Rust, and Go

In C, the classic red-black tree is the notorious data-structure-interview boss -- the CLRS version with parent pointers, sentinel nodes, and a fix-up routine with five cases and their mirror images is famously easy to get subtly wrong, and a miscoloured node produces a tree that is still a valid BST (so it passes shallow tests) but silently unbalanced. The Linux kernel ships a battle-tested rbtree.h precisely so nobody has to rewrite it. The recursive LLRB we built here is the antidote: no parent pointers, no sentinels, three fix-up lines. It is slightly slower per operation than a hand-tuned iterative version, but it fits on a page and you can actually prove it correct.

In Rust, a red-black tree is the structure you would not hand-write if you can avoid it -- the parent-pointer classic collides head-on with the borrow checker's hatred of mutable aliasing (the same wall the doubly linked list hit in episode 106, sending it into Rc<RefCell<>> or unsafe). Notably the Rust standard library sidesteps the whole fight by making BTreeMap its ordered map rather than a red-black tree -- a deliberate choice for cache behaviour and for ownership sanity. The recursive LLRB, with its strictly parent-to-child pointers, ports to safe Rust far more pleasantly than the classic ever could, exactly because there are no back-references to alias.

In Go, as with the B-tree, the standard library gives you an unordered hash map and nothing sorted, so an ordered map is a third-party package. Some reach for a red-black tree, others for a B-tree; the popular google/btree bet on the B-tree for cache reasons, which tells you where the informed money goes for in-memory ordered maps at scale. Our Zig version, with comptime T monomorphised inline and no garbage collector chasing the pointer-heavy internal nodes, gives you the red-black tree with zero boxing and zero collector tax -- the same story that has run through every structure in this stretch of the series.

Exercises

Add min(self: *Self) ?T and max(self: *Self) ?T. Unlike the B-tree, a red-black tree is a plain binary tree, so the minimum is the leftmost node (descend left until it is null) and the maximum the rightmost. Handle the empty tree, and test both against a scrambled batch of insertions by comparing to the first and last elements of a sorted copy.
Write a height(self: *Self) usize returning the number of levels, and a test that inserts a few hundred sequential integers -- the worst case for a naive BST -- then asserts the height stays at or below 2 * log2(n) + 1. This is the concrete proof that the colour rules did their job: a plain BST fed sorted input would degrade to height n, and your assertion is what catches the difference.
The hard one: implement deleteMin(self: *Self) and then full delete(self: *Self, key: T) bool for the LLRB. Deletion is the fiddly half of red-black trees just as it was for the B-tree, and Sedgewick's LLRB deletion is built from two helpers, moveRedLeft and moveRedRight, that push a red link down the tree ahead of the descent so the node you eventually remove is never a lone black leaf -- the binary-side echo of the B-tree's "ensure a child has enough keys before descending". After each delete, assert blackHeight is still non-negative, the in-order walk is still sorted, and std.testing.allocator reports zero leaks.

Where this is heading

Stand back and look at the whole arc. The skip list balanced with randomness. The B-tree balanced with a strict fatness rule and split-on-descent. The red-black tree took that exact B-tree rule and folded it onto a binary node using a single colour bit and O(1) rotations. Three structures, one recurring question -- "keep an ordered collection fast while it mutates" -- answered three ways, and the last two turned out to be the same answer viewed through different glass.

But every one of these has quietly assumed the same thing about keys: that the only operation you can do with a key is compare two of them, less-than or not, and that comparison costs O(1). What if that assumption is wrong? What if your keys are strings, or IP addresses, or byte sequences, where a single comparison already walks character by character -- and where two keys sharing a long common prefix waste that walk over and over on every lookup? There is a whole family of structures that throw out comparison entirely and instead navigate by the pieces of the key itself, one character or one bit at a time, so that a shared prefix is stored and traversed exactly once. That shift -- from comparing whole keys to spelling them out -- opens a different door, and it is the one we walk through next. One node at a time, we keep climbing.

Thanks for reading, and I'll see you in the next one!

@scipio

Leave Learn Zig Series (#109) - Red-Black Trees to:

Written by scipio

Does it matter who's right, or who's left?

Best Posts From scipio

We have not curated any of scipio's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.

Learn Zig Series (#109) - Red-Black Trees