Trie

A basic trie consumes one character or chosen key unit per level. Keys with the same beginning share a path until they diverge. A terminal marker or associated value distinguishes a complete stored key from a prefix that only leads to longer keys.

Storing a long word does not automatically store every shorter prefix as a key. Exact lookup checks both that the path exists and that its ending position represents a valid entry.

References: [1] [2]

Prefix enumeration reaches the supplied prefix and collects stored keys below it. Longest-prefix lookup instead walks the query while remembering the latest valid key ending. Both differ from asking whether the entire query is itself a stored key.

These operations support applications such as routing prefixes and completion, with meaning supplied by the application. Literal prefix agreement does not automatically establish that two names identify the same object or have a semantic relationship.

References: [1] [2]

Direct one-unit-per-level lookup commonly follows key length; Princeton’s 256-way implementation gives key-length bounds for core operations. Enumerating many matches additionally costs work proportional to the output rather than only to reaching the prefix.

Allocating a full alphabet-sized child array at each node can waste space on sparse branches. Ternary search tries use another representation. Implementations must specify key units, supported alphabet, case handling, and normalization instead of assuming all character encodings behave identically.

References: [1] [2]