Search algorithmsCTRL K
Autocomplete over a dictionary
· type a prefix, the trie narrows to the words below it/signatures/autocompletebuilt on TrieWORDS
150
in the dictionaryTRIE NODES
532
one per distinct prefixNODES VISITED
0vs 150 scan
by this queryCOMPLETIONS
0
found so farTYPED
3
characters, one edge eachcurrentprefix pathcompletionother nodes150 words · 532 nodes · 17 steps
step 0 / 16
SUGGESTIONS0
CURRENT STEP
150 words in a trie of 532 nodes. The root fans out into 5 first letters; type to walk down.
Autocomplete over a dictionary
A trie stores words character by character, so all the words sharing a prefix share a path. Autocomplete is then two moves: follow the typed prefix down the trie, which costs one step per character whatever the dictionary size, and enumerate the subtree under the node where the prefix ended.
This is what a search box, an IDE and a phone keyboard do: the walk is O(length of the prefix), the enumeration stops after the first k results, and no word outside the prefix is ever touched. A linear scan would compare the prefix against every entry.
What to notice
The nodes visited counter stays small however many words exist: only the prefix path and the subtree count.
A prefix with no child ends the search at once; a scan would still test every word.
The labels +n on cut branches are the words hidden below: the trie knows the count without visiting them.