Trie temelleri
Adım 1/10
Boş bir trie tek bir kök düğümden (node) ibarettir. Her kelime yoluna buradan başlar.
Fikir
Trie (prefix tree), kelimeleri bütün halinde saklamak yerine harf harf heceler. Her kenar tek bir karakter taşır, yani kökten aşağı inen yol bir prefix'tir (önek). Aynı prefix'i paylaşan kelimeler o düğümleri de paylaşır.
Düğüm (node) başına bir flag "burada bir kelime bitiyor" diye işaretler; o olmadan car kelimesini cart içindeki prefix'ten ayıramazsın.
Gerçek hayattan örnek
Eski bir kütüphane kart kataloğu düşün: A–C etiketli çekmeceler, içlerinde ikinci harf için ayraçlar, sonra üçüncü harf için. İki kitap da "Ca" ile başlıyor diye kimse başlığı iki kez saklamaz; etiketleri izlersin ve o ayracın altındaki her kitap bir eşleşmedir.
Kod
Sıra sende
Bu kod ne yazdırır?
root = {}
for word in ["do", "dorm"]:
node = root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
print(sorted(root["d"]["o"]))Mini quiz
1 / 3