A hash table can tell you whether "CART" is stored, but not which
stored words start with "CA". A trie (from retrieval, often said "try") can, because
it stores words letter by letter along paths from a root:
Each edge is labelled with one letter. Reading the edges from the root down to a node spells a prefix.
Words with the same beginning share the same path for as long as they agree, then branch.
A node is marked where a stored word ends. A word can end at a node that continues
further: CAR inside CART.
Operations
Search: follow the word's letters. It's stored only if every letter has an edge
and the last node is marked. A path without a mark is just a prefix of longer words.
Insert: follow the letters as far as they exist, add nodes for the rest, and mark
the last one.
Prefix query: walk down the prefix; every marked node below is a word that starts with
it. That's autocomplete.
Delete: remove the mark, then remove nodes from the end upward while they lead to no
other word: no children and no mark of their own.
Reading the pictures
The word being processed is shown above the trie, with its current letter outlined. A filled dot inside a
node marks a word end; the path being walked is blue, the matches green, and nodes about to be removed
are dashed red. Children are drawn in alphabetical order.
Trie
Search, insert, delete
O(L) for a word of length L, however many words are stored
Prefix query
O(L + the size of the answer)
Space
One node per distinct prefix. Real tries store children in arrays, maps, or compressed runs (radix trees) to save memory.