Trie (drzewo prefiksów) to drzewo, w którym każda krawędź reprezentuje znak, a każda ścieżka od korzenia tworzy prefiks. Słowa, które mają wspólny prefiks, dzielą tę samą ścieżkę, co sprawia, że wyszukiwanie prefiksów jest niezwykle szybkie.
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
| Operacja | Czas |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |
Krucjalnie, koszt zależy od długości słowa L, a nie od liczby przechowywanych słów.
Trie są podstawą autouzupełniania, sprawdzaczy ortografii, tablic routingu IP i wyszukiwania opartego na słowniku, gdzie istotne jest dopasowanie prefiksu.
Gdy hash set udziela odpowiedzi tylko na pytanie "czy istnieje dokładnie to?", trie dodatkowo odpowiada na pytanie "które słowa zaczynają się na X?" w wydajny sposób.
Biblioteka pytań rekrutacyjnych IT ze szczegółowymi odpowiedziami — od Juniora do Seniora.
Wesprzyj