Trie
Trie
A Trie (Prefix Tree) is an ordered tree data structure used to store strings. Each node represents a single character, and shared prefixes share the same node paths. This allows constant time retrieval proportional to key length, regardless of dictionary size.
Complexity Profile
| Case | Complexity |
|---|---|
| Best Case | O(L) - Key Length |
| Average Case | O(L) |
| Worst Case | O(L) |
| Space Complexity | O(ALPHABET_SIZE * N * L) |
Code Implementation
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_end_of_word = True
def search(self, word):
curr = self.root
for char in word:
if char not in curr.children:
return False
curr = curr.children[char]
return curr.is_end_of_wordReal-World Applications
- Autocomplete widgets on search bars.
- IP routing lookup tables.
- Spell checkers and dictionary validation tools.