20. Tries

Why exact-key lookup is not enough#

A hash table answers “Is this complete key present?” efficiently. Autocomplete asks a different question: “Which keys begin with these characters?” Knowing that "s" exists or does not exist in a hash table tells us little about "sea" or "shore". We need a representation that makes prefixes explicit.

A prefix consists of the first zero or more characters of a string. For "shell" the prefixes are the empty string, "s", "sh", "she", "shel" and "shell". A trie stores strings in a rooted tree whose links represent characters. Following the links from the root spells a prefix. A node marked finishing or terminal records that the prefix is also a complete stored key.

The name comes from retrieval, although it is pronounced like “try”. The lecture motivates tries through autocomplete, predictive text, spellchecking and approximate string matching. Exact search, insertion and deletion are the core algorithms developed here. Approximate matching needs an additional search procedure; it does not follow automatically from an exact lookup.

Read a path from the root downwards, collecting its letters. Dashed red circles mark finishing nodes. The path a → c → e spells "ace"; continuing to s spells "aces". Both are stored because both endpoints are marked. A finishing node can therefore have children. It is not the same thing as a leaf.

The root represents the empty prefix and usually stores no character. If the application permits the empty string as a key, mark the root finishing. Different stored words share nodes for their common prefix.

A BST stores a whole key at each node and compares keys to decide left/right. A trie stores keys implicitly in paths, and a node may have many children. It is not a binary search tree. The static diagrams below preserve the lecture's real multiway structures.

Practice. If "app" and "apply" are stored, must "ap" and "appl" be present as keys?

Representing the alphabet and its links#

An alphabet is the set of symbols allowed in keys. Let $R$ be its size. With lowercase English letters, $R=26$. Each node can contain an array of 26 child pointers, one per letter, with absent children stored as NULL.

#define ALPHABET_SIZE 26
struct trieNode {
    struct trieNode *children[ALPHABET_SIZE];
    bool finish;
    int data;
};

The integer payload is meaningful only at a finishing node. It could instead be a definition, a count, or a list of document locations. As always, choose an ownership policy if payloads contain pointers.

For ASCII lowercase keys, character c selects index c - 'a'. This is array indexing, not hashing. 'a' selects 0 and 'z' selects 25. Validate the alphabet before using the index: uppercase letters, punctuation and bytes from other encodings require a different representation or normalisation policy.

The diagram expands each logical node into an array. Most entries are unused. Following a pointer in the s position corresponds to taking an s-labelled link in the conceptual tree. Notice how the logical picture is compact while the actual representation reserves space for every possible next letter.

If total character count across all input keys is $K$, the trie has at most $K+1$ nodes: each new character can create at most one node, plus the root. Shared prefixes reduce the actual node count $P$. The array representation uses $\Theta(PR)$ pointer slots, hence $O((K+1)R)$ space including the root. If $R=26$ is fixed, this is $O(K+1)$ asymptotically, but its constant is substantial.

On a machine with eight-byte pointers, 26 child pointers alone occupy 208 bytes per node, before flags, payload and padding. Reserving 128 pointers for an ASCII alphabet requires 1024 bytes per node just for child links.

Practice. Insert "sea" and "sell" into an empty trie. How many non-root nodes are needed?

Insertion: extend a shared path#

Start at the root and read the key from left to right. For each character, create its child only if that child is absent, then descend. After all characters, mark the current node finishing and assign the payload.

The lecture inserts sea, shell, sell, shore, she:

1. sea creates s, se and sea; mark sea.
2. shell reuses s, creates sh, she, shel and shell; mark shell. The intermediate she node is not yet finishing.
3. sell reuses s and se, creates sel and sell; mark sell.
4. shore reuses s and sh, creates sho, shor and shore; mark shore.
5. she reuses its entire existing path and marks she finishing.

Inserting an already present key updates the payload at its endpoint. It does not add another copy of the path. Inserting a word which is already a prefix, such as she above, may allocate no nodes at all.

The invariant after reading $i$ characters is that the current node represents exactly the first $i$ characters of the key, and every node/link created so far extends an existing correct prefix. Each next child preserves that property. On termination the current node therefore represents the whole key, so marking it finishing records precisely the desired word.

Practice. After shell is stored, what changes when inserting she? What changes when inserting shells?

Search: two different ways to fail#

Follow the key's characters from the root. If the required child is absent, return false. If all characters are consumed, return the endpoint's finishing flag.

For the first dictionary diagram:

• early follows e, a, r, l, y and ends at a finishing node: true.
• apple follows a, p, p, l, then cannot find e: false.
• ear follows e, a, r successfully but its endpoint is not finishing: false.

There is an l child after app because apply exists, but its child is y, not e. Matching a long prefix does not establish a complete match.

The search invariant is the same prefix correspondence used for insertion. A missing link proves that no stored word has that extension. A non-finishing endpoint proves the path is merely a prefix. Only consuming the entire query at a finishing node establishes membership.

The lecture's recursive pseudocode writes return t->finish = true at this point. In C that would assign true and turn a prefix into a stored word. Correct lookup returns t->finish without modifying it.

Practice. Why does searching "ace" succeed although the endpoint is not a leaf? Why can searching "a" fail?

Deletion: remove a word without removing other words#

The simplest deletion clears the endpoint's finishing flag. This preserves all other paths but can leave dead branches: paths which lead to no finishing node and are no longer useful.

To reclaim nodes, recurse along the word, clear its finishing flag, then check nodes while returning towards the root. A node can be removed only when it is not finishing and has no children. Never remove the permanent root in this representation.

Three lecture examples reveal different cases:

• Delete ace: clear its flag but retain its node because the s child stores aces.
• Delete apply: remove terminal y, then remove the now-childless non-finishing l representing appl. Stop at p representing app because it is finishing.
• Delete earth: remove h, then t representing eart. Stop at r representing ear because its l child still leads to early.

Returning NULL to a parent makes the corresponding child pointer empty. It does not itself release allocated memory. A C implementation must free the node before returning NULL; the lecture pseudocode abstracts that release.

Complete C implementation#

This implementation accepts lowercase ASCII words, stores copied integer payloads, retains an allocated root, and permits the empty key. Invalid alphabet input is rejected before mutation. Allocation is fail-fast: the teaching program prints an error and exits rather than providing transactional recovery after a partially built path.

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

#define ALPHABET_SIZE 26
struct trieNode {
    struct trieNode *children[ALPHABET_SIZE];
    bool finish;
    int data;
};

static bool validWord(const char *word) {
    if (word == NULL) return false;
    for (const unsigned char *p = (const unsigned char *)word; *p; p++)
        if (*p < 'a' || *p > 'z') return false;
    return true;
}

struct trieNode *trieNew(void) {
    struct trieNode *t = calloc(1, sizeof *t);
    if (t == NULL) {
        fputs("out of memory\n", stderr);
        exit(EXIT_FAILURE);
    }
    return t;
}

bool trieInsert(struct trieNode *root, const char *word, int data) {
    if (!validWord(word)) return false;
    struct trieNode *t = root;
    for (const char *p = word; *p; p++) {
        size_t i = (size_t)(*p - 'a');
        if (t->children[i] == NULL) t->children[i] = trieNew();
        t = t->children[i];
    }
    t->finish = true;
    t->data = data;
    return true;
}

bool trieGet(const struct trieNode *root, const char *word, int *out) {
    if (!validWord(word)) return false;
    const struct trieNode *t = root;
    for (const char *p = word; *p; p++) {
        t = t->children[(size_t)(*p - 'a')];
        if (t == NULL) return false;
    }
    if (!t->finish) return false;
    if (out != NULL) *out = t->data;
    return true;
}

static bool childless(const struct trieNode *t) {
    for (size_t i = 0; i < ALPHABET_SIZE; i++)
        if (t->children[i] != NULL) return false;
    return true;
}

static struct trieNode *removeWord(struct trieNode *t,
                                   const char *word, bool isRoot) {
    if (*word == '\0') {
        t->finish = false;
    } else {
        size_t i = (size_t)(*word - 'a');
        t->children[i] = removeWord(t->children[i], word + 1, false);
    }
    if (!isRoot && !t->finish && childless(t)) {
        free(t);
        return NULL;
    }
    return t;
}

bool trieDelete(struct trieNode *root, const char *word) {
    if (!trieGet(root, word, NULL)) return false;
    (void)removeWord(root, word, true);
    return true;
}

void trieFree(struct trieNode *t) {
    if (t == NULL) return;
    for (size_t i = 0; i < ALPHABET_SIZE; i++)
        trieFree(t->children[i]);
    free(t);
}

All operations other than trieFree require the allocated root. The wrapper's trieGet establishes that the complete path exists before the deletion helper follows it, so the helper does not need an absent-child case. word + 1 points into the existing string; it does not allocate or copy the suffix. The pointer assignment after recursion is essential: if the child is freed, the parent must receive NULL.

trieFree uses postorder: free all children before freeing their parent. This is the same ownership reasoning as recursive tree/list processing. Freeing a parent first would lose access to its child pointers.

For fixed alphabet size and key length $L$, insertion, worst-case lookup and deletion are $O(L)$, including input validation. Iterative insertion/lookup use $O(1)$ auxiliary space; insertion may allocate $O(LR)$ additional node storage. Recursive deletion uses $O(L)$ stack frames and may scan $R$ child entries per frame, so more explicitly its time is $O(LR)$; with fixed $R=26$, that becomes $O(L)$ as in the lecture. trieFree visits all $P$ nodes and scans their $R$ pointers, taking $O(PR)$ time and stack depth proportional to the longest stored path.

Practice. Why not delete a childless node if it is finishing? Why retain the root after deleting the last word?

Storage variants#

The array-child representation gives constant-time next-character selection but many unused pointers. The lecture considers three ways to reduce storage, each changing how a path is represented or followed.

Linked lists of children#

Store only existing children, each with its character, node pointer and next pointer. To choose a child, scan that list for the character.

Alternatively combine the child-list entry and trie node: a node stores a character, a pointer to its first child and a pointer to its next sibling.

Solid downward links reach a first child; horizontal dashed links walk siblings. To choose d at the top level, scan a, then b, then d. Although there are two pointer fields, they mean child and sibling, not the left and right subtrees of a BST. Do not apply binary-search comparisons or the binary-tree visualiser to this semantic structure.

If a node has $b$ children, finding the right child costs $O(b)$. With alphabet size $R$, worst-case lookup is $O(LR)$; treating $R$ as fixed still gives $O(L)$ but potentially larger constants than direct indexing. Storage becomes $O(P)$ nodes/links rather than $O(PR)$ child-array entries.

Practice. Why can the list representation save memory yet make an absent-character lookup slower?

Alphabet reduction#

Break each eight-bit byte into two four-bit pieces called nibbles. Each nibble has 16 possibilities. Store two links per byte instead of one link chosen from 256 possibilities.

ASCII sea becomes hexadecimal nibbles 7,3,6,5,6,1: s is 0x73, e is 0x65 and a is 0x61. Branching drops to 16 pointer slots per node, but a three-byte word has a six-edge path.

Worst-case path length doubles; asymptotically lookup remains $O(L)$ for byte length $L$. A loose pointer-storage bound changes from about $256L$ per unshared byte path to about $16(2L)=32L$, before allowing for prefix sharing and node overhead. This comparison is against a full-byte alphabet, not the earlier 26-letter alphabet; savings depend on the representation being replaced.

Practice. How many children can a nibble node have, and where is the finishing flag for a two-byte key?

Compressed tries#

A compressed trie merges non-branching chains into multi-character labels. Only nodes which are non-finishing and have one child can be merged without losing a key endpoint or branch decision.

If "shore" is the only key below "sho", the remaining "re" can be one label rather than two separate nodes. If "she" and "shell" are both keys, do not merge away the finishing boundary at she unless the new representation explicitly records it.

Search compares every character in an edge label before continuing. A mismatch inside the label proves absence. Insertion may have to split a label where the new key diverges or ends. Compression reduces pointer/node overhead; it does not justify skipping the characters needed to distinguish keys. Exact search remains $O(L)$ character work under constant-time branch selection.

Applications: prefixes and multiple possible letters#

Word finding in a document#

Preprocess a document by inserting its words into a trie. At each word's finishing node, store the positions of all its occurrences. Searching then follows the word once and returns its occurrence list rather than rescanning the entire document.

The diagram's numbers belong to the word endpoint, not each character. If a word occurs three times, its path is stored once and its payload contains three locations.

Let $K$ be document character work used to build the index and $z$ the number of occurrences returned by a query of length $L$. Building has at least $O(K)$ input-reading work plus storage for locations. Lookup is $O(L)$ for the path; materialising $z$ results adds $\Theta(z)$. Saying “the whole query is $O(L)$” would omit its output.

Autocomplete#

Follow the typed prefix, such as "sh". If its path is absent, there are no completions. Otherwise traverse the subtree rooted there and report every finishing endpoint.

For the lecture sea/shell/sell/shore/she trie, "sh" reaches a node with e and o branches. The e branch reaches finishing she, then continues to shell; the o branch reaches shore. With children visited alphabetically, the completions are she, shell, shore.

The initial prefix lookup costs $O(L)$. Reporting completions additionally visits subtree nodes and constructs output strings. With array children, visiting $P_s$ subtree nodes scans $RP_s$ child entries. Include output character work as well: returning thousands of matches cannot be constant-time.

Practice. Can autocomplete return she and shell together? Why must traversal continue after a finishing node?

Predictive text#

On a phone keypad, one digit corresponds to several letters: 4 to g/h/i, 6 to m/n/o, and 3 to d/e/f. A digit sequence therefore describes several possible paths rather than one.

For 4663, the lecture examples include good, hoof, home, hood. Follow only child links allowed by the current digit, maintain all surviving prefixes, and retain finishing words after the final digit. This differs from exact search's single path.

The player below follows a small dictionary containing just those four words. The array is the unchanged digit input; the table records surviving prefixes. It deliberately uses no binary-tree picture for the multiway trie.

If there are $b$ choices per digit and $L$ digits, a loose upper bound on potential strings is $b^L$. The trie prunes absent prefixes, but the actual number of surviving branches still matters; predictive text does not inherit exact lookup's single-path $O(L)$ guarantee. Ranking matches by frequency needs stored frequency data and an explicit ranking rule.

The C tab implements a depth-first traversal of the same conceptual multiway trie. node is the current prefix; digits points to the unprocessed suffix. Each allowed letter selects an actual child pointer, and a null child prunes that entire branch. At the end, only finishing nodes are emitted. A small wrapper should first reject digits outside 2–9, allocate strlen(digits)+1 bytes for buffer, and pass a valid root/callback; that keeps index arithmetic safe. The callback consumes the buffer before the next candidate overwrites it.

#include <stddef.h>

/* Uses the trieNode from this chapter. Caller validates digits 2..9,
   and provides a buffer of strlen(digits)+1 bytes and an emit callback. */
static const char *letters[10] = {
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

void predict(const struct trieNode *node, const char *digits,
             size_t depth, char *buffer,
             void (*emit)(const char *)) {
    if (*digits == '\0') {
        if (node->finish) {
            buffer[depth] = '\0';
            emit(buffer);
        }
        return;
    }
    for (const char *p = letters[*digits - '0']; *p; p++) {
        const struct trieNode *next = node->children[*p - 'a'];
        if (next == NULL) continue; /* Prune absent prefix. */
        buffer[depth] = *p;
        predict(next, digits + 1, depth + 1, buffer, emit);
    }
}

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. A trie contains car and cart. Delete car. Which nodes remain, and which terminal marker changes?

Question 2. A compressed trie initially stores only car as one edge label. Insert cat. Where must the edge be split, and which two suffix labels branch afterward?

Question 3. A trie stores stone, stony and stop. What work is required to enumerate all completions of prefix sto?

For exact-key lookup comparisons, return to 17. Hash Tables and 11. AVL Trees. 21. COMP2521 Revision brings these structures together.