Tries (Prefix Trees)
A Trie (pronounced "try") or Prefix Tree is a tree-based data structure used to efficiently store and retrieve keys in a dataset of strings. It is particularly effective for problems involving string prefixes.
1. The Structure
Unlike a binary search tree, nodes in a Trie do not store their associated key. Instead, a node's position in the tree defines the key with which it is associated.
- Root: Represents an empty string.
- Edges: Represent characters.
- Nodes: Often contain a boolean flag (e.g.,
isEndOfWord) to indicate if the path from the root to this node forms a complete word.
2. Operations
Insert
To insert a word, we start at the root and walk down the tree, following the edges corresponding to each character in the word. If an edge doesn't exist, we create a new node. At the last character, we mark the node as isEndOfWord.
Search
Similar to insert, we traverse down the tree. If we can follow the path for all characters and the final node is marked isEndOfWord, the word exists.
StartsWith (Prefix Search)
This is the Trie's superpower. We traverse down the tree. If we can follow the path for all characters, then the prefix exists in the Trie, regardless of the isEndOfWord flag.
3. Complexity
- Time Complexity: $O(L)$ for insert, search, and prefix search, where $L$ is the length of the word. This is often faster than a Hash Table ($O(L)$ on average) because there are no hash collisions.
- Space Complexity: Can be high ($O(AL)$ where $A$ is alphabet size and $L$ is average length) if there are many words with no common prefixes. However, it saves space when storing many words with the same prefix (e.g., "inter", "interest", "internet").
4. Implementation (Python)
class TrieNode:
def __init__(self):
self.children = {} # Map char -> TrieNode
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word5. Use Cases
- Autocomplete: Suggesting words as you type.
- Spell Checkers: Quickly verifying if a word is in the dictionary.
- IP Routing: Longest prefix matching.
programming/algorithms programming/dictionaries-and-maps programming/graph-theory-basics