Tries: prefix trees

Introduction

When you type ca into a search box and it suggests car, cat and cart, a trie is often behind it. A trie (from retrieval, said "try") stores strings one character per level: the path from the root spells a prefix, and a mark on a node says "a whole word ends here".

        (root)
        /    \
       c      d
       |      |
       a      o
      / \     |
    r*   t*   g*
    |
    t*            * = a word ends here

This trie holds car, cat, cart and dog. The words car and cart share the nodes for c, a and r: common prefixes are stored once.

A hash table can tell you whether a word exists, but it cannot help you finish one. A trie arranges words by their letters, so every word that begins the same way lies along the same path.

How it works

Counting words with a prefix

Add a counter to each node: how many words pass through it. Then "how many words start with te?" is one walk down to the e node and one read.

#include <stdio.h>
#include <stdlib.h>

struct node {
    struct node *child[26];
    int pass;                 // how many words pass through this node
};

struct node *root;

void insert(const char *w) {
    struct node *cur = root;
    for (int i = 0; w[i]; i++) {
        int k = w[i] - 'a';
        if (!cur->child[k]) cur->child[k] = calloc(1, sizeof(struct node));
        cur = cur->child[k];
        cur->pass++;
    }
}

int starts_with(const char *p) {
    struct node *cur = root;
    for (int i = 0; p[i]; i++) {
        cur = cur->child[p[i] - 'a'];
        if (!cur) return 0;
    }
    return cur->pass;
}

int main(void) {
    root = calloc(1, sizeof(struct node));
    const char *words[] = {"tea", "ten", "to"};
    for (int i = 0; i < 3; i++) insert(words[i]);
    printf("t: %d\n", starts_with("t"));
    printf("te: %d\n", starts_with("te"));
    printf("x: %d\n", starts_with("x"));
    return 0;
}

Autocomplete goes one step further: from the prefix's node, visit the subtree (depth-first) and print every word found. Because children are visited in letter order, the words come out sorted, which a hash table cannot give you.

Tries, hash tables and search trees

The price is memory: with 26 pointers, a node takes over 200 bytes on a 64-bit computer, and most of those pointers are NULL. Real systems save space with a compressed trie (radix tree), which merges chains of single-child nodes into one node holding a string. Routers use one to find the longest matching IP address prefix.

Syntax

struct node {
    struct node *child[26];
    int end;
};

int k = word[i] - 'a';   // 'a' becomes 0, 'b' becomes 1, ...

Example

For lowercase English words, each node has one child pointer per letter. Letter ch goes to child[ch - 'a'], so finding the right child is one array lookup, with no searching.

#include <stdio.h>
#include <stdlib.h>

struct node {
    struct node *child[26];
    int end;                  // 1 if a word ends at this node
};

struct node *new_node(void) {
    return calloc(1, sizeof(struct node));   // every child starts as NULL
}

void insert(struct node *root, const char *word) {
    struct node *cur = root;
    for (int i = 0; word[i]; i++) {
        int k = word[i] - 'a';
        if (!cur->child[k]) cur->child[k] = new_node();
        cur = cur->child[k];
    }
    cur->end = 1;
}

int search(struct node *root, const char *word) {
    struct node *cur = root;
    for (int i = 0; word[i]; i++) {
        cur = cur->child[word[i] - 'a'];
        if (!cur) return 0;   // the path stops: not stored
    }
    return cur->end;          // the path exists, but is it a whole word?
}

int main(void) {
    struct node *root = new_node();
    insert(root, "car");
    insert(root, "cat");
    insert(root, "cart");
    printf("cat: %d\n", search(root, "cat"));
    printf("ca: %d\n", search(root, "ca"));
    printf("cow: %d\n", search(root, "cow"));
    return 0;
}

• insert: walk down from the root one letter at a time, creating any missing node, then set end = 1 on the last node.
• search: walk down the same way. If a child is NULL, the word is not there. If the walk finishes, the answer is the last node's end flag: ca is a path in the trie but not a word.

Both cost O(L) for a word of length L, however many words the trie holds. A balanced search tree of n strings needs O(L · log n), because every comparison may read a whole string.

Line by line

1. Each node has 26 child pointers and an end flag. calloc sets all of them to zero.
2. insert walks down the word, creating any missing node on the way.
3. After the last letter, it sets end on the node where the word stops.
4. search walks down the same way, and returns 0 as soon as a child is missing.
5. If the walk finishes, it returns the last node's end.
6. main adds three words. cat is found, ca is only a prefix, and cow has no path.

Expected result

cat: 1
ca: 0
cow: 0

In the real world

Search boxes and phone keyboards use tries to suggest how a word might end. Internet routers use a compressed form to find the longest matching prefix of every address they forward.

Common mistakes

• Forgetting the end flag, so ca is reported as a word because its path exists.
• Characters outside a to z (capitals, digits, spaces): ch - 'a' becomes a bad index. Check, or convert first.
• Never freeing the nodes. Free a trie bottom-up: the children first, then the node.

Best practices

• Convert or reject characters outside the expected range before indexing.
• Keep counts or flags on nodes, so that common questions take one walk.
• Consider a compressed trie when memory matters.

Summary

A trie stores strings a character at a time, sharing common prefixes. Searching takes one step per letter, an end flag marks whole words, and everything sharing a prefix sits in one subtree.

Mark lesson complete