Trie is a tree-like Data Structure used to store strings by shared prefixes.
Each path through the trie represents a sequence of characters. Words with the same prefix share the same initial path.
For example, the words car, cat, and cap share the prefix ca.
Tries are useful for:
- Autocomplete
- Spell checking
- Prefix search
- Dictionaries
- Routing tables
Lookup time is usually O(k), where k is the length of the string being searched. This can be useful when many strings share prefixes.
The main tradeoff is memory usage, because each node may need to store references to many possible next characters.
flowchart TD Root["root"] --> C["c"] C --> A["a"] A --> R["r"] A --> T["t"] A --> P["p"]
Anki
id: trie-definition deck: Computer Science::Data Structures tags: data-structures trie
Q: Why is a trie useful for autocomplete? A: Words with the same prefix share the same path, so the program can quickly find completions after a prefix.
id: trie-use-cases deck: Computer Science::Data Structures tags: data-structures trie strings
Q: If a trie contains car, cat, and cap, what prefix path do they share?
A: They share the prefix path ca.