AlgoVerse

Trie

Store words letter by letter in a tree where shared prefixes share one path; a search depends only on the word's length, not on how many words there are.

In a trie (from retrieval) each edge is a letter and each node a prefix. Words with a common prefix (like tea and ten) share a path. A node where a word ends is marked.

Read the full explanation ↓
Input:
words="tea ten to i…" · query="ten"PDF export

The words tea, ten, to, in, inn; te and in are shared paths. The search for ten succeeds.

  1. def trie(words, query):
  2. children = [{}] # children[node] maps a letter to a child node; node 0 is the root
  3. end = [False] # end[node]: some word ends here
  4. rows = [[0, "", "", ""]] # for the picture: node, prefix, child letters, word end
  5. for word in words.split():
  6. node = 0
  7. for ch in word:
  8. if ch not in children[node]:
  9. children.append({})
  10. end.append(False)
  11. children[node][ch] = len(children) - 1
  12. rows.append([len(children) - 1, rows[node][1] + ch, "", ""])
  13. rows[node][2] = "".join(sorted(children[node]))
  14. node = children[node][ch]
  15. end[node] = True
  16. rows[node][3] = "word"
  17. node = 0
  18. for i in range(len(query)):
  19. if query[i] not in children[node]:
  20. return False
  21. node = children[node][query[i]]
  22. found = end[node]
  23. return found

Invariant: Each node stands for the letters on the path from the root to it (its prefix), and each prefix has at most one node.

Start

012
ten

The table is still empty.

Local variables

words'tea ten to in inn'
query'ten'

Orange = changed in this step

Call stack

  1. trie()line 1
Step 1 of 122
Black = inserted · Orange = key stepnew_node: 0/8 · inserted: 0/5 · follow: 0/3 · found: 0/1
    Explanation

    The idea

    In a trie (from retrieval) each edge is a letter and each node a prefix. Words with a common prefix (like tea and ten) share a path. A node where a word ends is marked.

    Insert and search

    • Insert: walk from the root letter by letter; where there is no edge, make a new node; mark the last node.
    • Search: follow the same path; if an edge is missing or the last node is not marked, the word is not there.

    Cost

    Each operation is O(word length), whatever the number of words. Uses: autocomplete, spell checkers and IP routing tables.

    What to watch in the trace

    • The table lists every node: its prefix, its children's letters, and whether a word ends there.