---
title: 'Sözcük Ağaçları'
source: 'https://academia.sh/tr/kurslar/veri-yapilari/sozcuk-agaclari'
course: 'Veri Yapıları'
language: tr
updated: '2026-08-17T18:08:05+00:00'
license: 'CC BY-SA 4.0'
---

# Sözcük Ağaçları

Anahtarın yola dönüşmesi, ortak öneklerin paylaşılması, önek sorguları ve bellek–hız ödünleşimi.

Buraya kadarki arama yapıları anahtarları **bütün olarak** karşılaştırdı: iki dizgi
eşit mi, hangisi büyük. Anahtarlar dizgi olduğunda bu karşılaştırmaların her biri, en
kötü durumda dizgi uzunluğu kadar karakter incelemesi demektir.

Farklı bir yaklaşım, anahtarı bir bütün değil **karakter dizisi** olarak görmektir. Bu
durumda anahtar, ağaçta bir düğüm değil bir **yol** olur; karşılaştırma da bir kerede
değil, karakter karakter yapılır.

## Anahtar Bir Yoldur

**Sözcük ağacında (trie)** her kenar bir karaktere karşılık gelir. Kökten bir düğüme
giden yol üzerindeki karakterler, o düğümün temsil ettiği öneki oluşturur.

```
        (kök)
       /     \
     o         a
     |         |
     l         l
     |        / \
     ç       t   a
     |       |   |
     ü*      ı*  n*     (* : burada biten bir anahtar var)
     |
     m*
```

Bu ağaçta dört anahtar saklıdır: `olçü`, `olçüm`, `altı`, `alan`. `olçü` ve `olçüm`
anahtarlarının ortak öneki bir kez saklanmıştır; ikisini ayıran tek şey, `ü` düğümünün
de anahtar sonu işaretli olmasıdır.

**Anahtar sonu işareti** zorunludur: bir yolun üzerinden geçmek, o yolun bir anahtar
olduğu anlamına gelmez. `ol` yolu vardır ama `ol` anahtar değildir. Bu işaret olmadan yapı, yalnızca hangi öneklerin var olduğunu söyleyebilir; hangi
dizgilerin gerçekten saklandığını söyleyemez.

## Maliyet: Uzunluğa Bağlı, Sayıya Değil

Sözcük ağacında arama, anahtarın karakterlerini sırayla izlemektir. Adım sayısı,
anahtarın **uzunluğu** kadardır — ağaçta kaç anahtar bulunduğundan bağımsız.

$$
O(m), \quad m = \text{anahtar uzunluğu}
$$

Bu, dengeli arama ağacındaki $O(\log n)$ ile karşılaştırıldığında ilginç bir farktır:
milyon anahtar da olsa, on karakterlik bir anahtarın aranması on adımdır.

Karma tablosuyla karşılaştırma daha inceliklidir. Karma tablosunda arama "sabit"
sayılır, ancak karma değerinin hesaplanması anahtarın tamamını okur — yani $O(m)$. İki
yapının tekil arama maliyeti aynı mertebededir; ayrıldıkları yer, karma tablosunun
sunamadığı işlemlerdir.

```python
class SozcukAgaci:
    """Karakter dizilerini önek paylaşımıyla saklar."""

    def __init__(self) -> None:
        self.cocuklar: dict[str, "SozcukAgaci"] = {}
        self.anahtar_sonu = False

    def ekle(self, kelime: str) -> None:
        dugum = self
        for karakter in kelime:
            dugum = dugum.cocuklar.setdefault(karakter, SozcukAgaci())
        dugum.anahtar_sonu = True

    def _dugum_bul(self, onek: str) -> "SozcukAgaci | None":
        dugum = self
        for karakter in onek:
            if karakter not in dugum.cocuklar:
                return None
            dugum = dugum.cocuklar[karakter]
        return dugum

    def iceriyor_mu(self, kelime: str) -> bool:
        dugum = self._dugum_bul(kelime)
        return dugum is not None and dugum.anahtar_sonu

    def onek_var_mi(self, onek: str) -> bool:
        return self._dugum_bul(onek) is not None

    def onekle_baslayanlar(self, onek: str) -> list[str]:
        """Verilen önekle başlayan tüm anahtarları sıralı döndürür."""
        kok = self._dugum_bul(onek)
        if kok is None:
            return []
        sonuc: list[str] = []

        def gez(dugum: "SozcukAgaci", biriken: str) -> None:
            if dugum.anahtar_sonu:
                sonuc.append(onek + biriken)
            for karakter in sorted(dugum.cocuklar):        # sıralı gezinme
                gez(dugum.cocuklar[karakter], biriken + karakter)

        gez(kok, "")
        return sonuc


agac = SozcukAgaci()
for kelime in ("olcu", "olcum", "olcek", "alan", "alti"):
    agac.ekle(kelime)

print(agac.iceriyor_mu("olcum"), agac.iceriyor_mu("olc"))   # True False
print(agac.onek_var_mi("olc"))                              # True
print(agac.onekle_baslayanlar("ol"))     # ['olcek', 'olcu', 'olcum']
print(agac.onekle_baslayanlar("al"))     # ['alan', 'alti']
print(agac.onekle_baslayanlar("xy"))     # []
```

`iceriyor_mu("olc")` çağrısının yanlış dönmesi, anahtar sonu işaretinin işlevini
gösterir: yol vardır, anahtar yoktur.

## Önek Sorguları

Sözcük ağacının ayırt edici yeteneği son iki çağrıdadır. Bir önekle başlayan tüm
anahtarları bulmak, karma tablosunda **tüm anahtarların taranmasını** gerektirir;
sözcük ağacında önek düğümüne inip alt ağacı gezmek yeterlidir.

Tipik kullanım alanları:

- **Otomatik tamamlama.** Kullanıcının yazdığı önekle başlayan adaylar.
- **Sözlük ve yazım denetimi.** Var olan öneklerin izlenmesi, olası tamamlamalar; yazım
  önerileri, ağaçta küçük sapmalara izin veren bir gezinmeyle üretilir.
- **Yönlendirme tabloları.** Ağ müfredatındaki en uzun önek eşleme, adres bitleri
  üzerinde çalışan bir sözcük ağacıyla yapılır.
- **Sıralı gezinme.** Alt ağacın sıralı gezilmesi, anahtarları sözlük sırasında verir;
  karma tablosunun sunamadığı bir işlem.

## Bellek Ödünleşimi

Sözcük ağacının bedeli bellektir. Her karakter için bir düğüm oluşur ve her düğüm bir
çocuk eşlemesi taşır. Alfabesi geniş ve anahtarları ortak önek paylaşmayan bir kümede,
ağaç kendi verisinden büyük olabilir.

İki yaygın sıkıştırma vardır:

**Yolların birleştirilmesi.** Tek çocuklu düğüm zincirleri tek bir düğümde toplanır ve
kenar bir karakter yerine bir karakter dizisi taşır. Bu yapıya sıkıştırılmış sözcük
ağacı denir; anahtar sayısı az, anahtarlar uzun olduğunda büyük kazanç sağlar.

**Çocuk gösteriminin seçimi.** Küçük alfabelerde sabit boyutlu dizi (her karakter için
bir göz) hızlıdır ama seyrek düğümlerde yer israfıdır; eşleme kullanmak yeri azaltır,
erişimi bir miktar yavaşlatır.

## Bit Düzeyinde Sözcük Ağaçları

Anahtarlar dizgi olmak zorunda değildir. Herhangi bir değerin **bit dizisi** de bir yol
olarak kullanılabilir; bu durumda her düğümün en fazla iki çocuğu olur ve yapı ikili
ağaca dönüşür.

En bilinen uygulaması ağ yönlendirmesidir. Bir adres öneki, adresin ilk $k$ bitidir; en
uzun önek eşleme, kökten aşağı inip eşleşen en derin düğümü bulmaktır. Ağ müfredatındaki
yönlendirme tablosu araması bu yapıyla yapılır.

İkinci uygulama, tam sayı anahtarlı sözlüklerdir. Bit düzeyinde çalışan sıkıştırılmış
sözcük ağaçları, karma tablosuna alternatif olarak kullanılır: sıralı gezinme ve önek
sorgusu sunar, karma hesabı gerektirmez ve en kötü durum garantisi anahtar genişliğiyle
sınırlıdır.

Bilgisayarlar Nasıl Çalışır kursundaki bit düzeyi işlemler burada da doğrudan kullanılır:
her adımda ilgili bit, kaydırma ve maskeleme ile okunur.

## Karşılaştırma

| Ölçüt | Sözcük ağacı | Karma tablosu | Dengeli arama ağacı |
|---|---|---|---|
| Tekil arama | $O(m)$ | $O(m)$ ortalama | $O(m \log n)$ |
| Önek sorgusu | Doğrudan | Desteklemez | Aralık sorgusuyla kısmen |
| Sıralı gezinme | Var | Yok | Var |
| Bellek | Yüksek | Orta | Orta |
| En kötü durum | $O(m)$ | $O(n \cdot m)$ | $O(m \log n)$ |

Tablodaki değerler, anahtarların dizgi olduğu durumu varsayar; sayısal anahtarlarda
karşılaştırma sabit maliyetlidir ve karşılaştırmalı yapılar öne geçer.

Dengeli arama ağacındaki $\log n$ çarpanı, her düğümde bir dizgi karşılaştırması
yapılmasındandır — sözcük ağacında bu çarpan yoktur.

## Özet

- Sözcük ağacında anahtar bir düğümde değil, kökten inen bir yolda saklanır; ortak
  önekler bir kez tutulur.
- Anahtar sonu işareti zorunludur; bir yolun var olması, o yolun anahtar olduğu anlamına
  gelmez.
- Arama maliyeti anahtar uzunluğuna bağlıdır, saklanan anahtar sayısından bağımsızdır.
- Önekle başlayan tüm anahtarları listelemek, önek düğümünün alt ağacını gezmektir.
- Bedeli bellektir; yol sıkıştırma ve çocuk gösterimi seçimi bu maliyeti azaltır.
- Karma tablosunun sunamadığı önek sorgusu ve sıralı gezinme, bu yapının varlık
  nedenidir.

## Sonraki Adım

Buraya kadarki yapılar tekil anahtarlar üzerinde çalıştı. Bazı problemlerde ise sorgu bir
aralık hakkındadır: "şu iki dizin arasındaki değerlerin toplamı nedir" — ve bu sorgu,
veriler değişirken tekrar tekrar sorulur. Sonraki ders bu soruyu logaritmik maliyetle
yanıtlayan yapıları ele alacak.