Tries
The conceptHow autocomplete finds every word starting with "ca" so quickly
A trie (said "try") is a tree where each edge is one letter, so each node stands for a prefix: the letters on the path from the root to it. A flag on a node marks "a word ends here".
Store "car", "cat" and "cart": root → c → a, then "ca" splits into r ("car", flagged) and t ("cat", flagged); a t under "car" gives "cart". Five nodes hold three words, since "ca" is stored once.
Lookup follows one edge per letter; insert does the same and creates missing nodes. Each node keeps its children in a small array (a slot per letter) or a hash table, so choosing the next edge takes about one step.
What it’s forGives the cost of looking up or inserting a word in a trie.
lookup time = O(L)
- L
- the length of the word or prefix being searched, e.g. 4 for "cart"
- O(·)
- Big-O: how the work grows; note the number of stored words n does not appear
What it givesA cost that depends only on how long the word is, not on how big the dictionary is.
- Find "cart": 4 letters → 4 steps down the trie.
- Same 4 steps with 1,000 words or 1,000,000 words stored.
- Binary search on 1,000,000 sorted words needs about 20 whole-word comparisons (2²⁰ ≈ 1,000,000).