Trie (önek ağacı) nedir ve ne zaman yararlıdır?

Question

Accepted Answer

**Trie** (önek ağacı), her **kenarın** bir karakteri temsil ettiği ve **kökten başlayan her yolun** bir ön eki oluşturduğu bir ağaçtır. Aynı öneki paylaşan sözcükler aynı yolu paylaşır, bu da önek aramasını son derece hızlı hale getirir.

## Yapı

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## Kod

```python
class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):           # O(L), L = word length
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    def starts_with(self, prefix):    # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True
```

## Karmaşıklık

| İşlem | Zaman |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Önemlisi, maliyet **sözcük uzunluğu L** üzerine bağlıdır, depolanan sözcük sayısı *değil*.

## Ödünleşmeler

- **Güçlü Yönler:** hızlı önek araması; otomatik tamamlama; paylaşılan önekler benzer sözcükler için alanı tasarrufu sağlar.
- **Zayıf Yönler:** düğüm başına yüksek bellek yükü (her düğüm için bir alt harita); ilgisiz anahtarlar için hash setinden daha fazla alan kullanabilir.

## Neden önemli

Trie'ler, otomatik tamamlama, yazım denetleyici, IP yönlendirme tabloları ve **önek** eşleşmesinin önemli olduğu sözlük tabanlı aramayı güçlendirir.

Bir hash set sadece "tam eşleşme" sorusuna cevap verirken, trie ek olarak "X ile başlayan sözcükler hangileridir?" sorusuna verimli bir şekilde cevap verir.