How to make a trie in Zig

Help
21

I saw “character” in that trie and was triggered by that.
If the structure is suitable for it, and you can manage to stuff it into flat memory it is:

  • much faster
  • much smaller
  • and after that compressable (unique subtrees)

However that is quite compllcated :slight_smile:

22

This is the real error you should be solving. Trie.init returns Trie but children is ?*TrieNode. You likely want a TrieNode.init function, but without heap allocation there’s no where for the memory of the nodes to live (since they need to outlive the insert function).

You might need to rethink how you go about avoiding heap allocation.

I’ve added an init method in TrieNode as well as a search method in Trie, which follows insert closely and is mainly for testing.

In its entirety, the code looks like:

pub const TrieNode = struct {
    children: [26]?*TrieNode,
    is_word: bool,

    pub fn init() TrieNode {
        return .{
            .children = [1]?*TrieNode{null} ** 26,
            .is_word = false,
        };
    }
};

pub const Trie = struct {
    root: ?*TrieNode = null,

    pub fn insert(self: *Trie, word: []const u8) void {
        if (self.root == null) {
            var rootNode = TrieNode.init();
            self.root = &rootNode;
        }

        var node = self.root.?;

        for (word) |ch| {
            if (node.children[ch - 'a'] == null) {
                var trieNode = TrieNode.init();
                node.children[ch - 'a'] = &trieNode;
            } else {
                node = node.children[ch - 'a'].?;
            }
        }

        node.is_word = true;
    }

    pub fn search(self: Trie, word: []const u8) bool {
        var node = self.root.?;

        for (word) |ch| {
            if (node.children[ch - 'a'] == null) {
                return false;
            } else {
                node = node.children[ch - 'a'].?;
            }
        }

        return node.is_word;
    }
};

test Trie {
    var trie: Trie = .{};

    trie.insert("hello");
    trie.insert("world");

    try testing.expect(trie.search("hello") == true); // fails
    try testing.expect(trie.search("word") == false);
}

const std = @import("std");
const testing = std.testing;

but there’s a bug in the insert method as the first test case fails.

I have made one a while back, not the greatest, but it could serve as a starting point, lots of ways to improve my implementation :slight_smile:
ztrie

Thanks for sharing!

The insert and search methods are very close to what I’m trying. The only difference is that there’s no allocation … and a bug in insert :slight_smile:

23

You’re storing the address of a local variable, which will be have an undefined value after the function returns.

1 Like