inter in internet, interval and internal gets stored and walked exactly once, which is the entire reason the structure exists and where the name "prefix tree" comes from;insert, contains, and a startsWith prefix test that is the operation no hash map or balanced tree can give you cheaply;R at compile time and how the error union turns "that character is out of range" from a lurking segfault into a value the caller must handle;R-way branching inside real databases) and the sharp memory cost that keeps them from being the default;[]const u8 we walk byte by byte;Learn Zig Series):Episode 109 closed on a question I planted deliberately, and I want to open on it before we touch a single line of code. Every ordered structure in this run of the series -- the skip list, the B-tree, the red-black tree -- was built on one silent assumption: that the only thing you are allowed to do with a key is compare it to another key, less-than or not, and that the comparison costs O(1). For integers that is honest. For strings it is a small lie we all agreed to ignore. Comparing "international" to "internationalize" is not one operation -- it is a character-by-character march that only diverges at the fourteenth letter. Store a few thousand words that all begin with inter in a red-black tree and every single lookup re-walks that shared inter prefix, over and over, burning the same five comparisons before it ever reaches the part of the word that actually distinguishes anything. The trie is what you get when you refuse to keep paying that tax.
But first, the debt from episode 109 -- three exercises, and the last of them was the fiddly one.
Exercise 1 -- min and max. A red-black tree, unlike the B-tree, is a plain binary search tree wearing colours, so there is no fat-node cleverness to it: the smallest key is the leftmost node and the largest is the rightmost. Descend left until it is null, or right until it is null, and read off the key. Handle the empty tree by returning null.
// Add inside RedBlackTree(comptime T, comptime lessThan). A red-black tree is still a BST,
// so min is the far-left node and max the far-right -- colour is irrelevant to ordering.
fn min(self: *Self) ?T {
var node = self.root orelse return null;
while (node.left) |l| node = l;
return node.key;
}
fn max(self: *Self) ?T {
var node = self.root orelse return null;
while (node.right) |r| node = r;
return node.key;
}
The insight is that the colour bits govern balance, never order -- the in-order arrangement of a red-black tree is identical to a naive BST built on the same keys, so the extremes sit exactly where they would in any BST, at the two ends of the spine.
Exercise 2 -- height and the balance assertion. Height needs the max of the two subtrees plus one, so this one genuinely recurses (the B-tree could measure a single spine because every leaf sat at the same depth -- a red-black tree's leaves do not, the reds add slack). The payoff is the test: feed it sorted input, the classic worst case that turns a naive BST into a linked list, and assert the height stays under 2 * log2(n) + 1.
fn height(self: *Self) usize {
return nodeHeight(self.root);
}
fn nodeHeight(node: ?*Node) usize {
const n = node orelse return 0;
const lh = nodeHeight(n.left);
const rh = nodeHeight(n.right);
return 1 + @max(lh, rh);
}
test "red-black tree stays balanced on sorted input" {
var tree = RedBlackTree(u32, u32Less).init(std.testing.allocator);
defer tree.deinit();
var i: u32 = 0;
while (i < 1000) : (i += 1) try tree.insert(i); // sorted -> naive BST's nightmare
// 2*log2(1000) is about 20; a naive BST would be height 1000 here.
const log2n = std.math.log2_int(usize, tree.len);
try std.testing.expect(tree.height() <= 2 * log2n + 1);
}
This is the concrete proof the colour rules did their job. A plain BST fed 0,1,2,...,999 degrades to height 1000 -- a straight chain -- and this assertion is exactly the line that catches the difference.
Exercise 3 -- the hard one: delete for the LLRB. Deletion is the fiddly half of red-black trees, same as it was for the B-tree, and Sedgewick's left-leaning version handles it with two helpers -- moveRedLeft and moveRedRight -- that push a red link ahead of the descent so the node we eventually unlink is never a lone black leaf (removing one of those would break the black-height in one stroke). It is the binary-side echo of episode 108's "make sure a child has enough keys before you descend into it". Note the flipColors used here toggles all three colours rather than hard-setting them, because deletion runs it both to split and to merge. Here is the whole thing, slotting into the RedBlackTree from episode 109 and reusing its rotateLeft, rotateRight, isRed, and contains.
// flipColors for deletion: TOGGLE all three, so the same helper serves split and merge.
fn flip(h: *Node) void {
h.color = if (h.color == .red) .black else .red;
h.left.?.color = if (h.left.?.color == .red) .black else .red;
h.right.?.color = if (h.right.?.color == .red) .black else .red;
}
// balance: the same three fix-ups as insert, reused after every delete step on the way up.
fn balance(h: *Node) *Node {
var x = h;
if (isRed(x.right) and !isRed(x.left)) x = rotateLeft(x);
if (isRed(x.left) and isRed(x.left.?.left)) x = rotateRight(x);
if (isRed(x.left) and isRed(x.right)) flip(x);
return x;
}
// moveRedLeft: about to descend left into a node with no spare red -- borrow one first.
fn moveRedLeft(h: *Node) *Node {
var x = h;
flip(x);
if (isRed(x.right.?.left)) {
x.right = rotateRight(x.right.?);
x = rotateLeft(x);
flip(x);
}
return x;
}
// moveRedRight: mirror image, ahead of a right descent.
fn moveRedRight(h: *Node) *Node {
var x = h;
flip(x);
if (isRed(x.left.?.left)) {
x = rotateRight(x);
flip(x);
}
return x;
}
fn minNode(node: *Node) *Node {
var n = node;
while (n.left) |l| n = l;
return n;
}
// deleteMin: unlink the smallest node, pushing reds left ahead of the descent.
fn deleteMin(self: *Self, h: *Node) ?*Node {
if (h.left == null) {
self.allocator.destroy(h); // the leftmost node is red here -- safe to drop
return null;
}
var x = h;
if (!isRed(x.left) and !isRed(x.left.?.left)) x = moveRedLeft(x);
x.left = self.deleteMin(x.left.?);
return balance(x);
}
fn deleteNode(self: *Self, h: *Node, key: T) ?*Node {
var x = h;
if (lessThan(key, x.key)) {
if (!isRed(x.left) and !isRed(x.left.?.left)) x = moveRedLeft(x);
x.left = self.deleteNode(x.left.?, key);
} else {
if (isRed(x.left)) x = rotateRight(x);
if (!lessThan(x.key, key) and x.right == null) {
self.allocator.destroy(x); // found it at a leaf
return null;
}
if (!isRed(x.right) and !isRed(x.right.?.left)) x = moveRedRight(x);
if (!lessThan(x.key, key)) {
// key == x.key: overwrite with successor, then delete that successor
x.key = minNode(x.right.?).key;
x.right = self.deleteMin(x.right.?);
} else {
x.right = self.deleteNode(x.right.?, key);
}
}
return balance(x);
}
// public entry point: no-op if absent, then keep the root black.
fn delete(self: *Self, key: T) void {
if (!self.contains(key)) return;
if (!isRed(self.root.?.left) and !isRed(self.root.?.right))
self.root.?.color = .red;
self.root = self.deleteNode(self.root.?, key);
self.len -= 1;
if (self.root) |r| r.color = .black;
}
That is a genuine handful, and it is exactly why deletion is the part of red-black trees people quietly avoid. The load-bearing trick is worth naming once more: we never descend into a black-only child. moveRedLeft and moveRedRight guarantee a red link is waiting where we are about to step, so the node we finally unlink is red and removing it costs the black-height nothing. Test it by deleting keys in scrambled order and, after each one, asserting blackHeight(tree.root) != -1 (the checker from episode 109), that the in-order walk is still sorted, and that std.testing.allocator reports zero leaks. Debt paid -- now to today's structure, which happily has none of this deletion pain.
Here is the whole trie in a sentence. Instead of storing keys in nodes and comparing them, you store the key along the path from the root, one character per edge, and a node is nothing but a fork in the road. The word cat is not sitting in some node -- it is the path root -> c -> a -> t, and the node at the end carries a single flag saying "yes, a word ends here". The word car shares the first two edges (c, a) and diverges only at the third. That shared ca is stored once, walked once, and every word beginning with ca hangs off it. That is why it is called a prefix tree: the tree structure literally is the set of shared prefixes.
The consequences fall straight out of that picture, and they are the reason the trie earns a chapter of its own:
cat you follow three edges. It does not matter whether the trie holds three words or three million; a three-letter lookup is three hops. Compare that to the red-black tree's O(log n) comparisons, each of which is itself a character walk for strings. The trie's cost depends on the key, never on the collection.car?" is just "can I walk the c, a, r edges without falling off?". No other structure we have built gives you that -- a hash map scatters car, card, cart to three unrelated buckets with no notion that they are related at all.The price -- and there is always a price -- is memory, and we will be honest about it later. For now, let's build one.
I'll build the classic R-way trie, where every node holds an array of R child pointers, one slot per possible character. To keep the first pass concrete I'll fix the alphabet to lowercase a-z, so R = 26 and the slot for a character c is simply c - 'a'. Each node needs only that array and a single boolean -- is_word -- marking whether the path to this node spells a complete key. Notice what is not here: no key field, no colour, no balance bookkeeping. The node is astonishingly dumb, which is the point; all the intelligence lives in the shape of the tree.
const std = @import("std");
const R: usize = 26; // lowercase a-z; the slot for byte c is (c - 'a')
const Node = struct {
// one child slot per possible next character; null means "no word goes that way"
children: [R]?*Node = [_]?*Node{null} ** R,
// true if the path from the root TO this node spells a complete stored word
is_word: bool = false,
};
const Trie = struct {
const Self = @This();
root: ?*Node = null,
allocator: std.mem.Allocator,
len: usize = 0, // number of distinct words stored
fn init(allocator: std.mem.Allocator) Self {
return .{ .root = null, .allocator = allocator, .len = 0 };
}
fn newNode(self: *Self) !*Node {
const n = try self.allocator.create(Node);
n.* = .{}; // all children null, is_word false -- the struct defaults do the work
return n;
}
};
That [_]?*Node{null} ** R is Zig's array-repeat syntax doing the tedious work: it builds a 26-element array with every slot null, at comptime, so a fresh node starts life as a clean fork with no roads taken. The n.* = .{} in newNode leans on those struct defaults -- one line zeroes the whole node. Back in episode 8 we fussed over memory layout; here the layout is 26 pointers laid end to end, and we will come back to what that costs.
Insertion is a walk. Start at the root, and for each character of the word, look at the matching child slot -- if it is empty, create a node there; either way, step into it. When the characters run out, you are standing on the node that represents the whole word, so flip its is_word flag. The only bookkeeping is bumping len when the flag was not already set, so inserting cat twice counts once (set semantics, exactly like our earlier trees).
fn insert(self: *Self, word: []const u8) !void {
if (self.root == null) self.root = try self.newNode();
var node = self.root.?;
for (word) |c| {
const idx = c - 'a'; // assumes lowercase; the checked version comes next
if (node.children[idx] == null) node.children[idx] = try self.newNode();
node = node.children[idx].?;
}
if (!node.is_word) { // count a genuinely new word only
node.is_word = true;
self.len += 1;
}
}
Lookup splits into two questions that share almost all their code. contains asks "is this exact word stored?" and startsWith asks "does any stored word begin with this?". Both walk the characters the same way; they differ only in what they check at the end. So I factor the walk into a private find that returns the node you land on (or null if you fall off an edge), and the two public calls read the answer off it.
// walk the path; return the node the last character lands on, or null if the path breaks.
fn find(self: *Self, key: []const u8) ?*Node {
var node = self.root orelse return null;
for (key) |c| {
node = node.children[c - 'a'] orelse return null; // fell off -> not present
}
return node;
}
fn contains(self: *Self, word: []const u8) bool {
const node = self.find(word) orelse return false;
return node.is_word; // path exists, but is it a WHOLE word or just a prefix?
}
fn startsWith(self: *Self, prefix: []const u8) bool {
return self.find(prefix) != null; // the path existing IS the answer
}
The distinction between those two return lines is the entire soul of a prefix tree. After walking car, find lands on a real node -- so startsWith("car") is true whether or not car itself was ever inserted. But contains("car") demands that node's is_word be set. Store card and cart without car, and the car node exists as a mere junction, is_word false -- a prefix that is not itself a word. That one boolean is what separates "a word ends here" from "the road merely passes through".
The code above has a lurking landmine you may have spotted: c - 'a'. Feed it an uppercase letter, a space, or a digit and the index blows past 25, indexing the children array out of bounds -- in a safe build Zig panics, in a release-fast build it is undefined behaviour reading whatever memory sits past the array. In stead of trusting every caller to pre-sanitise input, we make the type system carry that guarantee. A checked index returns an error union, and Zig then refuses to compile any caller that ignores the failure -- the same "errors are values you must handle" discipline we leaned on all the way back in episode 4.
const TrieError = error{InvalidCharacter};
// The only place the a-z assumption lives. Every walk goes through here now, so an out-of-
// range byte becomes a handled error at the boundary instead of a segfault deep in a loop.
fn indexOf(c: u8) TrieError!usize {
if (c < 'a' or c > 'z') return TrieError.InvalidCharacter;
return c - 'a';
}
fn insertChecked(self: *Self, word: []const u8) !void {
if (self.root == null) self.root = try self.newNode();
var node = self.root.?;
for (word) |c| {
const idx = try indexOf(c); // caller MUST propagate; the compiler enforces it
if (node.children[idx] == null) node.children[idx] = try self.newNode();
node = node.children[idx].?;
}
node.is_word = true;
}
And comptime lets us stop hard-coding the alphabet at all. The radix R is a policy decision -- 26 for lowercase, 256 for arbitrary bytes, 16 if you index a nibble at a time -- and it belongs in a comptime parameter exactly like the element type of every generic we built since episode 14. fn Trie(comptime R: usize, comptime indexOf: fn (u8) TrieError!usize) type monomorphises a purpose-built trie for each alphabet, the child array sized [R]?*Node with zero runtime cost, and the whole family of tries -- byte trie, DNA trie over ACGT, lowercase word trie -- falls out of one definition. This is the through-line of the entire series: Zig pushes the parts that never change at runtime into comptime, and what is left is lean.
Now the operation that sells the whole structure. Given a prefix, list every stored word that starts with it -- the machinery behind every search box that finishes your sentence. It is two moves. First, find the node at the end of the prefix (episode's find, unchanged). Then do a depth-first walk from there, and every time you hit a node with is_word set, you have spelled a complete word: emit the prefix plus the characters accumulated along the way. Because we visit children in slot order (0 = a up to 25 = z), the words come out alphabetically sorted with no extra work.
// Depth-first walk from `node`, with `path` holding the characters spelled since the prefix.
// Every is_word node emits (prefix ++ path) as a freshly owned copy the caller must free.
fn collect(
self: *Self,
node: *Node,
prefix: []const u8,
path: *std.ArrayList(u8),
out: *std.ArrayList([]const u8),
) !void {
if (node.is_word) {
var word = std.ArrayList(u8).init(self.allocator);
try word.appendSlice(prefix);
try word.appendSlice(path.items);
try out.append(try word.toOwnedSlice()); // caller owns each returned word
}
for (node.children, 0..) |child, i| {
if (child) |c| {
try path.append(@as(u8, @intCast(i)) + 'a'); // slot i is character 'a' + i
try self.collect(c, prefix, path, out);
_ = path.pop(); // backtrack: undo this character before trying the next slot
}
}
}
fn autocomplete(self: *Self, prefix: []const u8) ![][]const u8 {
var out = std.ArrayList([]const u8).init(self.allocator);
const start = self.find(prefix) orelse return out.toOwnedSlice(); // no matches
var path = std.ArrayList(u8).init(self.allocator);
defer path.deinit();
try self.collect(start, prefix, &path, &out);
return out.toOwnedSlice();
}
The path.append then path.pop pair is the backtracking heartbeat of every DFS: push the character as you go down a slot, pop it as you come back up, so path always spells the exact route from the prefix node to wherever you currently stand. Try this against a red-black tree and feel the difference -- there, "all words starting with car" means an in-order traversal plus a manual filter over the whole tree; here it is a walk over precisely the subtree that is the answer, touching not one node that fails the prefix.
Same rule as every allocating structure since episode 7 -- we called create, so we owe a destroy, and there is no garbage collector coming to bail us out. Teardown is a post-order walk: free all of a node's children before the node itself, so you never destroy a parent while its children still dangle off it.
fn freeNode(self: *Self, node: ?*Node) void {
const n = node orelse return;
for (n.children) |child| self.freeNode(child); // free every subtree first
self.allocator.destroy(n); // then the node itself
}
fn deinit(self: *Self) void {
self.freeNode(self.root);
self.root = null;
}
The test earns its keep by pinning down the one behaviour that separates a trie from every other set -- the prefix logic, and specifically the case of a prefix that exists as a junction but is not itself a stored word. We lean on std.testing.allocator (episode 12) so any node freeNode forgets fails the test automatically.
test "trie: membership, prefixes, and no leaks" {
var trie = Trie.init(std.testing.allocator);
defer trie.deinit(); // testing.allocator flags any node freeNode misses
const words = [_][]const u8{ "car", "card", "care", "cart", "dog", "do" };
for (words) |w| try trie.insert(w);
try std.testing.expectEqual(@as(usize, words.len), trie.len);
// exact membership
try std.testing.expect(trie.contains("care"));
try std.testing.expect(!trie.contains("ca")); // a prefix, but never inserted as a word
try std.testing.expect(!trie.contains("carts")); // path falls off the end
// the payoff query: prefixes that are junctions, not words
try std.testing.expect(trie.startsWith("ca")); // true even though "ca" is not a word
try std.testing.expect(trie.startsWith("do"));
try std.testing.expect(!trie.startsWith("z"));
// "do" is BOTH a word and a prefix of "dog" -- the is_word flag settles it
try std.testing.expect(trie.contains("do"));
try std.testing.expect(trie.startsWith("do"));
}
The !trie.contains("ca") line paired with trie.startsWith("ca") being true is the assertion I would defend hardest in review -- it is the whole reason is_word exists. And the do/dog pair proves the other half: one node can legitimately be a complete word and a stepping stone to a longer one at the same time. A structure that conflated those two would pass a sloppy test and quietly corrupt any autocomplete built on top of it.
Time is the trie's showcase and I won't undersell it: contains, insert, and startsWith are all O(k) in the key length, dead independent of how many keys you store. A hash map is also roughly O(k) (you must hash all k bytes), but the hash then scatters related keys to unrelated buckets, so it cannot answer prefix questions at all. A balanced tree is O(k log n), the extra log n factor being the comparisons, each itself a character walk. For prefix work, nothing else is in the same postcode.
The cost is memory, and it is steep for the R-way version. Every node carries R pointers whether it uses them or not -- at R = 26 that is 26 times 8 bytes, 208 bytes plus the flag, for a node that might have a single child. Push the alphabet to full bytes (R = 256) for arbitrary strings and each node balloons to two kilobytes, most of it null. A trie holding a few long, unrelated keys can waste staggering amounts of space on empty slots. This is the honest reason the trie is a specialist, not a default container.
The fixes are a family worth knowing by name. Swap the fixed [R]?*Node array for a small hash map of children and each node stores only its live edges, trading a slice of speed and cache-locality for a big cut in wasted memory -- the standard move for large alphabets. Go further and compress chains: any run of single-child nodes (the nter in a trie holding only internet) collapses into one node holding the whole substring, which is the radix tree (a.k.a. Patricia trie) that powers real IP routing tables and the Linux kernel's page cache. And the ternary search trie stores three pointers per node instead of R, landing between a trie and a BST on both axes. We built the plain R-way version because it is the one where the idea is naked; every optimisation above is a memory-for-something trade layered on this same skeleton.
The reach is wider than the fat-node trees, just aimed at a different problem. Autocomplete and spell-checkers are the poster child -- every phone keyboard, every search bar, every IDE completion popup is walking a trie (usually a compressed one) to turn your three typed letters into a ranked list of continuations. IP routing is the giant: a router matching a packet's destination against thousands of CIDR prefixes is doing longest-prefix-match, and the radix-tree form of the trie is the classic structure for it -- the nter-collapsing compression is not a nicety there, it is what makes a wire-speed routing table fit in cache. Full-text search engines index terms in trie-like structures so a wildcard query car* is a subtree walk. And the trie idea recurses inside other structures: the branching inside some hash-array-mapped tries (HAMTs), the way certain databases index string keys, even how a T9 phone keypad mapped digit sequences to words back in the day.
The contrast with the last three episodes is the sharpest yet. The skip list, B-tree, and red-black tree all answered "keep an ordered collection fast under mutation" by comparing whole keys. The trie answered a question those three cannot touch -- "find me everything sharing this prefix" -- by refusing to treat the key as an atom and walking its pieces instead. Different question, different tool. When your keys are strings and your queries are prefix-shaped, no amount of balancing a comparison tree competes.
In C, a trie is a pile of malloc'd nodes each holding an array of child pointers, and the perennial bugs are the two you would expect from that: forgetting to free an entire subtree on teardown (a leak the compiler will never warn you about), and off-by-one indexing when you map a character to a slot without bounds-checking it. There is no standard-library trie; everyone rolls their own, and the good ones spend most of their code on the compressed radix variant because the naive R-way memory blowup bites hard in C's manual world.
In Rust, the trie is a pleasant surprise -- one of the rare pointer structures that does not fight the borrow checker. The reason is exactly the shape: every pointer runs strictly parent-to-child, root-downward, with no back-references, so ownership is a clean tree and Box<Node> with each node owning its children just works, teardown handled by an automatic recursive Drop. Contrast the doubly linked list of episode 106 or the parent-pointer red-black tree, both of which needed Rc<RefCell<>> or unsafe precisely because of their back-edges. The one Rust gotcha is that a very deep trie can blow the stack during that recursive drop, so production crates flatten teardown into a loop. Large alphabets there usually reach for a HashMap<u8, Node> of children over a fixed array.
In Go, the idiom is map[byte]*Node for the children and the garbage collector handles teardown, so the code is short and the leaks are the GC's problem, not yours -- at the cost of chasing pointer-heavy nodes through a collector that has no idea they form a tree. Our Zig version sits where it always does: the child array sized by a comptime R, the element type monomorphised inline, an explicit allocator you can swap for an arena (episode 26) to make teardown a single bulk free instead of a per-node walk, and not one byte of garbage-collector tax. Same structure, but you can see every allocation and decide who pays for it.
remove(self: *Self, word: []const u8) bool that unsets a word's is_word flag and returns whether the word was present. Then make it prune: after clearing the flag, walk back up and free any node that now has no children and is not itself a word, so deleting the only word in a long chain reclaims the whole chain. Test that removing cart from {car, cart} leaves car findable, that startsWith("car") stays true, and that std.testing.allocator reports zero leaks after a delete-everything pass.countWordsWithPrefix(self: *Self, prefix: []const u8) usize returning how many stored words begin with the prefix -- the number that a search box shows next to "N results". Do it two ways and compare: first by walking the subtree and counting is_word nodes on demand, then by caching a subtree_words counter in each node that insert maintains, turning the query into O(k) with no subtree walk at all. Which one would you ship, and why does the answer depend on the read/write ratio?Trie as fn Trie(comptime R: usize, comptime indexOf: fn (u8) TrieError!usize) type so the alphabet is a compile-time parameter. Instantiate it three ways -- lowercase a-z, full bytes (R = 256), and a DNA trie over just ACGT (R = 4) -- and write a test that stores a handful of keys in each and round-trips them through autocomplete. Measure the node size (@sizeOf(Node)) for each R and confirm with your own eyes why R = 256 is the version you would never use without switching the children to a hash map.Step back and look at what a trie actually gives you, because the next door opens exactly where the trie's cost becomes unbearable. The trie stores its keys exactly -- it can hand every one of them back to you, sorted, spelled out edge by edge -- and it pays for that fidelity in memory that grows with every character of every key you insert. But turn the question sideways. Suppose you do not need to enumerate the keys, do not need them sorted, do not need prefixes -- suppose the only thing you ever ask is "have I seen this key before, yes or no?". A spam filter checking a URL against a billion known-bad ones. A database skipping a disk read for a row it can prove is absent. A crawler avoiding pages it already fetched. Storing every one of those keys exactly, in a trie or a hash set, costs memory proportional to the total data -- and at a billion keys that is a lot of RAM to answer a single yes-or-no.
What if you were willing to give something up? What if you could answer "definitely not present" with total certainty, and "probably present" with a tiny, tunable chance of being wrong -- and in exchange the whole structure was a fixed pinch of memory that does not grow with key length at all, just a bit array and a fistful of hash functions? That trade -- perfect recall of absence, a controlled sliver of doubt about presence, for a fraction of the space -- is a genuinely different way to think about a set, and it is the one we walk into next. One bit at a time, we keep climbing ;-)
Bedankt en tot de volgende keer!
@scipio