Tries

Six words go into a tree one letter at a time. Words that begin alike share a path. Watch them grow, then look up a prefix.

⋯21void insert(struct trie *t, const char *w)22{23    for (; *w != '\0'; w++) {24        int c = *w - 'a';25        if (t->child[c] == NULL)26            t->child[c] = new_trie();27        t = t->child[c];28    }29    t->end = true;30}⋯32bool contains(const struct trie *t, const char *w)33{34    for (; *w != '\0'; w++) {35        t = t->child[*w - 'a'];36        if (t == NULL)37            return false;38    }39    return t->end;40}⋯42static void list_from(const struct trie *t, char *buf, int len)43{44    if (t->end) {45        buf[len] = '\0';46        printf(" %s", buf);47    }48    for (int c = 0; c < 26; c++) {49        if (t->child[c] != NULL) {50            buf[len] = (char)('a' + c);51            list_from(t->child[c], buf, len + 1);52        }53    }54}55 56void list_prefix(const struct trie *t, const char *prefix)57{58    char buf[32];59    int len = 0;60    printf("under %s:", prefix);61    for (; prefix[len] != '\0'; len++) {62        t = t->child[prefix[len] - 'a'];63        if (t == NULL)64            break;65        buf[len] = prefix[len];66    }67    if (t != NULL)68        list_from(t, buf, len);69    printf("\n");70}⋯80int main(void)81{82    struct trie *root = new_trie();83    const char *words[6] = { "car", "cart", "care", "cat", "dog", "do" };84    for (int i = 0; i < 6; i++)85        insert(root, words[i]);86    bool a = contains(root, "car");87    bool b = contains(root, "ca");88    bool c = contains(root, "cars");89    bool d = contains(root, "do");90    printf("car %d, ca %d, cars %d, do %d\n", a, b, c, d);91    list_prefix(root, "car");92    list_prefix(root, "ca");93    printf("%d nodes, %d pointers, %d in use\n", nodes, 26 * nodes, nodes - 1);94    free_trie(root);95    return 0;96}

One letter per edge

A trie (from retrieval, usually said “try”) is a tree in which each node stands for a beginning of a word. The root stands for the empty beginning. Each node has one child slot for every letter, and following the child for a letter adds that letter: from the root, c then a then r reaches the node for “car”.

A word is a path, not a node. The node for “ca” exists because car, cart, care and cat all begin with it, yet “ca” is not a word. So every node also has an end mark, which says whether a word stops there. In the picture the marked nodes are filled.

Two consequences follow:

• Words that share a beginning share its nodes. car, cart, care and cat use one c and one a between them.
• Every word that begins with a prefix sits in the subtree under the prefix’s node. To list the words beginning with “ca”, walk to its node and list everything under it.

The code and its cost

A node

The letters are lowercase a to z, and words are shorter than 32 letters. A node is an array of 26 child pointers, one per letter, and the end mark:

struct trie {
    struct trie *child[26];
    bool end;
};

sizeof (struct trie) is 216 bytes on this platform: 26 pointers of 8 bytes make 208, the bool adds 1, and the struct is padded to a multiple of 8. A new node comes from calloc, which hands back memory filled with zeros, so all 26 children start as NULL and the end mark as false. A static counter, nodes, counts the nodes made.

In the clip each node takes 224 bytes of heap, 216 and the allocator’s bookkeeping, so the ten nodes sit at 0x1000, 0x10e0, 0x11c0 and so on, 0xe0 apart: the root at 0x1000, “car” at 0x12a0, “dog” at 0x17e0.

Inserting a word

void insert(struct trie *t, const char *w)
{
    for (; *w != '\0'; w++) {
        int c = *w - 'a';
        if (t->child[c] == NULL)
            t->child[c] = new_trie();
        t = t->child[c];
    }
    t->end = true;
}

*w - 'a' turns a letter into its slot: a is 0, c is 2, z is 25. For each letter, insert follows the child for it, making the child first if it is missing. At the end it sets the mark on the node reached. Inserting “do” after “dog” makes no node at all: it walks d and o and marks the o.

Looking a word up

bool contains(const struct trie *t, const char *w)
{
    for (; *w != '\0'; w++) {
        t = t->child[*w - 'a'];
        if (t == NULL)
            return false;
    }
    return t->end;
}

A missing child means no word has those letters: “cars” fails at the s. Reaching the end of the word is not enough: contains returns the end mark, so “ca” gives false although its path exists. The program prints the four answers:

car 1, ca 0, cars 0, do 1

Both insert and contains take one step per letter, however many words the trie holds. A hash table, later in the course, also reads every letter to compute its hash; binary search on a sorted array of n words compares whole words about log₂ n times.

Listing the words under a prefix

static void list_from(const struct trie *t, char *buf, int len)
{
    if (t->end) {
        buf[len] = '\0';
        printf(" %s", buf);
    }
    for (int c = 0; c < 26; c++) {
        if (t->child[c] != NULL) {
            buf[len] = (char)('a' + c);
            list_from(t->child[c], buf, len + 1);
        }
    }
}

list_prefix walks down the prefix, copying its letters into buf, then calls list_from on the node it reached. list_from prints the word in buf if one ends here, then visits the children in letter order, writing each letter into buf before going down. Because the children are tried from a to z, the words come out in alphabetical order: care before cart.

under car: car care cart
under ca: car care cart cat

Memory

Each node holds 26 pointers, and most of them are NULL. The program prints its count at the end:

10 nodes, 260 pointers, 9 in use

Every node but the root hangs from exactly one pointer, so 10 nodes use 9 pointers and leave 251 of the 260 empty. Radix trees cut the number of nodes by merging chains that have only one child.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic trie.c -o trie
./trie

Worked example

Inserting “cats”. c, a and t exist, so insert walks them and makes one new node under t for s, and marks it.

Inserting “dot”. d and o exist; the o has no child t, so one new node.

Why is contains(“ca”) false? Its node exists, but it has no end mark: no word stops at “ca”.

The memory, in bytes. The six words have 3 + 4 + 4 + 3 + 3 + 2 = 19 letters. The trie uses 10 nodes × 216 bytes = 2,160 bytes for them, and 251 of its 260 pointers are NULL.

A large dictionary. Put 100,000 words into a trie and a lookup still takes one step per letter of the word looked up: a nine-letter word takes nine steps, whether the trie holds a hundred words or a hundred thousand.

Where it’s used

Autocomplete. As a prefix is typed, its node is found in a few steps, and the words under it are the suggestions.

Spell checkers. A word not on any path, or ending on an unmarked node, is not in the dictionary; nearby paths suggest corrections.

Routing tables. Network routers find the longest stored prefix of an address in a compressed binary form of the trie, the subject of Radix trees.

Counting by prefix. A count kept in each node, raised by every insertion through it, says how many words begin with each prefix.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.