Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Tries: make prefix search distinct from complete-key lookup

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A trie follows one edge per symbol in a key. Prefix lookup and insertion take O(L) time for key length L, independent of the number of stored keys under constant-time child lookup assumptions. A path existing does not mean its prefix is a stored complete key, so a terminal flag is necessary. Tries can use substantial memory because each node has child mappings and references. Normalize case and Unicode according to the application's identifier contract before insertion; otherwise visually similar labels may take different paths and produce confusing search results.

Operational case

A depot indexes part codes AX47 and AX52. Prefix AX exists, but it is not a complete part code. The terminal marker on AX47 distinguishes an exact match from a prefix suggestion. The two codes share the AX nodes, which makes prefix filtering natural. A general substring search inside arbitrary product descriptions is a different problem; this trie only follows prefixes from the root. For a small catalog, a sorted list may be simpler and use less memory.

Working Python program

python
part_root = {}
for part_code in ("AX47", "AX52"):
    current = part_root
    for symbol in part_code:
        current = current.setdefault(symbol, {})
    current["$end"] = True

def lookup(part_code):
    current = part_root
    for symbol in part_code:
        if symbol not in current:
            return False
        current = current[symbol]
    return "$end" in current

print(lookup("AX"), lookup("AX47"))

Output

Output
False True

Time, space, and tradeoff

The two insertions take O(total characters) time and space. Lookup is O(L) expected time with hash-backed child maps. The sentinel key is safe here because symbols are individual characters and no input character equals the multi-character marker; a typed node with a separate boolean is clearer in a larger implementation. Deletion needs to unmark the terminal and prune only nodes no longer shared by another code. Prefix listing also pays for every descendant key returned, beyond the O(L) path walk.

Common Mistakes

  • Do not report every existing prefix as a full stored key.
  • Do not mistake prefix search for arbitrary substring search.
  • Do not prune a shared branch while deleting one key.

Connected lessons

Failure-linked tries: find overlapping alert terms in one scan handles a related query contract.

Binary tries: choose a maximum-XOR fingerprint adds a related operation contract.

Front-coded lexicons: store shared prefixes within sorted term blocks adds a related indexing contract.

Level-order unary degree tries: encode child runs as bits adds a compact lookup contract.

Ternary search trees: branch by character and continue prefixes adds a keyed lookup comparison.

LZ78 phrase tries: emit dictionary index and next symbol adds a related structure with a different operation boundary.

Double-array tries: static incident-code transitions with BASE and CHECK examines a related structure with a different operation boundary.

Minimal acyclic dictionaries: merge equivalent word suffix states examines a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details