İçeriğe geç

Trie temelleri

Ders 1 / 4 · 5 dk

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

Bir trie'de tek bir kenar neyi temsil eder?