Suatu trie (prefix tree) ialah tree di mana setiap edge mewakili satu aksara dan setiap laluan dari root mengeja satu prefix. Perkataan yang berkongsi prefix berkongsi laluan yang sama, menjadikan carian prefix amat pantas.
Insert "cat", "car", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* marks end-of-word)
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word): # O(L), L = word length
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def starts_with(self, prefix): # O(L)
node = self.root
for ch in prefix:
if ch not in node.children: return False
node = node.children[ch]
return True
| Operasi | Masa |
|---|---|
| insert | O(L) |
| search | O(L) |
| pertanyaan prefix | O(L) |
Yang penting, kos bergantung pada panjang perkataan L, bukan bilangan perkataan yang disimpan.
Trie menggerakkan autolengkap, penyemak ejaan, jadual penghalaan IP, dan carian berasaskan kamus di mana padanan prefix penting.
Apabila hash set hanya menjawab "padanan tepat," trie secara tambahan menjawab "perkataan apa yang bermula dengan X?" dengan cekap.