Implement a Red-Black Tree in Zig
Build a self-balancing red-black tree from scratch in Zig.
Introduction
30 Second Summary
Databases, file systems, and language runtimes all depend on balanced tree structures to keep lookups fast. Without balancing, a binary search tree can degrade into a linked list, turning O(log n) operations into O(n).
In this project, you will implement a red-black tree from scratch in Zig. You will build insertion, rotations, and a validation suite that proves your tree stays balanced after every operation.
What You'll Build
A complete red-black tree data structure in a single Zig file, with insertion, search, left/right rotations, and a test suite you run with zig test.
By the end of this project, you'll have:
- A working self-balancing red-black tree that maintains O(log n) performance on every insertion.
- Left and right rotation functions that restructure the tree without breaking parent-child links.
- A property validation function that programmatically checks all five red-black invariants after every operation.
- Secret Mission: Implement red-black tree deletion with the four-case fix-up algorithm.
Are there any prerequisites?
You need basic programming fundamentals like variables, functions, loops, and conditionals. No prior Zig or binary search tree experience is required.
Set Up the Project and Node Structure
A red-black tree is a pointer-heavy data structure. Every node points to its parent, left child, and right child. In Zig, you model these relationships using optional pointers and manage memory through an explicit allocator.
In this step, you will create the project directory, define the foundational types (a color enum, a node struct, and a tree struct), and run your first test to confirm everything compiles cleanly.
In this step, get ready to:
- Create the project directory and source file.
- Define the Color, Node, and RBTree types.
- Write and run a first test to verify the setup.
Create the project directory and file
You need a dedicated folder to hold the source file and a place for Zig's test runner to output its results.
- Move to your Desktop by running this command:
cd ~/Desktop- Create the project directory and move into it by running these commands:
mkdir rbtree
cd rbtree- Confirm the directory exists by running:
lsThe folder is empty for now. That is expected.
- Open the source file in Neovim by running:
nvim red_black_tree.zigWhat does this command do?
Running nvim red_black_tree.zig opens Neovim with a new buffer named red_black_tree.zig. The file does not exist on disk yet. It will be created the first time you save inside Neovim.
Define the Color enum and Node struct
Every node in a red-black tree carries a color (red or black) and pointers to its parent and two children. In Zig, nullable pointers are represented as ?*T which can hold either a valid pointer or null.
- In Neovim, type the following code at the top of the file:
const std = @import("std");
const testing = std.testing;
// Color property: every node is either red or black
pub const Color = enum {
red,
black,
};
// A single node in the red-black tree
pub const Node = struct {
key: i32,
color: Color,
left: ?*Node, // optional pointer to left child
right: ?*Node, // optional pointer to right child
parent: ?*Node, // optional pointer to parent
};What does this code do?
The first two lines import Zig's standard library and alias its testing namespace. You will use testing for assertions later.
The Color enum gives each node exactly two possible colors. The Node struct stores an integer key, its color, and three optional pointers. A value of null in any pointer field means "no child" or "no parent."
Define the RBTree struct
The tree struct holds a pointer to the root node and an allocator that it uses to create and destroy nodes. Zig does not have a garbage collector, so you must free every node you allocate.
- Below the Node struct, add the following code:
// The tree container: holds the root and manages memory
pub const RBTree = struct {
root: ?*Node,
allocator: std.mem.Allocator,
// Create an empty tree with the given allocator
pub fn init(allocator: std.mem.Allocator) RBTree {
return .{
.root = null,
.allocator = allocator,
};
}
// Free every node in the tree
pub fn deinit(self: *RBTree) void {
destroySubtree(self.allocator, self.root);
self.root = null;
}
// Recursively free all nodes in a subtree
fn destroySubtree(allocator: std.mem.Allocator, node: ?*Node) void {
if (node) |n| {
destroySubtree(allocator, n.left);
destroySubtree(allocator, n.right);
allocator.destroy(n);
}
}
};What does this code do?
The init function returns a tree with a null root and stores the allocator for later use. The deinit function walks the entire tree recursively and frees each node with allocator.destroy.
The if (node) |n| pattern unwraps an optional pointer. If node is not null, Zig binds the unwrapped value to n and runs the block. This is how you safely traverse nullable pointer chains in Zig.
Why explicit allocators?
Zig has no hidden allocations or garbage collector. Every allocation is visible in the source code because you pass the allocator explicitly. This makes memory usage predictable and testable.
In tests, std.testing.allocator is a special allocator that automatically detects memory leaks. If your deinit misses a node, the test fails.
Write and run the first test
Zig's built-in test framework lets you declare tests directly in your source file. The test runner compiles and executes every test block it finds.
- Below the closing }; of the RBTree struct, add this test:
test "tree initializes with null root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try testing.expect(tree.root == null);
}What does this code do?
This test creates a tree using the test allocator, then asserts that the root is null. The defer tree.deinit() line guarantees cleanup runs when the test block exits, even if an assertion fails.
If you forget to free a node later, the testing allocator will report a leak as a test failure. This gives you an automatic safety net for memory correctness.
- Save the file in Neovim by pressing Esc, then typing :w and pressing Enter.
- Open a terminal (or use a second terminal tab) and run the test suite:
zig test red_black_tree.zigYou should see output indicating all 1 tests passed.
Seeing a compile error?
- Check that the Node struct fields use ?*Node (with the question mark), not *Node. A bare pointer cannot be null in Zig.
- Make sure destroySubtree is defined inside the RBTree struct block, not outside it.
- Verify you are running the command from inside the rbtree directory where red_black_tree.zig lives.
Still stuck? Help me debug a compile error in my red-black tree Zig file.
✔️ Awesome, I've got everything!
Great. Double check you have saved red_black_tree.zig before moving on.
ⓧ I'd like to double check the full code
Here is the complete red_black_tree.zig at this point:
const std = @import("std");
const testing = std.testing;
pub const Color = enum {
red,
black,
};
pub const Node = struct {
key: i32,
color: Color,
left: ?*Node,
right: ?*Node,
parent: ?*Node,
};
pub const RBTree = struct {
root: ?*Node,
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) RBTree {
return .{
.root = null,
.allocator = allocator,
};
}
pub fn deinit(self: *RBTree) void {
destroySubtree(self.allocator, self.root);
self.root = null;
}
fn destroySubtree(allocator: std.mem.Allocator, node: ?*Node) void {
if (node) |n| {
destroySubtree(allocator, n.left);
destroySubtree(allocator, n.right);
allocator.destroy(n);
}
}
};
test "tree initializes with null root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try testing.expect(tree.root == null);
}Your tree skeleton compiles and passes its first test. Next up, you will implement insertion and search so the tree can actually hold data.
Implement BST Insertion and Search
Your tree can initialize and free memory, but it cannot store anything yet. A tree without insertion is just an empty shell.
In this step, you will write the two core operations every binary search tree needs: inserting a new node in the correct sorted position, and searching for a node by key. These form the foundation that rotations and fix-ups build on later.
In this step, get ready to:
- Implement a BST insert function that allocates and positions new nodes.
- Implement a search function that traverses the tree to find a key.
- Write tests that verify insertion and search work correctly together.
Write the insert function
Insertion into a binary search tree follows a simple rule: compare the new key against each node, go left if smaller, go right if larger, and attach the new node once you reach an empty spot.
- In red_black_tree.zig, find the closing }; of the RBTree struct (after the destroySubtree function).
- Add the following insert function just above that closing };:
pub fn insert(self: *RBTree, key: i32) !void {
// Allocate a new node on the heap, colored red
const new_node = try self.allocator.create(Node);
new_node.* = .{
.key = key,
.color = .red,
.left = null,
.right = null,
.parent = null,
};
// Walk down the tree to find the correct parent
var parent: ?*Node = null;
var current = self.root;
while (current) |c| {
parent = c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
// Attach the new node to its parent (or make it root)
new_node.parent = parent;
if (parent) |p| {
if (key < p.key) {
p.left = new_node;
} else {
p.right = new_node;
}
} else {
self.root = new_node;
}
}What does this code do?
The function has three sections that mirror the three phases of BST insertion.
- allocator.create(Node) allocates heap memory for a single Node. The try keyword propagates any allocation failure to the caller, which is why the return type is !void.
- The while (current) |c| loop unwraps the optional pointer on each iteration. When current becomes null, the loop exits and parent holds the node to attach under.
- If parent is null, the tree was empty, so the new node becomes the root.
- Save red_black_tree.zig.
- Confirm it still compiles by running:
zig test red_black_tree.zigYou should see your 1 existing test still passes. The new function compiles but nothing exercises it yet.
Seeing a compile error?
- Check that the insert function is inside the RBTree struct body (before the closing };), not outside it.
- Make sure new_node.* = .{ uses .* (dereference then assign) not just =.
- Verify there is a comma after each struct field inside the .{ ... } initializer.
Help me fix a compile error in my insert function
Write the search function
Search follows the same traversal logic as insert, but instead of attaching a node, it returns the node whose key matches.
- In red_black_tree.zig, add the search function directly below the insert function (still inside the RBTree struct):
pub fn search(self: *const RBTree, key: i32) ?*Node {
// Start at the root and walk down
var current = self.root;
while (current) |c| {
if (key == c.key) return c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
return null;
}What does this code do?
The return type ?*Node is an optional pointer. It returns either a valid pointer to the found node, or null if the key does not exist in the tree.
Notice self: *const RBTree instead of self: *RBTree. The const signals that search only reads the tree. It never modifies it.
- Save red_black_tree.zig.
- Run zig test red_black_tree.zig again to confirm it compiles cleanly.
Getting an unused function error?
Zig may warn about unused declarations. This resolves itself once you add tests that call search in the next substep.
Help me fix a Zig unused declaration error
Write tests for insert and search
Tests are your proof that the functions work. You will write two tests: one that inserts a single node and checks it becomes the root, and one that inserts multiple nodes and verifies search finds each one.
- Scroll to the bottom of red_black_tree.zig, after the existing test "tree initializes with null root" block.
- Add these two test blocks:
test "insert single node becomes black root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
// The first inserted node should become the root
try testing.expect(tree.root != null);
try testing.expect(tree.root.?.key == 10);
}
test "insert multiple nodes maintains BST ordering" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
// Every inserted key should be findable
try testing.expect(tree.search(10) != null);
try testing.expect(tree.search(5) != null);
try testing.expect(tree.search(15) != null);
// A key that was never inserted returns null
try testing.expect(tree.search(99) == null);
}What do these tests verify?
- The first test confirms that inserting into an empty tree makes that node the root, and that root.?.key unwraps the optional pointer and reads the key.
- The second test inserts three keys and uses search to prove each one landed in the tree. Searching for 99 (never inserted) returns null, proving search does not produce false positives.
- testing.allocator automatically detects memory leaks. If deinit fails to free all nodes, the test fails.
- Save red_black_tree.zig.
- Run the full test suite:
zig test red_black_tree.zigYou should see all 3 tests pass.
Tests failing?
- If a test reports a memory leak, check that defer tree.deinit() appears immediately after RBTree.init in each test.
- If search(99) does not return null, double-check that your search loop returns null at the bottom, outside the while block.
- If root.?.key panics, ensure insert sets self.root = new_node when parent is null.
Help me debug my failing insert/search tests
✔️ Awesome, I've got everything!
Great. Double check you have saved red_black_tree.zig and all 3 tests pass before moving on.
ⓧ I'd like to double check the full code
Here is the complete red_black_tree.zig file as it should look at the end of this step:
const std = @import("std");
const testing = std.testing;
pub const Color = enum {
red,
black,
};
pub const Node = struct {
key: i32,
color: Color,
left: ?*Node,
right: ?*Node,
parent: ?*Node,
};
pub const RBTree = struct {
root: ?*Node,
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) RBTree {
return .{
.root = null,
.allocator = allocator,
};
}
pub fn deinit(self: *RBTree) void {
destroySubtree(self.allocator, self.root);
self.root = null;
}
fn destroySubtree(allocator: std.mem.Allocator, node: ?*Node) void {
if (node) |n| {
destroySubtree(allocator, n.left);
destroySubtree(allocator, n.right);
allocator.destroy(n);
}
}
pub fn insert(self: *RBTree, key: i32) !void {
const new_node = try self.allocator.create(Node);
new_node.* = .{
.key = key,
.color = .red,
.left = null,
.right = null,
.parent = null,
};
var parent: ?*Node = null;
var current = self.root;
while (current) |c| {
parent = c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
new_node.parent = parent;
if (parent) |p| {
if (key < p.key) {
p.left = new_node;
} else {
p.right = new_node;
}
} else {
self.root = new_node;
}
}
pub fn search(self: *const RBTree, key: i32) ?*Node {
var current = self.root;
while (current) |c| {
if (key == c.key) return c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
return null;
}
};
test "tree initializes with null root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try testing.expect(tree.root == null);
}
test "insert single node becomes black root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try testing.expect(tree.root != null);
try testing.expect(tree.root.?.key == 10);
}
test "insert multiple nodes maintains BST ordering" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
try testing.expect(tree.search(10) != null);
try testing.expect(tree.search(5) != null);
try testing.expect(tree.search(15) != null);
try testing.expect(tree.search(99) == null);
}Your tree now stores and retrieves data correctly. Next up, you will implement left and right rotations. These are the mechanical building blocks that the fix-up algorithm uses to keep the tree balanced.
Implement Left and Right Rotations
Your tree can insert nodes and search for them, but it has no way to restructure itself. Rotations are the core mechanical operation that keeps a red-black tree balanced.
A rotation rearranges a parent-child pair without breaking BST ordering. In this step, you will implement left and right rotations that move nodes up and down the tree while carefully maintaining all parent pointers.
In this step, get ready to:
- Implement the left rotation function that promotes a node's right child.
- Implement the right rotation function as the mirror operation.
- Run the test suite to verify your rotations compile correctly.
Implement the left rotation
A left rotation on node x takes its right child y and promotes y into x's position. Node x becomes the left child of y, and y's old left subtree transfers to become x's new right subtree.
- In red_black_tree.zig, find the closing brace of the insert function inside the RBTree struct.
- Add the leftRotate function below it by copying this code:
fn leftRotate(self: *RBTree, x: *Node) void {
const y = x.right orelse return;
x.right = y.left;
if (y.left) |yl| {
yl.parent = x;
}
y.parent = x.parent;
if (x.parent) |p| {
if (x == p.left) {
p.left = y;
} else {
p.right = y;
}
} else {
self.root = y;
}
y.left = x;
x.parent = y;
}What does this code do?
The rotation has four phases that must happen in the correct order to avoid dangling pointers.
- const y = x.right orelse return; grabs the right child. If there is no right child, a left rotation is impossible, so the function returns early.
- x.right = y.left; transfers y's left subtree to x's right side, since y is about to move up.
- The parent-pointer updates (y.parent = x.parent and the conditional block) link y into x's old spot in the tree, updating the tree root if x was the root.
- y.left = x; x.parent = y; finishes by making x the left child of y.
Implement the right rotation
The right rotation is the exact mirror of left rotation. It takes a node y and promotes its left child x into y's position.
- Directly below the leftRotate function, add the rightRotate function:
fn rightRotate(self: *RBTree, y: *Node) void {
const x = y.left orelse return;
y.left = x.right;
if (x.right) |xr| {
xr.parent = y;
}
x.parent = y.parent;
if (y.parent) |p| {
if (y == p.left) {
p.left = x;
} else {
p.right = x;
}
} else {
self.root = x;
}
x.right = y;
y.parent = x;
}How does rightRotate mirror leftRotate?
Every left/right direction is swapped. Where leftRotate grabs x.right, rightRotate grabs y.left. Where leftRotate sets y.left = x, rightRotate sets x.right = y.
The parent-pointer update logic is identical in structure. This symmetry means once you understand one rotation, you understand both.
Run the tests to verify compilation
Your rotation functions are private helpers (fn instead of pub fn). They will be called by the insertFixup function you build in the next step.
- Save red_black_tree.zig in Neovim with :w.
- Run the test suite to confirm your new code compiles and existing tests still pass:
zig test red_black_tree.zig- You should see All 3 tests passed. in the output.
Why do the rotations not have their own test yet?
Rotations only make sense in the context of tree rebalancing. In the next step, you will wire insertFixup into insert, which calls these rotations automatically.
The ascending-insertion test in that step will prove rotations work correctly by verifying the tree restructures itself.
Seeing a compile error?
- Check that leftRotate and rightRotate are placed inside the RBTree struct, not outside it.
- Verify you used orelse return (not orelse null) since the function returns void.
- Make sure the pipe captures (|yl|, |xr|, |p|) match the variable names used inside their blocks.
Help me debug a compile error in my Zig rotation functions
✔️ Awesome, I've got everything!
Great. Double check you have saved red_black_tree.zig and that zig test shows all tests passing.
ⓧ I'd like to double check the full code
const std = @import("std");
const testing = std.testing;
pub const Color = enum {
red,
black,
};
pub const Node = struct {
key: i32,
color: Color,
left: ?*Node,
right: ?*Node,
parent: ?*Node,
};
pub const RBTree = struct {
root: ?*Node,
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) RBTree {
return .{
.root = null,
.allocator = allocator,
};
}
pub fn deinit(self: *RBTree) void {
destroySubtree(self.allocator, self.root);
self.root = null;
}
fn destroySubtree(allocator: std.mem.Allocator, node: ?*Node) void {
if (node) |n| {
destroySubtree(allocator, n.left);
destroySubtree(allocator, n.right);
allocator.destroy(n);
}
}
pub fn insert(self: *RBTree, key: i32) !void {
const new_node = try self.allocator.create(Node);
new_node.* = .{
.key = key,
.color = .red,
.left = null,
.right = null,
.parent = null,
};
var parent: ?*Node = null;
var current = self.root;
while (current) |c| {
parent = c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
new_node.parent = parent;
if (parent) |p| {
if (key < p.key) {
p.left = new_node;
} else {
p.right = new_node;
}
} else {
self.root = new_node;
}
}
fn leftRotate(self: *RBTree, x: *Node) void {
const y = x.right orelse return;
x.right = y.left;
if (y.left) |yl| {
yl.parent = x;
}
y.parent = x.parent;
if (x.parent) |p| {
if (x == p.left) {
p.left = y;
} else {
p.right = y;
}
} else {
self.root = y;
}
y.left = x;
x.parent = y;
}
fn rightRotate(self: *RBTree, y: *Node) void {
const x = y.left orelse return;
y.left = x.right;
if (x.right) |xr| {
xr.parent = y;
}
x.parent = y.parent;
if (y.parent) |p| {
if (y == p.left) {
p.left = x;
} else {
p.right = x;
}
} else {
self.root = x;
}
x.right = y;
y.parent = x;
}
pub fn search(self: *const RBTree, key: i32) ?*Node {
var current = self.root;
while (current) |c| {
if (key == c.key) return c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
return null;
}
};
test "tree initializes with null root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try testing.expect(tree.root == null);
}
test "insert single node becomes black root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try testing.expect(tree.root != null);
try testing.expect(tree.root.?.key == 10);
}
test "insert multiple nodes maintains BST ordering" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
try testing.expect(tree.search(10) != null);
try testing.expect(tree.search(5) != null);
try testing.expect(tree.search(15) != null);
try testing.expect(tree.search(99) == null);
}Your tree now has the mechanical tools it needs to restructure itself. Next up, you will implement the insertion fix-up algorithm that decides when and where to apply these rotations.
Implement Insertion Fix-up
Your tree can insert and rotate, but it has no idea when to rotate. Inserting a red node can create a red-red parent-child pair, violating the red-black property.
The insertion fix-up algorithm walks up the tree after every insert, inspecting uncle nodes to decide whether to recolor or rotate. It handles three cases per side, and the result is a tree that stays balanced no matter what order you insert keys.
In this step, get ready to:
- Implement the insertFixup function with all three fix-up cases.
- Wire insertFixup into the insert function.
- Write tests that prove rotations and recoloring happen correctly.
Implement the insertion fix-up algorithm
After inserting a red node, the only property that can be violated is the no-red-red rule. The fix-up walks up from the new node and applies one of three cases depending on the uncle's color and the node's position relative to its grandparent.
- In red_black_tree.zig, add the insertFixup function inside the RBTree struct, after the insert function. Copy the following code:
fn insertFixup(self: *RBTree, node: *Node) void {
var z = node;
while (z.parent) |p| {
if (p.color != .red) break;
const gp = p.parent orelse break;
if (p == gp.left) {
const uncle = gp.right;
if (uncle) |u| {
if (u.color == .red) {
// Case 1: uncle is red — recolor and move up
p.color = .black;
u.color = .black;
gp.color = .red;
z = gp;
continue;
}
}
if (z == p.right) {
// Case 2: z is inner child — rotate to make it outer
z = p;
self.leftRotate(z);
}
// Case 3: z is outer child — rotate grandparent
if (z.parent) |zp| {
zp.color = .black;
if (zp.parent) |zgp| {
zgp.color = .red;
self.rightRotate(zgp);
}
}
break;
} else {
// Mirror: parent is right child of grandparent
const uncle = gp.left;
if (uncle) |u| {
if (u.color == .red) {
// Case 1: uncle is red — recolor and move up
p.color = .black;
u.color = .black;
gp.color = .red;
z = gp;
continue;
}
}
if (z == p.left) {
// Case 2: z is inner child — rotate to make it outer
z = p;
self.rightRotate(z);
}
// Case 3: z is outer child — rotate grandparent
if (z.parent) |zp| {
zp.color = .black;
if (zp.parent) |zgp| {
zgp.color = .red;
self.leftRotate(zgp);
}
}
break;
}
}
// Root must always be black
if (self.root) |r| {
r.color = .black;
}
}What does this code do?
The fix-up loop only runs while the newly inserted node's parent is red (a violation). It checks which side the parent is on, then inspects the uncle.
- Case 1: The uncle is red. Recolor both parent and uncle to black, grandparent to red, then move z up to the grandparent and repeat.
- Case 2: The uncle is black and z is an inner child (right child of left parent). Rotate z's parent to convert into Case 3.
- Case 3: The uncle is black and z is an outer child. Recolor and rotate the grandparent. This restores the property in one rotation.
The final line forces the root to black, ensuring property 2 always holds regardless of how many recolorings propagated upward.
- Save red_black_tree.zig.
Seeing a compile error?
Make sure insertFixup is placed inside the RBTree struct (between its opening and closing braces). It uses self to call leftRotate and rightRotate, so it must be a method on the struct.
Also check that indentation uses spaces consistently. Zig is whitespace-insensitive, but mixing tabs and spaces can cause confusing alignment issues in Neovim.
Why is my insertFixup not compiling?
Wire insertFixup into the insert function
The fix-up function exists, but insert doesn't call it yet. Every insertion must end with a fix-up pass to restore the red-black properties.
- In red_black_tree.zig, find the end of the insert function. Locate this block:
new_node.parent = parent;
if (parent) |p| {
if (key < p.key) {
p.left = new_node;
} else {
p.right = new_node;
}
} else {
self.root = new_node;
}
}- Add self.insertFixup(new_node); as the last line before the closing brace of insert, so it looks like this:
new_node.parent = parent;
if (parent) |p| {
if (key < p.key) {
p.left = new_node;
} else {
p.right = new_node;
}
} else {
self.root = new_node;
}
self.insertFixup(new_node);
}- Save red_black_tree.zig.
Write tests that prove rebalancing works
The best way to confirm your fix-up works is to insert keys in an order that guarantees rotations. Inserting an ascending sequence (1, 2, 3, 4, 5) into a plain BST would create a right-leaning chain. A red-black tree rebalances, so the root should not be 1.
- First, update your existing "insert single node becomes black root" test. Find the test and add a color assertion so it matches this:
test "insert single node becomes black root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try testing.expect(tree.root != null);
try testing.expect(tree.root.?.key == 10);
// Verify the fix-up colors the root black
try testing.expect(tree.root.?.color == .black);
}Why check the root color?
Every new node starts as red. The fix-up's final line forces the root to black. This test confirms that single-node edge case is handled.
- Next, replace your existing "insert multiple nodes maintains BST ordering" test with this expanded version that inserts more keys:
test "insert multiple nodes maintains BST ordering" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
try tree.insert(3);
try tree.insert(7);
try testing.expect(tree.search(5) != null);
try testing.expect(tree.search(15) != null);
try testing.expect(tree.search(3) != null);
try testing.expect(tree.search(99) == null);
}- Now add these two new tests at the bottom of the file, after the existing tests:
test "ascending insertion triggers rotations" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(1);
try tree.insert(2);
try tree.insert(3);
try tree.insert(4);
try tree.insert(5);
// If the tree rebalanced, root cannot still be 1
try testing.expect(tree.root.?.key != 1);
}
test "insertion triggers recoloring" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
// Inserting 3 triggers Case 1 recoloring (uncle 15 is red)
try tree.insert(3);
}What do these tests prove?
- The ascending test inserts 1, 2, 3, 4, 5 in order. Without fix-up, the root stays at 1 with everything chaining right. With fix-up, rotations rebalance the tree so the root changes.
- The recoloring test inserts 3 into a tree where both children of 10 are red. This triggers Case 1 (uncle is red), which recolors without rotating.
- Save red_black_tree.zig and run the test suite:
zig test red_black_tree.zig- You should see all tests pass with no failures and no memory leaks detected.
Tests failing or leaking memory?
If a test reports a memory leak, your fix-up may be creating an orphaned node. Check that rotations properly update parent pointers in both directions.
If the ascending test fails (root is still 1), confirm that self.insertFixup(new_node) is actually called inside insert. Without the call, no rebalancing happens.
Help me debug my failing red-black tree tests.
✔️ Awesome, I've got everything!
Great. Double check you have saved red_black_tree.zig and all tests pass.
ⓧ I'd like to double check the full code
Here is the complete red_black_tree.zig at this point:
const std = @import("std");
const testing = std.testing;
pub const Color = enum {
red,
black,
};
pub const Node = struct {
key: i32,
color: Color,
left: ?*Node,
right: ?*Node,
parent: ?*Node,
};
pub const RBTree = struct {
root: ?*Node,
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) RBTree {
return .{
.root = null,
.allocator = allocator,
};
}
pub fn deinit(self: *RBTree) void {
destroySubtree(self.allocator, self.root);
self.root = null;
}
fn destroySubtree(allocator: std.mem.Allocator, node: ?*Node) void {
if (node) |n| {
destroySubtree(allocator, n.left);
destroySubtree(allocator, n.right);
allocator.destroy(n);
}
}
pub fn insert(self: *RBTree, key: i32) !void {
const new_node = try self.allocator.create(Node);
new_node.* = .{
.key = key,
.color = .red,
.left = null,
.right = null,
.parent = null,
};
var parent: ?*Node = null;
var current = self.root;
while (current) |c| {
parent = c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
new_node.parent = parent;
if (parent) |p| {
if (key < p.key) {
p.left = new_node;
} else {
p.right = new_node;
}
} else {
self.root = new_node;
}
self.insertFixup(new_node);
}
fn insertFixup(self: *RBTree, node: *Node) void {
var z = node;
while (z.parent) |p| {
if (p.color != .red) break;
const gp = p.parent orelse break;
if (p == gp.left) {
const uncle = gp.right;
if (uncle) |u| {
if (u.color == .red) {
p.color = .black;
u.color = .black;
gp.color = .red;
z = gp;
continue;
}
}
if (z == p.right) {
z = p;
self.leftRotate(z);
}
if (z.parent) |zp| {
zp.color = .black;
if (zp.parent) |zgp| {
zgp.color = .red;
self.rightRotate(zgp);
}
}
break;
} else {
const uncle = gp.left;
if (uncle) |u| {
if (u.color == .red) {
p.color = .black;
u.color = .black;
gp.color = .red;
z = gp;
continue;
}
}
if (z == p.left) {
z = p;
self.rightRotate(z);
}
if (z.parent) |zp| {
zp.color = .black;
if (zp.parent) |zgp| {
zgp.color = .red;
self.leftRotate(zgp);
}
}
break;
}
}
if (self.root) |r| {
r.color = .black;
}
}
fn leftRotate(self: *RBTree, x: *Node) void {
const y = x.right orelse return;
x.right = y.left;
if (y.left) |yl| {
yl.parent = x;
}
y.parent = x.parent;
if (x.parent) |p| {
if (x == p.left) {
p.left = y;
} else {
p.right = y;
}
} else {
self.root = y;
}
y.left = x;
x.parent = y;
}
fn rightRotate(self: *RBTree, y: *Node) void {
const x = y.left orelse return;
y.left = x.right;
if (x.right) |xr| {
xr.parent = y;
}
x.parent = y.parent;
if (y.parent) |p| {
if (y == p.left) {
p.left = x;
} else {
p.right = x;
}
} else {
self.root = x;
}
x.right = y;
y.parent = x;
}
pub fn search(self: *const RBTree, key: i32) ?*Node {
var current = self.root;
while (current) |c| {
if (key == c.key) return c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
return null;
}
};
test "tree initializes with null root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try testing.expect(tree.root == null);
}
test "insert single node becomes black root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try testing.expect(tree.root != null);
try testing.expect(tree.root.?.key == 10);
try testing.expect(tree.root.?.color == .black);
}
test "insert multiple nodes maintains BST ordering" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
try tree.insert(3);
try tree.insert(7);
try testing.expect(tree.search(5) != null);
try testing.expect(tree.search(15) != null);
try testing.expect(tree.search(3) != null);
try testing.expect(tree.search(99) == null);
}
test "ascending insertion triggers rotations" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(1);
try tree.insert(2);
try tree.insert(3);
try tree.insert(4);
try tree.insert(5);
try testing.expect(tree.root.?.key != 1);
}
test "insertion triggers recoloring" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
try tree.insert(3);
}Your tree now self-balances on every insertion. Next up, you'll build a validation function that programmatically proves all five red-black properties hold after every operation.
Add Property Validation and Complete the Test Suite
Your red-black tree can insert nodes and rebalance itself. But how do you prove it is correct? A tree that looks balanced might still violate the red-black invariants in subtle ways that only surface with specific insertion sequences.
In this step, you will build a validation function that programmatically checks all five red-black properties after every operation. This turns your test suite from "did it crash?" into "is it provably correct?"
In this step, get ready to:
- Implement a validate function that checks root color, red-red violations, and black-height balance.
- Implement a BST ordering check to verify keys are correctly positioned.
- Write a comprehensive test that validates correctness after every single insertion in a 10-key sequence.
Implement the validate function and color property checks
A valid red-black tree must satisfy three color-related properties: the root is black, no red node has a red child, and every path from the root to a null leaf passes through the same number of black nodes.
You will implement three functions together. The main validate function orchestrates the checks, and two recursive helpers do the actual tree traversal.
- In red_black_tree.zig, find the closing brace of the search function. Add the following three functions below it (still inside the RBTree struct):
pub fn validate(self: *const RBTree) bool {
// An empty tree is valid by definition
const root = self.root orelse return true;
// Property: root must be black
if (root.color != .black) return false;
// Property: no red node has a red child
if (!checkNoRedRed(root)) return false;
// Property: all root-to-leaf paths have equal black-height
if (checkBlackHeight(root) == null) return false;
// Property: BST ordering is maintained
if (!isBSTValid(root, null, null)) return false;
return true;
}
fn checkNoRedRed(node: ?*Node) bool {
const n = node orelse return true;
// If this node is red, neither child can be red
if (n.color == .red) {
if (n.left) |l| {
if (l.color == .red) return false;
}
if (n.right) |r| {
if (r.color == .red) return false;
}
}
// Recurse into both subtrees
return checkNoRedRed(n.left) and checkNoRedRed(n.right);
}
fn checkBlackHeight(node: ?*Node) ?usize {
// Null leaves count as 1 black node
const n = node orelse return 1;
// Get black-height of left and right subtrees
const left_bh = checkBlackHeight(n.left) orelse return null;
const right_bh = checkBlackHeight(n.right) orelse return null;
// If they differ, the tree is invalid
if (left_bh != right_bh) return null;
// Add 1 to height if this node is black
const increment: usize = if (n.color == .black) 1 else 0;
return left_bh + increment;
}What does this code do?
validate is the entry point that runs each property check in sequence. If any check fails, it returns false immediately.
checkNoRedRed recurses through every node. When it finds a red node, it inspects both children. If either child is also red, the tree is invalid.
checkBlackHeight uses Zig's optional return type (?usize) cleverly. It returns null to signal an imbalanced path, which propagates up via orelse return null. A valid subtree returns its black-height as a number.
- Save red_black_tree.zig.
You won't see a change yet. The validate function references isBSTValid which you will add next.
Implement BST ordering validation
A red-black tree is also a binary search tree. Every node's key must be greater than all keys in its left subtree and less than all keys in its right subtree.
- Add the isBSTValid function directly below checkBlackHeight (still inside the RBTree struct):
fn isBSTValid(node: ?*Node, min: ?i32, max: ?i32) bool {
const n = node orelse return true;
// Check that this node's key is within the allowed bounds
if (min) |m| {
if (n.key <= m) return false;
}
if (max) |m| {
if (n.key >= m) return false;
}
// Left subtree keys must be less than this key
// Right subtree keys must be greater than this key
return isBSTValid(n.left, min, n.key) and isBSTValid(n.right, n.key, max);
}What does this code do?
isBSTValid uses a min/max bounds technique. As it recurses left, it narrows the maximum allowed key. As it recurses right, it narrows the minimum. If any node violates its bounds, the BST property is broken.
The ?i32 optional parameters start as null (no bound) at the root and tighten as the recursion descends.
- Save red_black_tree.zig. The file should now compile without errors, but you have not called validate from any tests yet.
Seeing a compile error?
Make sure all three new functions (validate, checkNoRedRed, checkBlackHeight, isBSTValid) are inside the RBTree struct's closing };. If they are outside it, Zig cannot resolve the Node type reference.
Help me fix a compile error in my validate functions
Write the comprehensive test suite
Now you will wire validate into every existing test so that each test proves correctness, not just the absence of crashes. Then you will add a comprehensive test that exercises all fix-up cases.
- In the "tree initializes with null root" test, find this line:
try testing.expect(tree.root == null);- Add this line directly below it:
try testing.expect(tree.validate());- Add the same try testing.expect(tree.validate()); line to the remaining four tests. Place it after all insertions but before any other assertions.
Where exactly does validate go in each test?
- "insert single node becomes black root": after the three existing assertions about root, key, and color.
- "insert multiple nodes maintains BST ordering": after the last insert and before the search assertions.
- "ascending insertion triggers rotations": after the last insert and before the root key assertion.
- "insertion triggers recoloring": after the last insert, as the final line of the test.
Now add the comprehensive test. This sequence is specifically chosen to trigger all three insertion fix-up cases (recoloring, left rotation, and right rotation).
- Add this new test block after the "insertion triggers recoloring" test (outside the RBTree struct, at the bottom of the file):
test "large descending sequence validates after each insert" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
// This sequence triggers all fix-up cases
const keys = [_]i32{ 41, 38, 31, 12, 19, 8, 7, 5, 2, 1 };
for (keys) |key| {
try tree.insert(key);
// Prove correctness after every single insertion
try testing.expect(tree.validate());
}
// Verify all keys are still searchable
for (keys) |key| {
try testing.expect(tree.search(key) != null);
}
}What does this test prove?
By calling validate() after every single insertion (not just at the end), you prove that the tree is correct at every intermediate state. A bug that temporarily breaks a property then "fixes" itself later would be caught.
The second loop confirms that rebalancing did not lose any keys. Rotations move nodes around but must never disconnect a key from the tree.
- Save red_black_tree.zig.
- Run your tests by running this command:
zig test red_black_tree.zig- You should see all 6 tests pass with no failures.
Tests failing?
If a validate assertion fails, your insertion fix-up may have a subtle bug. Common causes: the root is not being set to black at the end of insertFixup, or a rotation is not updating all parent pointers correctly.
If you see a compile error about isBSTValid not being found, make sure it is placed inside the RBTree struct before the final };.
Help me debug my failing red-black tree validation tests
✔️ Awesome, I've got everything!
Great. Double check you have saved your file and all 6 tests pass.
ⓧ I'd like to double check the full code
const std = @import("std");
const testing = std.testing;
pub const Color = enum {
red,
black,
};
pub const Node = struct {
key: i32,
color: Color,
left: ?*Node,
right: ?*Node,
parent: ?*Node,
};
pub const RBTree = struct {
root: ?*Node,
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) RBTree {
return .{
.root = null,
.allocator = allocator,
};
}
pub fn deinit(self: *RBTree) void {
destroySubtree(self.allocator, self.root);
self.root = null;
}
fn destroySubtree(allocator: std.mem.Allocator, node: ?*Node) void {
if (node) |n| {
destroySubtree(allocator, n.left);
destroySubtree(allocator, n.right);
allocator.destroy(n);
}
}
pub fn insert(self: *RBTree, key: i32) !void {
const new_node = try self.allocator.create(Node);
new_node.* = .{
.key = key,
.color = .red,
.left = null,
.right = null,
.parent = null,
};
var parent: ?*Node = null;
var current = self.root;
while (current) |c| {
parent = c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
new_node.parent = parent;
if (parent) |p| {
if (key < p.key) {
p.left = new_node;
} else {
p.right = new_node;
}
} else {
self.root = new_node;
}
self.insertFixup(new_node);
}
fn insertFixup(self: *RBTree, node: *Node) void {
var z = node;
while (z.parent) |p| {
if (p.color != .red) break;
const gp = p.parent orelse break;
if (p == gp.left) {
const uncle = gp.right;
if (uncle) |u| {
if (u.color == .red) {
p.color = .black;
u.color = .black;
gp.color = .red;
z = gp;
continue;
}
}
if (z == p.right) {
z = p;
self.leftRotate(z);
}
if (z.parent) |zp| {
zp.color = .black;
if (zp.parent) |zgp| {
zgp.color = .red;
self.rightRotate(zgp);
}
}
break;
} else {
const uncle = gp.left;
if (uncle) |u| {
if (u.color == .red) {
p.color = .black;
u.color = .black;
gp.color = .red;
z = gp;
continue;
}
}
if (z == p.left) {
z = p;
self.rightRotate(z);
}
if (z.parent) |zp| {
zp.color = .black;
if (zp.parent) |zgp| {
zgp.color = .red;
self.leftRotate(zgp);
}
}
break;
}
}
if (self.root) |r| {
r.color = .black;
}
}
fn leftRotate(self: *RBTree, x: *Node) void {
const y = x.right orelse return;
x.right = y.left;
if (y.left) |yl| {
yl.parent = x;
}
y.parent = x.parent;
if (x.parent) |p| {
if (x == p.left) {
p.left = y;
} else {
p.right = y;
}
} else {
self.root = y;
}
y.left = x;
x.parent = y;
}
fn rightRotate(self: *RBTree, y: *Node) void {
const x = y.left orelse return;
y.left = x.right;
if (x.right) |xr| {
xr.parent = y;
}
x.parent = y.parent;
if (y.parent) |p| {
if (y == p.left) {
p.left = x;
} else {
p.right = x;
}
} else {
self.root = x;
}
x.right = y;
y.parent = x;
}
pub fn search(self: *const RBTree, key: i32) ?*Node {
var current = self.root;
while (current) |c| {
if (key == c.key) return c;
if (key < c.key) {
current = c.left;
} else {
current = c.right;
}
}
return null;
}
pub fn validate(self: *const RBTree) bool {
const root = self.root orelse return true;
if (root.color != .black) return false;
if (!checkNoRedRed(root)) return false;
if (checkBlackHeight(root) == null) return false;
if (!isBSTValid(root, null, null)) return false;
return true;
}
fn checkNoRedRed(node: ?*Node) bool {
const n = node orelse return true;
if (n.color == .red) {
if (n.left) |l| {
if (l.color == .red) return false;
}
if (n.right) |r| {
if (r.color == .red) return false;
}
}
return checkNoRedRed(n.left) and checkNoRedRed(n.right);
}
fn checkBlackHeight(node: ?*Node) ?usize {
const n = node orelse return 1;
const left_bh = checkBlackHeight(n.left) orelse return null;
const right_bh = checkBlackHeight(n.right) orelse return null;
if (left_bh != right_bh) return null;
const increment: usize = if (n.color == .black) 1 else 0;
return left_bh + increment;
}
fn isBSTValid(node: ?*Node, min: ?i32, max: ?i32) bool {
const n = node orelse return true;
if (min) |m| {
if (n.key <= m) return false;
}
if (max) |m| {
if (n.key >= m) return false;
}
return isBSTValid(n.left, min, n.key) and isBSTValid(n.right, n.key, max);
}
};
test "tree initializes with null root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try testing.expect(tree.root == null);
try testing.expect(tree.validate());
}
test "insert single node becomes black root" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try testing.expect(tree.root != null);
try testing.expect(tree.root.?.key == 10);
try testing.expect(tree.root.?.color == .black);
try testing.expect(tree.validate());
}
test "insert multiple nodes maintains BST ordering" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
try tree.insert(3);
try tree.insert(7);
try testing.expect(tree.validate());
try testing.expect(tree.search(5) != null);
try testing.expect(tree.search(15) != null);
try testing.expect(tree.search(3) != null);
try testing.expect(tree.search(99) == null);
}
test "ascending insertion triggers rotations" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(1);
try tree.insert(2);
try tree.insert(3);
try tree.insert(4);
try tree.insert(5);
try testing.expect(tree.validate());
try testing.expect(tree.root.?.key != 1);
}
test "insertion triggers recoloring" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
try tree.insert(10);
try tree.insert(5);
try tree.insert(15);
try tree.insert(3);
try testing.expect(tree.validate());
}
test "large descending sequence validates after each insert" {
var tree = RBTree.init(testing.allocator);
defer tree.deinit();
const keys = [_]i32{ 41, 38, 31, 12, 19, 8, 7, 5, 2, 1 };
for (keys) |key| {
try tree.insert(key);
try testing.expect(tree.validate());
}
for (keys) |key| {
try testing.expect(tree.search(key) != null);
}
}Your red-black tree now proves its own correctness after every operation. Every insertion passes a full property audit. That is a production-grade confidence level for a data structure implementation.
Secret mission
Implement Deletion
Insertion was just the warm-up. Deletion from a red-black tree is the hardest operation on this data structure, requiring four fix-up cases (compared to three for insertion) and careful tracking of whether a removed node was black. Can you implement the full delete algorithm and prove it correct with your validation function?
Clean Up Your Resources
Clean Up Your Resources
This project runs entirely locally, so there are no ongoing costs. Your implementation lives in a single directory with no external dependencies.
Decide whether to keep your resources as a reference implementation, or delete them entirely.
Resources you used:
- The rbtree project directory on your Desktop containing red_black_tree.zig.
Keep everything running
No action needed. Choose this if you want to keep your red-black tree implementation as a reference you can study, extend, or revisit later.
- Your rbtree directory stays on your Desktop.
- You can re-run your test suite any time with zig test red_black_tree.zig.
Pause - I'll come back to this later
There are no running processes or services to pause. Your project is a static file on disk with no background activity.
- Your rbtree directory uses minimal disk space and has no ongoing resource usage.
- Come back any time and pick up where you left off.
Delete - I don't want to use this again
Remove the project directory and all its contents to start fresh.
- Delete the project directory by running this command:
rm -rf ~/Desktop/rbtree- On Windows, run this instead:
rmdir /s /q %USERPROFILE%\Desktop\rbtree- Confirm the directory is gone by running ls ~/Desktop and verifying rbtree no longer appears.
Nice Work!
Nice Work!
Nice work! You just built a complete red-black tree from scratch in Zig, proving that all five invariants hold after every operation through a programmatic validation suite.
What you learned:
- Implemented a self-balancing binary search tree with insertion, search, left/right rotations, and the three-case insertion fix-up algorithm in Zig.
- Used Zig's optional pointers and explicit allocator pattern to build a memory-safe pointer-based data structure with automatic leak detection via std.testing.allocator.
- Created a property validation function that programmatically verifies root color, no red-red violations, equal black-height on all paths, and correct BST ordering.
- Secret Mission: Implemented red-black tree deletion with the four-case fix-up algorithm, the hardest operation on a red-black tree.
Ready to quiz yourself?