Trie (prefix tree) nedir? Ekleme ve önek arama işlemlerini yazın.

Trie, string'leri karakter karakter saklayan bir ağaçtır. Her düğüm bir karakteri temsil eder; kökten bir düğüme giden yol bir öneki oluşturur. Kelime sonları bir bayrakla işaretlenir.

Kullanım alanları: otomatik tamamlama, yazım denetimi, IP yönlendirme (longest prefix match), kelime oyunları.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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.is_end = True

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

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

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

    def autocomplete(self, prefix, limit=5):
        node, out = self._find(prefix), []
        def dfs(n, path):
            if len(out) >= limit: return
            if n.is_end: out.append(prefix + path)
            for ch in sorted(n.children):
                dfs(n.children[ch], path + ch)
        if node: dfs(node, "")
        return out

Karmaşıklık

• Ekleme / arama / önek kontrolü: `O(L)` (L = kelime uzunluğu), sözlükteki kelime sayısından bağımsız.
• Bellek: en kötü O(toplam karakter sayısı); çok sayıda düğüm nedeniyle hash set'ten fazla bellek harcayabilir.

Hash set ile karşılaştırma

Tam kelime araması için hash set de ortalama O(L)'dir. Trie'nin üstünlüğü önek sorgularıdır: "ka ile başlayan kelimeler" sorusunu set ile tüm kelimeleri tarayarak cevaplamak gerekir.

Bellek optimizasyonu için tek çocuklu zincirleri birleştiren radix tree (compressed trie) kullanılır.