Overview
A Trie (derived from “retrieval”), also known as a prefix tree, is a specialized tree-based data structure used to store a dynamic set of strings. Unlike a binary search tree, no node in the trie stores the key associated with that node; instead, its position in the tree defines the key it is associated with.
Core Concepts
- Nodes and Edges: Each node represents a character of a string. The path from the root to a particular node represents a prefix.
- Prefix Sharing: All descendants of a node have a common prefix. This makes tries incredibly efficient for prefix-based searches.
- Termination Marker: Nodes often contain a boolean flag (e.g.,
isEndOfWord) to indicate if the node completes a valid word in the set. - Complexity:
- Insert: $O(L)$ where $L$ is the length of the word.
- Search: $O(L)$.
- Prefix Search: $O(L)$.
Code Examples
class TrieNode {
children: Map<string, TrieNode> = new Map();
isEndOfWord: boolean = false;
}
class Trie {
root = new TrieNode();
insert(word: string) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) node.children.set(char, new TrieNode());
node = node.children.get(char)!;
}
node.isEndOfWord = true;
}
search(word: string): boolean {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) return false;
node = node.children.get(char)!;
}
return node.isEndOfWord;
}
}Use Cases
- Autocomplete / Type-ahead: Finding all words that start with a given prefix.
- Spell Checkers: Quickly validating if a word exists in a dictionary.
- IP Routing: Longest prefix matching for routing packets.
Gotchas
- Memory Usage: Tries can consume a lot of memory because each node may have many child pointers (e.g., 26 for the English alphabet), even if only a few are used.
- Compressed Tries (Radix Trees): To save space, nodes with only one child can be merged with their child.