# Trie

Adres: https://softwaredictionary.org/tr/terimler/trie
Kategori: Veri Yapıları
Son güncelleme: 2026-09-30
Türkçe karşılığı: önek ağacı
Okunuşu: tri ya da tray

Kısaca: Trie, string'leri karakter karakter saklayan ağaç biçimli bir veri yapısıdır; aynı öneki paylaşan tüm kelimeler kökten itibaren aynı yolu paylaşır.

## Trie nedir?

Önek ağacı (prefix tree) olarak da adlandırılan trie, kelimeler ya da anahtarlar gibi bir string kümesini her seviyede bir karakter olacak şekilde saklayan bir ağaçtır. Kök boş string'i temsil eder, her kenar bir karakter ekler ve düğüme giden yol eksiksiz bir kaydı hecelediğinde düğüm bir kelimenin sonu olarak işaretlenir. Aynı başlangıca sahip kelimeler bir yolu paylaştığı için `car`, `card` ve `care` kelimelerinin üçü de `c`, `a` ve `r` düğümlerini yeniden kullanır.

m uzunluğunda bir kelimeyi eklemek ya da aramak için kökten başlar ve karakter başına bir çocuk bağını izlersiniz; bu yüzden trie kaç kelime tutarsa tutsun ikisi de O(m) sürer. Bir önekle başlayan tüm kelimeleri bulmak da aynı derecede doğrudandır: önekin düğümüne O(m)'de inin, sonra altındaki her kelimeyi toplayın. Her düğüm genellikle çocuklarını küçük bir hash map'te ya da her olası karakter için bir yuvası olan sabit bir dizide saklar.

Kâğıt bir sözlükteki kenar dizinlerini düşünün: C bölümüne atlarsınız, sonra `ca` ile başlayan kelimelere, sonra `car`'a daraltırsınız; her harften sonra seçenekler azalır. Trie'ler otomatik tamamlamaya ve arama önerilerine, yazım denetleyicilerine ve kelime oyunlarına güç verir. Yönlendiriciler, yönlendirme tablolarında en uzun eşleşen adres önekini bulmak için yakın bir akrabasını kullanır.

Trie sıklıkla hash tablosuyla karşılaştırılır. Hash tablosu da her karakteri hash'lemesi gerektiği için tüm bir anahtarı ortalamada O(m) sürede arar, ancak `pre` ile başlayan kelimelerin hangileri olduğu gibi önek sorularını verimli yanıtlayamaz ve anahtarları sıralı tutmaz. Ödünleşim bellektir: sade bir trie çok sayıda düğüm kullanabilir; bu yüzden radix ağaçları gibi sıkıştırılmış türler tek çocuklu düğüm zincirlerini tek bir düğümde birleştirir.

## Önemli noktalar

- Trie, string'leri her seviyede bir karakter olacak şekilde saklar ve ortak öneke sahip kelimeler düğümleri paylaşır.
- Ekleme ve arama, kaç kelime saklandığından bağımsız olarak O(m) sürer; m kelimenin uzunluğudur.
- Bir önekle başlayan tüm kelimeleri bulmak, önekə ulaşmak için O(m) artı toplanan eşleşmelerle orantılı zaman alır.
- Trie'ler otomatik tamamlama, yazım denetimi ve yönlendirme tablolarında önek eşleştirme için kullanılır.
- Başlıca maliyet bellektir; radix ağaçları gibi sıkıştırılmış türler bunu azaltır.

## Örnek: İç içe Python dict'lerinden oluşan asgari bir trie

```python
def insert(node, word):
    for char in word:  # one step per character: O(m)
        node = node.setdefault(char, {})
    node["$"] = True   # "$" marks the end of a complete word

def has_prefix(node, prefix):
    for char in prefix:  # also O(m), however many words are stored
        if char not in node:
            return False
        node = node[char]
    return True
trie = {}
for word in ["car", "card", "care"]:
    insert(trie, word)  # all three words share the path c -> a -> r
print(has_prefix(trie, "car"), has_prefix(trie, "cat"))  # True False
```

## Sık sorulan sorular

**Buna neden trie deniyor?**

Ad, retrieval (geri getirme) sözcüğünün ortasından gelir. Adı 1960'ta ortaya atan Edward Fredkin bunu tree gibi telaffuz etmiştir, ancak birçok kişi şimdi tree ile karışmasın diye try der.

**Ne zaman hash tablosu yerine trie kullanmalıyım?**

Otomatik tamamlama ya da belirli bir metinle başlayan her anahtarı bulmak gibi önek sorgularına ihtiyacınız olduğunda veya anahtarları sıralı listelemek istediğinizde trie kullanın. Düz tam eşleşmeli aramalar için hash tablosu genellikle daha basittir ve daha az bellek kullanır.

**Trie'nin zaman karmaşıklığı nedir?**

Bir kelimeyi eklemek, silmek ya da aramak, kaç kelime saklandığından bağımsız olarak O(m) sürer; m kelimenin uzunluğudur. Belirli bir önekle başlayan tüm kelimeleri listelemek, önekə ulaşmak için O(m) artı sonuçların boyutuyla orantılı zaman alır.

---

Software Dictionary: https://softwaredictionary.org/tr · https://softwaredictionary.org/tr/llms.txt