Önek Ağacı (Trie)

#Nasıl çalışır?

Trie (önek ağacı, prefix tree), kelimeleri harf harf saklayan bir ağaçtır. Her kenar bir harfi temsil eder; kökten bir düğüme inen yol bir öneki yazar.

Ortak öneke sahip kelimeler aynı yolu paylaşır: "car" ve "cart" için c-a-r düğümleri bir kez saklanır. Bir kelimenin nerede bittiğini bilmek için düğümlerde "kelime sonu" işareti tutulur.

Arama süresi trie'deki kelime sayısına değil, aranan kelimenin uzunluğuna bağlıdır. Bu yüzden otomatik tamamlama gibi önek sorgularında çok hızlıdır.

#Kendin dene

#Temel işlemler

insert(word)

Kelimenin harflerini kökten itibaren takip eder, eksik düğümleri oluşturur ve son düğümü kelime sonu olarak işaretler.

search(word)

Harfleri takip eder; yol kopmazsa ve son düğüm kelime sonuysa true döner.

startsWith(prefix)

Yalnızca yolun var olup olmadığına bakar; bu önekle başlayan en az bir kelime varsa true döner.

delete(word)

Kelime sonu işaretini kaldırır; başka kelimeye ait olmayan düğümleri siler.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

from typing import Dict, Optional


class Node:
    def __init__(self) -> None:
        self.children: Dict[str, "Node"] = {}
        self.is_word = False  # a word ends at this node


class Trie:
    def __init__(self) -> None:
        self._root = Node()

    def insert(self, word: str) -> None:
        node = self._root
        for c in word:
            node = node.children.setdefault(c, Node())
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def _walk(self, text: str) -> Optional[Node]:
        """Follows the letters; None if the path breaks off."""
        node = self._root
        for c in text:
            node = node.children.get(c)
            if node is None:
                return None
        return node


trie = Trie()
for word in ["cat", "car", "cart", "dog"]:
    trie.insert(word)

show = lambda b: "true" if b else "false"
print(show(trie.search("car")))      # true
print(show(trie.search("ca")))       # false: only a prefix
print(show(trie.starts_with("ca")))  # true
print(show(trie.search("do")))       # false

#Karmaşıklık

L, kelimenin (ya da önekin) uzunluğudur. Çocuklar 26 elemanlı bir dizide tutulursa her adım O(1) olur ama bellek harcar; hash map ile bellek azalır, adım ortalama O(1) olur.

#Ne zaman kullanılır?

Otomatik tamamlama, yazım denetimi, sözlük oyunları (Boggle, kelime bulmaca), IP yönlendirme tablolarında en uzun önek eşleşmesi ve çok sayıda kelimeyi aynı metinde arama (Aho-Corasick) trie üzerine kuruludur.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.