Intrusive Red-Black Trees: The Ultimate Balance of Memory Layout

High-performance systems programming forces a choice: optimize for memory layout and cache efficiency, or accept the convenience of standard library containers. Containers like std::map and std::set hide significant costs behind their ease of use. Every insertion allocates a heap node; thousands of tiny scattered allocations fragment memory and disable CPU cache prefetching. During tree traversal, the CPU jumps through memory—pointer chasing—rather than following contiguous data.

Intrusive Red-Black Trees sidestep this trade-off by embedding tree linkage directly in the business object. This pattern is deployed widely in performance-critical infrastructure: OS kernels, game engines, and HFT systems. Zig provides elegant tools to implement it safely and transparently, combining zero allocation overhead, cache locality, and O(log N) random access in a single structure.

What is "Intrusive"?

In standard (non-intrusive) containers, the container is responsible for allocating node memory and holding data. The data knows nothing about the container.

// Non-intrusive: Container wraps data
const Node = struct {
    left: ?*Node,
    right: ?*Node,
    data: UserData, // Data is copied or referenced
};

In an intrusive design, the data itself is the node. The business object "knows" it is part of a container and actively embeds the required linkage fields (like left, right, parent).

// Intrusive: Data embeds node
const UserData = struct {
    id: u64,
    name: []const u8,
    // Intrusive node, directly embedded in the struct
    rb_node: RbNode, 
};

This inversion brings substantial advantages:

Zero Extra Allocations: Inserting an element requires no malloc for a new node because the node is already inside the object.
Cache Friendliness: Business data and tree linkage information are contiguous in memory.
Multiple Indexing: An object can embed multiple different nodes (e.g., rb_node, list_node), allowing it to exist in a Red-Black Tree and a Linked List simultaneously without complex back-pointer maintenance.

The Zig Implementation: The Magic of `fieldParentPtr`

In C++, intrusive containers are often implemented via complex templates and inheritance (CRTP). In Zig, the logic of recovering the object from the node can be handled much more elegantly and explicitly using fieldParentPtr.

First, define an embedded Red-Black Tree node. Note that we add a size field, which is crucial for the efficient indexing discussed below.

const Color = enum { red, black };

/// Intrusive RB-Tree node, embedded in business objects
pub const RbNode = struct {
    parent: ?*RbNode = null,
    left: ?*RbNode = null,
    right: ?*RbNode = null,
    color: Color = .red,
    /// Subtree size (including self) for O(log N) random access
    size: usize = 1, 
};

Next is the container's core logic. Pay attention to the getEntry function, which uses pointer casting to restore the RbNode pointer back to the host object T pointer. This mechanism is central to intrusive containers.

pub fn IntrusiveRbTree(comptime T: type, comptime field_name: []const u8) type {
    return struct {
        const Self = @This();
        root: ?*RbNode = null,

        /// "Reverse" the node pointer back to the business object T
        fn getEntry(node: *RbNode) *T {
            return @fieldParentPtr(T, field_name, node);
        }

        fn getSize(node: ?*RbNode) usize {
            if (node) |n| return n.size;
            return 0;
        }

        // ... Insertion and Rotation Logic ...
    };
}

Core Feature: `size` Counting & O(log N) Random Access

Standard Red-Black Trees support only key-based lookup. To find the "100th smallest element" normally requires an O(N) traversal.

In our design, each node maintains a size field: the count of the current node plus all nodes in its left and right subtrees. This gives the Red-Black Tree array-like characteristics:

/// Get element at rank `index`, time complexity O(log N)
pub fn at(self: *Self, index: usize) ?*T {
    var curr = self.root;
    var idx = index;

    while (curr) |n| {
        const left_sz = getSize(n.left);
        if (idx < left_sz) {
            // Target is in the left subtree
            curr = n.left;
        } else if (idx == left_sz) {
            // Current node is the target
            return getEntry(n);
        } else {
            // Target is in the right subtree
            // adjust index by subtracting left subtree + current
            idx -= left_sz + 1;
            curr = n.right;
        }
    }
    return null;
}

This design suits scenarios needing frequent access by rank or index—leaderboards, random sampling of ordered sequences—while maintaining O(log N) insertion and deletion performance. The cost is that every rotation and recoloring operation must update size on the affected path, but this remains a constant-factor overhead per operation.

Full Demonstration

Let's see how to use it in actual code:

const std = @import("std");

// Business Object
const Monster = struct {
    hp: i32,
    attack: i32,
    // Embed node to make it part of the tree
    node: RbNode = .{},

    // Comparison function defines tree order
    pub fn compare(self: *Monster, other: *Monster) i32 {
        if (self.hp < other.hp) return -1;
        if (self.hp > other.hp) return 1;
        return 0;
    }
};

test "intrusive tree demo" {
    // Define an RB-Tree using the "node" field hook
    var tree = IntrusiveRbTree(Monster, "node"){};

    // Objects allocated on stack or anywhere, container doesn't care
    var m1 = Monster{ .hp = 100, .attack = 10 };
    var m2 = Monster{ .hp = 200, .attack = 50 };
    var m3 = Monster{ .hp = 50, .attack = 5 };

    // Insert pointers, zero memory allocation
    tree.insert(&m1);
    tree.insert(&m2);
    tree.insert(&m3);

    // Verify Order (Sorted by HP: 50, 100, 200)
    // Get 1st element (index 1), should be m1 with HP=100
    const found = tree.at(1); 
    try std.testing.expect(found.?.hp == 100);
}

Design Trade-offs

This design carries clear trade-offs.

Advantages:

Extreme Performance: Zero allocation overhead and high cache locality.
Dual Access Modes: Supports both key-based and index-based lookup.
User-Controlled Lifecycle: Object lifetime is determined by the user, not constrained by container ownership.

Disadvantages:

Structural Coupling: Business objects must embed tree-specific fields, polluting the data structure.
Lifetime Management: Users must ensure objects are not destroyed before removal from the tree. Zig's ownership model provides some protection, but discipline is required.

When performance becomes a bottleneck in systems programming, intrusive data structures often provide the necessary breakthrough. Zig's fieldParentPtr and explicit memory model make this classical technique more transparent and safer than traditional approaches like C++ CRTP.