Tries & String Indexes

A trie indexes a key by consuming successive key units along a path. Keys with a common prefix share that path, so exact lookup, prefix lookup, autocomplete, and lexical traversal arise naturally. The headline cost depends mainly on key length rather than the number of stored keys—but memory, alphabet representation, Unicode semantics, and output size determine whether the structure is actually suitable.

Define the key unit before building the index #

“Character” is not precise enough. A path step might consume:

• a byte in a binary protocol;
• a Unicode code point;
• a UTF-8/UTF-16 code unit;
• a grapheme cluster perceived as one user-facing character;
• a token, path component, domain label, or bit.

This choice changes ordering, key length, fanout, memory use, and which prefixes are meaningful. Splitting UTF-8 at arbitrary byte positions preserves byte identity but can yield prefixes that are not valid displayed strings. Code points still do not equal grapheme clusters.

Canonical-equivalent Unicode strings can have different code-point sequences. If the application intends them to match, select and apply a normalization form consistently before insertion and lookup. Normalization, case folding, and locale-aware collation are separate policies; applying them changes key identity and must not be an accidental preprocessing step.

The trie invariant and terminal marker #

Each outgoing edge from a node has a distinct label. Concatenating labels from the root to a node yields that node's prefix. A key exists only if its full path exists and the final node is marked terminal or carries a value.

The terminal marker is necessary because one key can prefix another. With keys to and top, the node reached after to must record that to is complete even though it has child p. Conversely, a path for top does not imply that to was inserted.

struct Node {
    std::unordered_map<unsigned char, std::unique_ptr<Node>> child;
    bool terminal = false;
};

void insert(Node& root, std::string_view key) {
    Node* node = &root;
    for (unsigned char unit : key) {
        auto& next = node->child[unit];
        if (!next) next = std::make_unique<Node>();
        node = next.get();
    }
    node->terminal = true;
}

This example deliberately indexes bytes. It is correct only for a contract that defines keys as byte sequences or normalizes/encodes text before this boundary.

For a key of $L$ units, exact lookup takes $O(L)$ child transitions under an $O(1)$ child-map assumption. With sorted child vectors it may take $O(L\log d)$ comparisons for node degree $d$; with a balanced tree, similar. Reporting merely $O(L)$ hides the child representation and potentially expensive hashing/comparison.

Prefix queries include their output cost #

To find all keys under prefix $p$:

1. follow the path for $p$;
2. traverse terminal descendants;
3. reconstruct or return their suffixes/values.

The work is at least $O(|p|+z)$ where $z$ is the output size, and usually includes every visited node or emitted key unit. Autocomplete systems therefore cap results, rank candidates, cache top-$k$ values at nodes, or stop under a time budget. A trie finds the prefix region cheaply; it does not make an enormous answer free.

Lexicographic enumeration requires outgoing labels in lexical order. A hash map of children gives unspecified iteration order, while a sorted vector/tree or dense alphabet array can provide order. Ordering is thus an explicit representation promise.

Fanout representation dominates memory #

A naive 256-way byte trie can spend far more memory on null child slots than on stored key data. Pool allocation, packed indices instead of pointers, and path compression often matter more than the abstract node count. Measure bytes per key, cache misses, and construction cost on representative keys.

Path compression turns chains into radix edges #

If an internal node has one child and is not terminal, its edge can be merged with the child's edge so one edge carries several units. Lookup compares the edge label with the corresponding key slice, splitting an edge on the first mismatch during insertion. This radix tree preserves prefix semantics while reducing nodes and pointer traversals.

Compressed edges need ownership rules. A label may be copied, stored as offsets into an immutable string arena, or borrowed from key storage whose lifetime outlives the index. Borrowing slices from mutable or temporary strings creates dangling labels.

Deletion clears a terminal marker/value and then may remove empty nodes or merge newly unary nonterminal paths. It must not remove a path still required by another key.

PATRICIA compresses binary decisions #

PATRICIA (Morrison's “Practical Algorithm To Retrieve Information Coded in Alphanumeric”) avoids storing every unary bit node. Internal nodes identify a discriminating bit position; search tests only positions that distinguish stored keys. Leaves hold keys/records. Because a path tests selected bits rather than necessarily consuming every bit, lookup must perform a final full-key equality check at the candidate leaf.

Bit numbering, byte order, key length, and the rule for “no bit beyond end” must be consistent. A sentinel terminator or length-aware comparison is necessary to distinguish a key from a longer key sharing all its existing bits.

Patricia/radix tries are common for IP prefixes and routing-like longest-prefix matching. That contract differs from exact string lookup: the result is the deepest terminal prefix encountered, not necessarily a full-key leaf.

A ternary search trie trades fanout for three links #

A ternary search trie (TST) node stores one key unit and three branches:

• low when the query unit is smaller;
• equal when it matches;
• high when it is larger.

Only the equal transition consumes the next key unit. Low/high transitions compare the same position again. This detail is the central invariant and a common implementation bug.

TSTs avoid a large child array and support ordered traversal, but low/high chains can degenerate with unlucky insertion order. Randomized insertion or balancing can improve behavior; the basic structure does not by itself promise worst-case logarithmic sibling search.

Suffix indexes answer a different question #

A prefix trie answers “which stored keys begin with $p$?” It does not directly answer “where does pattern $p$ occur anywhere inside one text?” Suffix tries/trees/arrays index suffixes so substring queries become prefix searches over suffixes. A naive suffix trie for a length-$n$ text can use $\Theta(n^2)$ space; compressed suffix trees and suffix arrays reduce storage with more sophisticated construction and query tradeoffs.

Do not store every suffix in an ordinary object-heavy trie and call the result scalable. Define whether the workload needs dictionary prefixes, longest routing prefix, arbitrary text substrings, fuzzy matching, or locale-aware search; each points to a different index family.

Mutation, concurrency, and untrusted keys #

Node-per-unit allocation amplifies adversarial long keys and high prefix diversity. Enforce key-length and memory limits where input is untrusted. Recursive traversal/destruction can overflow on a deep chain; iterative traversal or path compression bounds practical depth but does not replace an input contract.

Concurrent insertion can publish a child before its edge label/value is fully initialized unless the implementation uses a lock or correct release/acquire publication. Deletion requires safe reclamation for readers holding node pointers. Copy-on-write immutable tries simplify snapshot reads: updates create changed path nodes and reuse untouched subtrees, trading allocations for stable snapshots.

Review and failure diagnostics #

1. Are keys bytes, code units, code points, grapheme clusters, tokens, or bits?
2. Are normalization, case, locale, and encoding policies applied identically at every boundary?
3. Does a terminal marker distinguish a key from its prefixes?
4. Is child lookup cost/order stated for the actual fanout representation?
5. Does a prefix query include traversal and emitted-output cost?
6. Are compressed edge labels owned safely and split at the first mismatch?
7. Does PATRICIA verify full key equality after bit-guided search?
8. Does a TST consume a key unit only on its equal branch?
9. Is the desired query prefix, longest-prefix, substring, fuzzy, or ordered enumeration?
10. Can hostile key length/diversity exhaust nodes, recursion depth, or allocator metadata?

Exercises #

1. Insert to, tea, and ten into a character trie and identify terminal nodes.
2. Why can a path-compressed edge labeled testing split when inserting team?
3. In a TST, what query position is used after taking the low branch?