Trie (source code)
= Trie
= Tries
{synonym}
A <trie> stores strings in a rooted tree whose edges represent symbols; the path from the root spells a prefix. A separate terminal marker distinguishes a stored word from a prefix of another. Storing `to`, `tea` and `ten` shares the initial `t`, and `tea` with `ten` also shares `te`. Lookup follows one edge per symbol, taking $O(m)$ time for a length-$m$ key when child selection is constant-time. Dense child <arrays> use more memory than sparse maps. A <trie> naturally supports prefix queries and longest-prefix matching.https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/TrieST.java[Class documentation: key operations, prefix queries and length-based costs]{ref}
Back to article page
