Trie

Önek arama için trie ağacını öğrenirsin.

Trie, kelimeleri önek (prefix) ile saklayan ağaçtır. Her düğüm bir harfi temsil eder; kökten yaprağa olan yol bir kelime oluşturur.

Otomatik tamamlama, yazım denetimi gibi önek aramalarında verimlidir. Ekleme ve arama O(L) zamanda yapılır; L kelime uzunluğudur.

Sözlük yapısı

Trie düğümleri bir sözlük olarak temsil edilir. Her düğüm, harften alt düğüme eşleme içerir. Kelime sonu '$' işaretiyle belirtilir.

Bu gösterim, yeni harfler eklendikçe ağacın otomatik büyümesini sağlar. Boş trie {} ile başlar.

init_trie() yaz. Boş trie kökünü (sözlük) döndür. print(init_trie()) ile yazdır.

Örnek çözümü göster

def init_trie():
    # Boş trie kökünü döndür
    return {}
print(init_trie())

Sıradaki ders: Segment tree