Trie
- Algoritmalar kursu
- İleri seviye
- Ders 50/56
- 4 dk
Önek arama için trie ağacını öğrenirsin.
Trie
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.
Uygulama init_trie fonksiyonu
init_trie() yaz. Boş trie kökünü (sözlük) döndür. print(init_trie()) ile yazdır.
Başlangıç kodu
def init_trie():
# Boş trie kökünü döndürÖrnek çözüm
def init_trie():
# Boş trie kökünü döndür
return {}
print(init_trie())Beklenen çıktı
{}
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 harf döngüsü
for ____ in word:for ch in word:Açıklama: ch doğru.
2 Boş trie ne ile başlar?
- []
- {} Doğru cevap
- 0
- ()
Açıklama: Boş trie {} ile başlar.
3 Trie: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
kök |
Başlangıç |
harf |
Düğüm |
'+' |
Kelime sonu |
sözlük |
Düğüm yapısı |