Trie (prefiks ağacı) sətirləri hərf-hərf saxlayır: hər söz kökdən gedən yoldur, hər kənar bir hərfdir, ümumi prefiksli sözlər yolun əvvəlini bölüşür. Axtarış sətirin uzunluğundan asılıdır, lüğətin ölçüsündən yox, buna görə avtotamamlama, orfoqrafiya yoxlaması və IP marşrut cədvəllərinin arxasında trie dayanır.

Yeddi sözün trie-si: yaşıl düyünlər sözün sonudur
Yeddi sözün trie-si: yaşıl düyünlər sözün sonudur

Problem: prefiks sorğuları

"ca ilə başlayan sözlər hansılardır?" Sözlərdən ibarət set "car buradadır?" sualına O(L)-də cavab verir, prefiks sualı üçün isə bütün n sözü keçmək lazımdır: O(n · L). Trie prefiks boyunca enib altındakıları toplayaraq cavab verir.

Quruluş və əsas əməliyyatlar

Düyün children lüğətini (hərf və uşaq düyün) və end bayrağını saxlayır: söz burada bitir. Bayraq lazımdır, çünki prefiks hələ söz deyil: ca ağacda car və cat-ın hissəsi kimi var, amma əlavə edilməyib.

python
class TrieNode:
    def __init__(self):
        self.children = {}          # letter -> TrieNode
        self.end = False            # a word ends here

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

trie = Trie()
for w in ["car", "care", "cart", "cat", "do", "dog", "dot"]:
    trie.insert(w)

print(trie.search("car"), trie.search("ca"))
print(trie.starts_with("ca"), trie.starts_with("cb"))
text
True False
True False