---
title: 'Veri Yapıları'
source: 'https://academia.sh/tr/kurslar/veri-yapilari'
language: tr
updated: '2026-08-17T04:39:30+00:00'
license: 'CC BY-SA 4.0'
lessons: 26
outcomes:
    - 'Doğrusal ve bağlantılı veri yapılarının bellek düzenini ve işlem maliyetini karşılaştırır'
    - 'Bir probleme uygun veri yapısını maliyet gerekçesiyle seçer'
    - 'Ağaç ve çizge yapılarını gezinme algoritmalarıyla birlikte kullanır'
---

# Veri Yapıları

Doğrusal yapılardan ağaç ve çizgelere, verinin bellekteki düzeni ile işlem maliyeti arasındaki ilişkiyi kuran orta seviye kurs.

## Doğrusal Yapılar

Diziler, bağlı listeler, yığıtlar, kuyruklar ve atlama listeleri; bitişik ve bağlantılı yerleşimin sonuçları.

### Diziler

Source: https://academia.sh/tr/kurslar/veri-yapilari/diziler

Bitişik bellek yerleşimi, adres aritmetiğiyle sabit zamanlı erişim, sabit boyut kısıtı ve maliyet dili.

Programlama Temelleri kursunda listeler kullanıldı: elemanlar eklendi, gezildi,
süzüldü. Bu işlemlerin bellekte neye karşılık geldiği ve neden bazılarının diğerlerinden
pahalı olduğu açık bırakıldı.

Bu kurs o boşluğu doldurur. Sorusu şudur: veri bellekte nasıl düzenlenirse hangi işlem
ucuz, hangisi pahalı olur? Yanıt her seferinde aynı iki kaynaktan gelir — Bilgisayarlar
Nasıl Çalışır kursunda kurulan bellek modeli ve yapının kendi düzeni.

#### Bitişik Yerleşim

**Dizi (array)**, aynı tipteki elemanları bellekte **bitişik** tutan yapıdır. İlk
elemanın adresi biliniyorsa, diğerlerinin adresi hesaplanabilir:

$$
\text{adres}(i) = \text{taban} + i \times \text{eleman boyutu}
$$

Dört baytlık tam sayılardan oluşan bir dizi `1000` adresinden başlıyorsa, `3` numaralı
elemanın — yani baştan dördüncünün — adresi $1000 + 3 \times 4 = 1012$'dir. Hesap tek bir
çarpma ve bir toplamadır; dizinin uzunluğundan bağımsızdır.

Bu, dizinin ayırt edici özelliğidir: **herhangi bir elemana, sırasını bilerek doğrudan
erişilir.** Beşinci elemana ulaşmak için önceki dördünün üzerinden geçmek gerekmez.

Yerleşimin ikinci sonucu, dizinin tek tip eleman taşımasıdır. Adres aritmetiği,
elemanların eşit boyutta olmasına dayanır; farklı boyutlarda elemanlar bitişik
dizilseydi $i$'nci elemanın yeri hesaplanamaz, aranması gerekirdi.

#### Maliyet Dili

Bu kurs boyunca işlemlerin maliyeti karşılaştırılacaktır. Karşılaştırma için üç ifade
yeterlidir; biçimsel tanımları **Algoritmalar** kursunda verilir.

- **Sabit zaman**, $O(1)$: İşin süresi veri büyüklüğünden bağımsızdır. Dizinin
  $i$'nci elemanına erişim böyledir.
- **Doğrusal zaman**, $O(n)$: Süre, eleman sayısıyla orantılı büyür. Bir diziyi baştan
  sona taramak böyledir.
- **Logaritmik zaman**, $O(\log n)$: Her adımda arama alanı sabit bir oranda küçülür.
  Sıralı bir dizide ikili arama böyledir.

Gösterim, sabit çarpanları ve düşük dereceli terimleri yok sayar; ölçtüğü şey, veri
büyüdükçe maliyetin **hangi hızla** arttığıdır.

#### Dizinin İşlem Maliyetleri

| İşlem | Maliyet | Gerekçe |
|---|---|---|
| $i$'nci elemana erişim | $O(1)$ | Adres aritmetiği |
| Sıralı olmayan dizide arama | $O(n)$ | En kötü durumda tüm elemanlar |
| Sıralı dizide arama | $O(\log n)$ | Her adımda aralık yarılanır |
| Sona ekleme (yer varsa) | $O(1)$ | Tek yazma |
| Başa veya ortaya ekleme | $O(n)$ | Sonraki elemanların kaydırılması |
| Ortadan silme | $O(n)$ | Boşluğun kapatılması |

Ekleme ve silmenin pahalı olması, bitişik yerleşimin doğrudan bedelidir. Beş elemanlı
bir dizinin başına eleman eklemek, var olan beş elemanın her birini bir sıra ileri
taşımayı gerektirir; yerleşim bitişik kalmalıdır, çünkü adres aritmetiği buna dayanır.

```python
def basa_ekle(dizi: list[int], deger: int) -> int:
    """Diziyi bir sıra kaydırarak başa ekler; kaydırılan eleman sayısını döndürür."""
    dizi.append(None)                      # sona yer aç
    kaydirma = 0
    for i in range(len(dizi) - 1, 0, -1):  # sondan başa doğru kaydır
        dizi[i] = dizi[i - 1]
        kaydirma += 1
    dizi[0] = deger
    return kaydirma


olcumler = [12, 18, 7, 25, 14]
print(basa_ekle(olcumler, 30))     # 5   — beş eleman kaydırıldı
print(olcumler)                    # [30, 12, 18, 7, 25, 14]
```

Kaydırma sayısı, dizinin uzunluğuna eşittir; bu, tablodaki $O(n)$ satırının sayımla
gösterilmiş hâlidir.

#### Sabit Boyut Kısıtı

Klasik bir dizi, yaratıldığı anda boyutu belirlenen bir bellek bloğudur. Blok
bitişik olduğundan, sonradan büyütmek genellikle mümkün değildir: dizinin hemen
ardındaki bellek başka bir veri tarafından kullanılıyor olabilir.

Bu kısıtın iki sonucu vardır. Gereğinden büyük ayrılan dizi bellek israfıdır; küçük
ayrılan dizi ise dolduğunda kullanılamaz hâle gelir. Programın kaç eleman tutacağı
önceden bilinmiyorsa, sabit boyutlu dizi doğrudan çözüm değildir.

Sonraki dersin konusu, tam olarak bu kısıtın nasıl aşıldığıdır.

#### Dizin Denetimi

Adres aritmetiği, verilen dizinin geçerli olduğunu varsayar. Dizin aralık dışındaysa
hesaplanan adres, dizinin dışındaki bir bellek konumunu gösterir.

Diller bu duruma iki farklı yanıt verir. **Denetim yapanlar**, her erişimde dizini sınır
ile karşılaştırır ve aşımda hata üretir; bedeli, erişim başına birkaç komuttur.
**Denetim yapmayanlar** hesabı doğrudan uygular; erişim en hızlı hâlindedir, ancak
aralık dışı bir dizin, komşu verinin okunmasına veya üzerine yazılmasına yol açar.

İkinci davranış, Bilgisayarlar Nasıl Çalışır kursunda tanımsız davranış başlığı altında
geçmişti. Sonucu yalnızca yanlış değer değildir: dizinin dışına yazmak, çağrı
çerçevesindeki dönüş adresini bozabilir. Bu, bellek güvenliği açıklarının en bilinen
sınıfıdır ve siber güvenlik müfredatında ayrıca ele alınır.

#### Çok Boyutlu Diziler

İki boyutlu bir dizi de bellekte tek boyutlu olarak durur; satırlar art arda yerleştirilir.
Buna **satır öncelikli yerleşim** denir ve dizin hesabı şöyle olur:

$$
\text{konum}(i, j) = i \times \text{sütun sayısı} + j
$$

```python
SUTUN = 4
duz = [0] * (3 * SUTUN)          # 3 satır, 4 sütunluk tablo tek dizide

def yaz(i: int, j: int, deger: int) -> None:
    duz[i * SUTUN + j] = deger

def oku(i: int, j: int) -> int:
    return duz[i * SUTUN + j]

yaz(1, 2, 99)
print(oku(1, 2), duz)            # 99 [0, 0, 0, 0, 0, 0, 99, 0, 0, 0, 0, 0]
```

`99` değerinin düz dizide `6` numaralı konumda ($1 \times 4 + 2$) durması, iki boyutun
tek boyuta nasıl indirildiğini gösterir.

Bu yerleşimin başarım sonucu, Bilgisayarlar Nasıl Çalışır kursunun önbellek dersinde
hesaplanmıştı: satır boyunca gezinme ardışık adresleri okur, sütun boyunca gezinme her
adımda bir satır uzunluğu atlar. Aynı sayıda toplama için taşınan veri miktarı, önbellek
satırına sığan eleman sayısı kadar farklıdır.

#### Diziler Neden Yaygın

Dizinin ekleme ve silme maliyetleri yüksek olmasına karşın, pratikte en sık kullanılan
yapı olmasının üç nedeni vardır.

**Erişim maliyeti en düşüktür.** Sabit zamanlı ve tek bir adres hesabı kadar ucuzdur.

**Önbellek davranışı en iyisidir.** Bitişik yerleşim, uzamsal yerellikten en çok
yararlanan düzendir; bir eleman getirildiğinde komşuları da önbelleğe girer.

**Ek yer tutmaz.** Bağlantılı yapıların aksine, eleman başına işaretçi saklanmaz.

Bu üç nedenle, "hangi yapı" sorusunun varsayılan yanıtı dizidir; başka bir yapı, ancak
dizinin zayıf olduğu bir işlem baskınsa seçilir. Bu kursun geri kalanı, o durumların
neler olduğunu ve hangi yapının hangi maliyeti düşürdüğünü gösterir.

#### Maliyet Tablosu

Kurs boyunca aşağıdaki tablo satır satır büyüyecektir. İlk satır bu dersin sonucudur:

| Yapı | Erişim | Arama | Başa ekleme | Sona ekleme | Ortadan silme |
|---|---|---|---|---|---|
| Dizi (sabit boyut) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ |

\* Yer kaldığı sürece; dizi dolduğunda ekleme yapılamaz.

#### Özet

- Dizi, aynı tipteki elemanları bitişik tutar; $i$'nci elemanın adresi taban adres ve
  eleman boyutundan hesaplanır.
- Bu hesap dizinin uzunluğundan bağımsız olduğu için erişim sabit zamanlıdır.
- Ekleme ve silme, bitişikliği korumak için eleman kaydırmayı gerektirir ve doğrusal
  zamanlıdır.
- Sabit boyut kısıtı, bitişik bloğun sonradan büyütülememesinden doğar.
- Çok boyutlu diziler bellekte tek boyutlu durur; satır öncelikli yerleşim, gezinme
  yönünün önbellek davranışını belirlemesine yol açar.
- Erişim maliyeti, önbellek uyumu ve ek yer tutmaması nedeniyle dizi, varsayılan
  seçimdir.

#### Sonraki Adım

Sabit boyut kısıtı, eleman sayısı önceden bilinmeyen problemlerde diziyi kullanılamaz
kılıyor. Sonraki ders, diziyi taşımaya dayalı bir çözümle bu kısıtı kaldıracak ve bu
çözümün maliyetinin neden göründüğü kadar yüksek olmadığını — amortize maliyet
kavramıyla — gösterecek.

### Dinamik Diziler

Source: https://academia.sh/tr/kurslar/veri-yapilari/dinamik-diziler

Kapasite büyütme, büyütme çarpanının seçimi, amortize maliyet çözümlemesi ve küçülme eşiği.

Önceki ders, dizinin sabit boyutlu bir bitişik blok olduğunu ve bu bloğun sonradan
büyütülemediğini kurdu. Eleman sayısı önceden bilinmediğinde bu kısıt bağlayıcıdır.

Çözüm, kısıtı ortadan kaldırmak değil, onunla yaşamaktır: dizi dolduğunda daha büyük
yeni bir dizi ayrılır, eski elemanlar oraya kopyalanır ve eski blok bırakılır. Bu yapıya
**dinamik dizi (dynamic array)** denir.

#### Kapasite ve Uzunluk

Dinamik dizi iki sayı tutar:

- **Uzunluk:** İçindeki gerçek eleman sayısı.
- **Kapasite:** Ayrılmış bloğa sığabilecek en fazla eleman sayısı.

Kapasite her zaman uzunluğa eşit veya ondan büyüktür. Aradaki fark, henüz kullanılmayan
ama ayrılmış olan yerdir; sona ekleme bu boşluğu kullandığı sürece ucuzdur.

Uzunluk kapasiteye ulaştığında **yeniden ayırma** gerekir: yeni ve daha büyük bir blok
ayrılır, tüm elemanlar kopyalanır. Kopyalama, eleman sayısıyla orantılıdır — yani
$O(n)$.

#### Büyütme Çarpanı

Kritik soru şudur: yeni kapasite ne kadar olmalıdır?

**Sabit miktarda büyütme** — her seferinde kapasiteye sabit bir sayı eklemek — kötü bir
seçimdir. Kapasite birer birer artırılsaydı, $n$ eleman eklemek için yapılan toplam
kopyalama şu olurdu:

$$
1 + 2 + 3 + \dots + (n-1) = \frac{n(n-1)}{2}
$$

Bu, $O(n^2)$ demektir: bin eleman eklemek yaklaşık yarım milyon kopyalama yapar.

**Katlayarak büyütme** — kapasiteyi her defasında bir çarpanla (yaygın olarak iki ile)
çarpmak — toplam maliyeti kökten değiştirir. Kapasite $1$'den başlayıp ikiye
katlanıyorsa, $n$ elemana ulaşana kadar yapılan kopyalamaların toplamı:

$$
1 + 2 + 4 + \dots + \frac{n}{2} < n
$$

Geometrik toplamın kendisi, son terimin iki katından küçüktür. $n$ tam bir ikinin kuvveti
değilse kapasite bir üstteki kuvvete çıkar ve toplam $n$'yi biraz aşabilir — bin eleman için
1023 kopyalama gibi — ama her durumda $2n$'nin altında kalır; ekleme başına düşen ortalama
maliyet **sabittir**.

#### Amortize Maliyet

Bu gözlem bir kavramı gerektirir. Tek tek bakıldığında sona ekleme işlemlerinin çoğu
$O(1)$, bazıları $O(n)$'dir; en kötü durum maliyeti doğrusaldır.

Ancak pahalı işlemler seyrektir ve her pahalı işlemden sonra kapasite iki katına
çıktığı için bir sonraki pahalı işleme kadar iki kat daha fazla ucuz işlem yapılır. Bir
işlem dizisinin **toplam** maliyetini işlem sayısına bölerek elde edilen değere
**amortize maliyet** denir.

Dinamik dizide sona eklemenin amortize maliyeti $O(1)$'dir. Bu, "her ekleme sabit
sürer" demek değildir; "$n$ ekleme toplamda $O(n)$ sürer" demektir. Ayrım, gecikmeye
duyarlı sistemlerde önem kazanır: tek bir eklemenin uzun sürebileceği bilinmelidir.

```python
class DinamikDizi:
    """Kapasitesini ikiye katlayarak büyüyen dizi."""

    def __init__(self) -> None:
        self._blok: list = [None]      # kapasite 1 ile başlar
        self._uzunluk = 0
        self.kopyalama = 0             # ölçüm için sayaç

    def __len__(self) -> int:
        return self._uzunluk

    def kapasite(self) -> int:
        return len(self._blok)

    def ekle(self, deger: int) -> None:
        if self._uzunluk == self.kapasite():
            self._buyut()
        self._blok[self._uzunluk] = deger
        self._uzunluk += 1

    def _buyut(self) -> None:
        yeni = [None] * (self.kapasite() * 2)
        for i in range(self._uzunluk):        # her eleman yeni bloğa taşınır
            yeni[i] = self._blok[i]
            self.kopyalama += 1
        self._blok = yeni

    def __getitem__(self, i: int) -> int:
        if not 0 <= i < self._uzunluk:
            raise IndexError("dizin aralık dışında")
        return self._blok[i]


dizi = DinamikDizi()
for deger in range(16):
    dizi.ekle(deger)

print(len(dizi), dizi.kapasite())     # 16 16
print(dizi.kopyalama)                 # 15  — toplam kopyalama, eleman sayısından az
print(dizi[3])                        # 3
```

On altı ekleme için yapılan kopyalama sayısı $1 + 2 + 4 + 8 = 15$'tir. Ekleme başına
ortalama bir kopyalamadan az; geometrik toplamın verdiği sınır sayımla doğrulanmıştır.

Bu sayım, amortize çözümlemenin en sade biçimidir: her ekleme kendi maliyetinin yanında
ileride yapılacak kopyalama için bir pay biriktirir; yeniden ayırma geldiğinde bu
birikmiş paylar maliyeti karşılar.

Çarpanın iki olması zorunlu değildir. Daha küçük bir çarpan (örneğin $1{,}5$) daha az
boş yer bırakır ama daha sık kopyalar; daha büyük çarpan tersini yapar. Her iki durumda
da amortize maliyet sabit kalır — değişen, sabit çarpanın büyüklüğüdür.

#### Önceden Ayırma

Eleman sayısı önceden biliniyorsa, büyüme hiç yaşanmayabilir. Çoğu dinamik dizi
gerçekleştirimi, kapasiteyi baştan belirlemeye izin veren bir işlem sunar.

Kazanç iki yönlüdür. Yeniden ayırma ve kopyalama tümüyle ortadan kalkar; ve ayrılan blok
tek parça olduğu için bellek parçalanması azalır. Bin elemanlık bir sonucun üretileceği
biliniyorsa, kapasitenin baştan bin verilmesi on yeniden ayırmayı önler.

```python
sonuc = []
# Kapasite baştan bilinen durumda, dilin sunduğu ön ayırma kullanılır.
# Ön ayırma yoksa, sonucu doğrudan hedef boyutta üretmek aynı işi görür:
hazir = [0] * 1000                      # tek ayırma, kopyalama yok
for i in range(1000):
    hazir[i] = i * 3
print(len(hazir), hazir[999])           # 1000 2997
```

Bu, erken eniyileme değildir: son boyutun bilindiği durumlarda ön ayırma, kodun
okunabilirliğini de artırır — niyet açıkça yazılmış olur.

#### Küçülme ve Salınım

Elemanlar silindiğinde kapasitenin de düşürülmesi beklenir; aksi hâlde bir kez büyüyen
dizi belleği bırakmaz.

Küçültme eşiği dikkatle seçilmelidir. Kapasite, uzunluk kapasitenin yarısına indiğinde
yarıya düşürülürse **salınım** oluşur: dizi tam sınırdayken art arda yapılan bir ekleme
ve bir silme, her seferinde yeniden ayırma tetikler. Her işlem $O(n)$ olur ve amortize
kazanç yok olur.

Standart çözüm, eşikleri ayırmaktır: kapasite dolduğunda ikiye katlanır, ancak yalnızca
uzunluk kapasitenin **dörtte birine** indiğinde yarıya düşürülür. Aradaki boşluk,
sınırda gidip gelen işlemlerin yeniden ayırma tetiklemesini engeller.

#### Gerçek Dillerdeki Karşılığı

Çoğu dilin standart "liste" veya "vektör" yapısı, bir dinamik dizidir. Sona ekleme
amortize sabit, başa ekleme doğrusaldır; bu asimetri, kod yazarken hangi ucun
kullanılacağını belirler.

Bir ayrıntı, elemanların ne saklandığıdır. Sabit genişlikli tipler doğrudan blokta
tutulabilir; nesne referansları saklandığında ise blok işaretçiler taşır ve gerçek
değerler öbekte dağınık durur. İkinci düzen esneklik verir, önbellek uyumunu düşürür.
Bilgisayarlar Nasıl Çalışır kursundaki bitişik yerleşim tartışması bu ayrımı içeriyordu.

#### Maliyet Tablosu

| Yapı | Erişim | Arama | Başa ekleme | Sona ekleme | Ortadan silme |
|---|---|---|---|---|---|
| Dizi (sabit boyut) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ |
| Dinamik dizi | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ amortize | $O(n)$ |

\* Yer kaldığı sürece.

#### Özet

- Dinamik dizi, dolduğunda daha büyük bir blok ayırıp elemanları kopyalayarak sabit
  boyut kısıtını aşar.
- Kapasite ayrılmış yeri, uzunluk gerçek eleman sayısını gösterir.
- Sabit miktarda büyütme toplam maliyeti $O(n^2)$ yapar; katlayarak büyütmede toplam
  kopyalama $n$'den azdır.
- Amortize maliyet, bir işlem dizisinin toplam maliyetinin işlem sayısına bölünmesidir;
  sona eklemenin amortize maliyeti sabittir, tek bir eklemeninki değildir.
- Küçültme eşiği büyütme eşiğinden ayrı seçilir; aksi hâlde sınırdaki işlemler salınım
  üretir.

#### Sonraki Adım

Dinamik dizi, sona eklemeyi ucuzlattı ama başa ve ortaya ekleme hâlâ doğrusal. Kaydırma
maliyetinin kaynağı bitişik yerleşimdi. Sonraki ders, bitişikliği tümüyle terk eden bir
yapıyı — bağlı listeyi — ve bu değiş tokuşun neyi kazanıp neyi kaybettirdiğini ele alacak.

### Bağlı Listeler

Source: https://academia.sh/tr/kurslar/veri-yapilari/bagli-listeler

Düğüm ve bağ yapısı, tek ve çift yönlü listeler, işaretçi yeniden bağlamanın maliyeti ve pratikteki sınırları.

Dizinin ekleme ve silme maliyeti, tek bir gereklilikten doğuyordu: elemanların bitişik
durması. Bitişiklik terk edilirse kaydırma da ortadan kalkar.

**Bağlı liste (linked list)** bu değiş tokuşu yapar. Elemanlar bellekte istedikleri
yerde durur; sıra, her elemanın bir sonrakinin adresini taşımasıyla kurulur.

#### Düğüm ve Bağ

Yapının birimi **düğümdür (node)**: bir değer ve bir sonraki düğümün adresi.

```
baş → [12 | •] → [18 | •] → [7 | •] → [25 | ⏚]
```

Son düğümün bağı boştur; listenin sonunu bu boşluk belirtir. Listenin kendisi tek bir
şeyle temsil edilir: ilk düğümün adresi, yani **baş**.

Adres aritmetiği burada geçersizdir. Üçüncü elemanın nerede olduğu hesaplanamaz;
baştan başlanıp iki bağ izlenmelidir. Bu, dizinin sabit zamanlı erişimini kaybetmek
demektir: bağlı listede $i$'nci elemana erişim $O(n)$'dir.

```python
class Dugum:
    """Bir değer ve bir sonraki düğümün bağı."""

    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.sonraki: "Dugum | None" = None


class BagliListe:
    def __init__(self) -> None:
        self.bas: Dugum | None = None
        self.uzunluk = 0

    def basa_ekle(self, deger: int) -> None:
        """Yeni düğümü başa bağlar: sabit zamanlı."""
        yeni = Dugum(deger)
        yeni.sonraki = self.bas
        self.bas = yeni
        self.uzunluk += 1

    def bul(self, deger: int) -> int:
        """Değerin sırasını döndürür; yoksa -1. İzlenen bağ sayısı kadar adım atar."""
        sira = 0
        dugum = self.bas
        while dugum is not None:
            if dugum.deger == deger:
                return sira
            dugum = dugum.sonraki
            sira += 1
        return -1

    def degerler(self) -> list[int]:
        sonuc = []
        dugum = self.bas
        while dugum is not None:
            sonuc.append(dugum.deger)
            dugum = dugum.sonraki
        return sonuc


liste = BagliListe()
for olcum in (25, 7, 18, 12):        # ters sırada eklenir
    liste.basa_ekle(olcum)

print(liste.degerler())              # [12, 18, 7, 25]
print(liste.bul(7), liste.bul(99))   # 2 -1
print(liste.uzunluk)                 # 4
```

Başa ekleme sabit zamanlıdır: iki bağ yazılır, hiçbir eleman taşınmaz. Dizide aynı
işlem tüm elemanları kaydırıyordu.

#### Konum Bulmak ile Bağlamak

Bağlı listenin en sık yanlış anlaşılan yanı şudur: **ekleme ve silme ucuzdur, ancak
yerini bulmak pahalıdır.**

Elde bir düğüm referansı varsa, ondan sonrasına eklemek birkaç işaretçi yazımıdır —
$O(1)$. Ancak "onuncu elemandan sonraya ekle" denirse, önce dokuz bağ izlenir; toplam
maliyet yine $O(n)$ olur.

Bu ayrım, bağlı listenin doğru kullanım alanını belirler: ilgili düğümün referansı zaten
elde tutuluyorsa yapı kazanç sağlar; her işlemde baştan aranıyorsa sağlamaz.

#### Çift Yönlü Liste

Tek yönlü listede bir düğümü silmek, **önceki** düğümün bağını değiştirmeyi gerektirir;
oysa düğümden geriye gidilemez. Çözüm, her düğüme bir de geri bağ eklemektir.

**Çift yönlü listede** her düğüm hem sonrakini hem öncekini bilir. Sonuçları:

- Elde bir düğüm referansı varken silme $O(1)$ olur.
- Liste iki yönde gezilebilir.
- Her düğüm bir işaretçi daha taşır; bellek ek yükü artar.
- Her ekleme ve silmede iki yerine dört bağ güncellenir; kod daha hatalıdır.

Baş ve son işaretçilerinin ikisi birden tutulursa, listenin her iki ucuna ekleme sabit
zamanlı olur. Bu, sonraki iki dersteki yığıt ve kuyruk yapılarının doğal temelidir.

Üçüncü bir varyant, son düğümün başa bağlandığı **dairesel listedir**; sıradaki öğeye
sürekli dönen zamanlama ve tampon uygulamalarında kullanılır.

#### Sınır Düğümü

Bağlı liste kodunun hata kaynağı, uç durumlardır: boş listeye ekleme, ilk düğümü silme,
son düğümden sonrasına ekleme. Her biri ayrı bir `if` bloğu gerektirir ve bu bloklardan
biri unutulduğunda hata, yalnızca o durumda ortaya çıkar.

**Sınır düğümü (sentinel)**, değer taşımayan sahte bir düğümdür ve listenin başına
kalıcı olarak yerleştirilir. Baş her zaman var olduğundan, "ilk düğümü silmek" ayrı bir
durum olmaktan çıkar — her düğümün bir öncesi vardır.

```python
class SinirliListe:
    """Baştaki sınır düğümü sayesinde silme tek bir kodla yürür."""

    def __init__(self) -> None:
        self.sinir = Dugum(0)          # değeri kullanılmaz

    def ekle(self, deger: int) -> None:
        yeni = Dugum(deger)
        yeni.sonraki = self.sinir.sonraki
        self.sinir.sonraki = yeni

    def sil(self, deger: int) -> bool:
        onceki = self.sinir            # her zaman geçerli bir "önceki" var
        while onceki.sonraki is not None:
            if onceki.sonraki.deger == deger:
                onceki.sonraki = onceki.sonraki.sonraki
                return True
            onceki = onceki.sonraki
        return False


liste = SinirliListe()
for o in (7, 18, 12):
    liste.ekle(o)
print(liste.sil(12), liste.sil(99))    # True False
```

Aynı teknik, dairesel çift yönlü listelerde de kullanılır ve kodun uç durum sayısını
belirgin biçimde azaltır.

#### Bellek Ek Yükü ve Önbellek

Bağlı listenin ilan edilen üstünlükleri, pratikte iki maliyetle sınırlanır.

**Ek yer.** Her düğüm, değerin yanında bir veya iki işaretçi taşır. Sekiz baytlık
işaretçilerle, dört baytlık tam sayılardan oluşan tek yönlü bir listede yapı verisi,
gerçek veriden fazladır. Diziyle karşılaştırıldığında bellek kullanımı kat düzeyinde
artabilir.

**Yerellik.** Düğümler öbekte dağınık durur. Bir düğümden diğerine geçmek, bellekte
öngörülemeyen bir adrese atlamaktır; önbellek satırı getirmenin kazancı yoktur ve
önden getirme çalışmaz. Bilgisayarlar Nasıl Çalışır kursunun önbellek dersinde
hesaplanan fark burada tersine işler: dizi taraması satır başına birçok eleman
kullanırken, liste taraması her düğüm için ayrı bir ıska riski taşır.

Sonuç şudur: kâğıt üzerinde $O(1)$ olan bağlı liste eklemesi, gerçek ölçümlerde
$O(n)$ olan dizi eklemesinden yavaş kalabilir — özellikle eleman sayısı küçük veya orta
ölçekteyken. Karmaşıklık sınıfı, sabit çarpanları görmezden gelir; donanım görmezden
gelmez.

#### Ne Zaman Bağlı Liste

Yapının meşru kullanım alanları dardır ama gerçektir:

- **Düğüm referansı elde tutuluyorsa.** En bilinen örnek, bir karma tablosuyla birlikte
  kullanılan çift yönlü listedir: tablo düğümü doğrudan verir, liste sıralamayı sabit
  zamanda günceller. En az kullanılanı çıkaran önbellek tasarımı bu ikilinin üzerine
  kurulur.
- **Yeniden ayırma kabul edilemezse.** Dinamik dizinin büyümesi, tek bir işlemi uzun
  sürdürür; gecikme sınırı olan sistemlerde bu kabul edilmeyebilir.
- **Referans kararlılığı gerekiyorsa.** Bağlı listede bir düğümün adresi, listeye yeni
  elemanlar eklendiğinde değişmez; dinamik dizide yeniden ayırma tüm adresleri
  geçersizleştirir.
- **Listelerin birleştirilmesi sıksa.** İki listeyi uç uca eklemek, bağ yazmaktan
  ibarettir.

Bunların dışında, varsayılan seçim dizidir.

#### Maliyet Tablosu

| Yapı | Erişim | Arama | Başa ekleme | Sona ekleme | Silme (düğüm elde) |
|---|---|---|---|---|---|
| Dizi (sabit boyut) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ |
| Dinamik dizi | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ amortize | $O(n)$ |
| Tek yönlü bağlı liste | $O(n)$ | $O(n)$ | $O(1)$ | $O(n)$** | $O(n)$ |
| Çift yönlü bağlı liste | $O(n)$ | $O(n)$ | $O(1)$ | $O(1)$** | $O(1)$ |

\* Yer kaldığı sürece.  \*\* Son işaretçisi tutuluyorsa $O(1)$.

#### Özet

- Bağlı listede elemanlar bitişik durmaz; sıra, her düğümün bir sonrakinin adresini
  taşımasıyla kurulur.
- Adres aritmetiği geçersizdir; $i$'nci elemana erişim doğrusal zamanlıdır.
- Ekleme ve silme, işaretçi yazmaktan ibaret olduğu için ucuzdur; pahalı olan, konumu
  bulmaktır.
- Çift yönlü listede geri bağ, elde düğüm varken silmeyi sabit zamanlı yapar; karşılığı
  ek bellek ve daha karmaşık güncellemedir.
- İşaretçi ek yükü ve dağınık yerleşim, listenin pratik başarımını kuramsal
  maliyetinin altına çekebilir.
- Yapı, düğüm referansının elde tutulduğu, yeniden ayırmanın kabul edilmediği veya
  referans kararlılığının gerektiği durumlarda seçilir.

#### Sonraki Adım

Sonraki iki ders, buraya kadar tanımlanan yapıların üzerine kurulan iki soyut veri
tipini ele alacak. İlki, yalnızca son eklenen elemana erişime izin veren yığıttır;
fonksiyon çağrılarının nasıl yönetildiğini önceki kurstan hatırlayacaksınız.

### Yığıtlar

Source: https://academia.sh/tr/kurslar/veri-yapilari/yigitlar

Soyut veri tipi kavramı, son giren ilk çıkar modeli, iki gerçekleştirim seçeneği ve tipik kullanım alanları.

Önceki üç ders somut yerleşimleri anlattı: bitişik blok, büyüyen blok, bağlı düğümler.
Bu ders farklı bir soru sorar — verinin nasıl saklandığı değil, **hangi işlemlere izin
verildiği**.

#### Soyut Veri Tipi

**Soyut veri tipi**, bir yapının sunduğu işlemleri ve bu işlemlerin anlamını tanımlar;
verinin bellekte nasıl durduğunu söylemez. Programlama Temelleri kursundaki arayüz–
gerçekleştirim ayrımının veri yapılarındaki karşılığıdır.

Ayrımın değeri iki yönlüdür. Kullanan taraf, yalnızca sözleşmeye dayanarak kod yazar;
gerçekleştiren taraf, sözleşmeyi bozmadan iç yapıyı değiştirebilir. Aynı soyut tip,
farklı maliyet profilleriyle birden çok biçimde gerçeklenebilir.

**Yığıt (stack)**, bu dersin konusu olan soyut veri tipidir ve tek bir kuralla
tanımlanır: **son eklenen eleman, ilk çıkan elemandır.**

#### Yığıt İşlemleri

Dört işlem yeterlidir:

| İşlem | Anlamı | Maliyet |
|---|---|---|
| `it` (push) | Tepeye eleman ekler | $O(1)$ |
| `çek` (pop) | Tepedeki elemanı çıkarır ve döndürür | $O(1)$ |
| `tepe` (peek) | Tepedekini çıkarmadan gösterir | $O(1)$ |
| `boş_mu` | Yığıtın boş olup olmadığını söyler | $O(1)$ |

Listede olmayan işlemler de tanımın parçasıdır: yığıtta ortadaki bir elemana erişilemez,
arama yapılmaz, gezinme yoktur. Kısıtlama bir eksiklik değil, tasarımın kendisidir —
kısıtlı arayüz, yanlış kullanımı olanaksız kılar.

#### İki Gerçekleştirim

Aynı sözleşme iki farklı yapıyla karşılanabilir ve ikisi de tüm işlemleri sabit zamanda
yapar.

**Dinamik dizi ile:** Tepe, dizinin sonudur. Ekleme sona ekleme, çıkarma sondan
silmedir; ikisi de kaydırma gerektirmez. Amortize maliyet sabittir ve bitişik yerleşim
sayesinde önbellek davranışı iyidir.

**Bağlı liste ile:** Tepe, listenin başıdır. Başa ekleme ve baştan silme sabit
zamanlıdır. Yeniden ayırma hiç olmaz; buna karşılık düğüm başına işaretçi ek yükü ve
dağınık yerleşim vardır.

Seçim ölçütü, önceki derslerin sonucunu tekrarlar: öngörülebilir tek işlem süresi
gerekmiyorsa dinamik dizi, gerekiyorsa bağlı liste.

```python
class Yigit:
    """Son giren ilk çıkar; dinamik dizi üzerine kurulu."""

    def __init__(self) -> None:
        self._veri: list = []

    def it(self, deger) -> None:
        self._veri.append(deger)

    def cek(self):
        if self.bos_mu():
            raise IndexError("boş yığıttan çekilemez")
        return self._veri.pop()

    def tepe(self):
        if self.bos_mu():
            raise IndexError("boş yığıtın tepesi yok")
        return self._veri[-1]

    def bos_mu(self) -> bool:
        return len(self._veri) == 0

    def __len__(self) -> int:
        return len(self._veri)


y = Yigit()
for olcum in (12, 18, 7):
    y.it(olcum)

print(y.tepe(), len(y))      # 7 3
print(y.cek(), y.cek())      # 7 18
print(len(y), y.bos_mu())    # 1 False
```

Boş yığıttan çekmenin hata üretmesi, sözleşmenin parçasıdır. Sessizce boş değer
döndürmek, Programlama Temelleri kursundaki boş değer sorununu çağıran tarafa taşırdı.

#### Neden Yığıt

Yığıt, "en son yarım kalan işe geri dön" biçiminde tanımlanabilen her problemin doğal
yapısıdır.

**Çağrı yığıtı.** Bilgisayarlar Nasıl Çalışır kursunda kurulan çerçeve düzeni tam olarak
budur: en son çağrılan fonksiyon en önce döner. Özyineleme derinliği, bu yığıtın
doluluğuydu.

**Geri alma.** Bir düzenleyicide yapılan işlemler yığıta itilir; geri alma, tepedeki
işlemi çeker.

**Eşleşme denetimi.** Açılan her parantez yığıta itilir, kapanan her parantez tepedekiyle
karşılaştırılır.

**Geri izleme.** Denenmiş seçimlerin yığıtta tutulması, çıkmaza girildiğinde son karara
dönmeyi sağlar.

**Derine arama.** Bu kursun son konusunda görüleceği gibi, çizgelerde derine arama bir
yığıtla yürür — özyinelemeli yazımında bu yığıt, çağrı yığıtının kendisidir.

#### Örnek: Parantez Denetimi

Bir metindeki parantezlerin doğru eşleşip eşleşmediği, tek geçişte ve yığıtla
sınanır:

```python
ESLESME = {")": "(", "]": "[", "}": "{"}

def dengeli_mi(metin: str) -> bool:
    """Parantezlerin doğru sırayla açılıp kapandığını sınar."""
    yigit = Yigit()
    for karakter in metin:
        if karakter in "([{":
            yigit.it(karakter)
        elif karakter in ESLESME:
            if yigit.bos_mu() or yigit.cek() != ESLESME[karakter]:
                return False               # eşleşmeyen kapanış
    return yigit.bos_mu()                  # açık kalan varsa dengesiz


print(dengeli_mi("(12 + [18 - 7])"))       # True
print(dengeli_mi("(12 + [18 - 7)]"))       # False   — sıra bozuk
print(dengeli_mi("((12)"))                 # False   — açık kaldı
print(dengeli_mi("12)"))                   # False   — fazladan kapanış
```

Çözümün yığıt gerektirmesinin nedeni, iç içe geçmenin derinliğinin önceden bilinmemesidir:
en son açılan parantez, ilk kapanması gerekendir. Aynı yapı, iç içe geçen her şey için
geçerlidir — kod blokları, işaretleme etiketleri, ifade ayrıştırma.

Bu, önceki kursta anlatılan ayrıştırma aşamasının çekirdeğidir; dilbilgisi kurallarının
iç içe geçmiş yapıları, bir yığıt üzerinde işlenir.

#### Örnek: İfade Değerlendirme

İkinci klasik kullanım, aritmetik ifadelerin değerlendirilmesidir. İşleçlerin
işlenenlerden sonra yazıldığı **son ek gösteriminde** parantez gerekmez ve
değerlendirme tek bir yığıtla yürür: sayı görülünce itilir, işleç görülünce iki değer
çekilip sonuç geri itilir.

```python
def son_ek_degerlendir(ifade: str) -> float:
    """Son ek gösterimindeki ifadeyi yığıtla hesaplar."""
    yigit = Yigit()
    for birim in ifade.split():
        if birim in "+-*/":
            sag = yigit.cek()
            sol = yigit.cek()
            if birim == "+": yigit.it(sol + sag)
            elif birim == "-": yigit.it(sol - sag)
            elif birim == "*": yigit.it(sol * sag)
            else: yigit.it(sol / sag)
        else:
            yigit.it(float(birim))
    return yigit.cek()


print(son_ek_degerlendir("12 18 +"))          # 30.0
print(son_ek_degerlendir("12 18 + 2 /"))      # 15.0   — (12 + 18) / 2
print(son_ek_degerlendir("12 18 7 - +"))      # 23.0   — 12 + (18 - 7)
```

İkinci çağrı, bu kurs boyunca kullanılan ortalama hesabının son ek gösterimidir.
Çekme sırasının önemine dikkat edin: ilk çekilen değer sağ işlenendir, çünkü en son
itilen odur. Çıkarma ve bölmede bu sıra karıştırılırsa sonuç sessizce yanlış çıkar.

Ara gösterimdeki (alışıldık) bir ifadeyi son ek gösterimine çevirmek de bir yığıt
gerektirir; işleç önceliği, yığıtta bekleyen işleçlerin ne zaman çıkarılacağını
belirler. Derleyicilerin ifade ayrıştırma aşaması bu düzenin genelleştirilmiş hâlidir.

#### Sınırlar

Yığıtın kısıtlı arayüzü, bazı soruların yanıtlanamamasını beraberinde getirir: kaç
elemanın hangi değerde olduğu, ortadaki bir elemanın ne olduğu, elemanların sıralı olup
olmadığı. Bu bilgiler gerekiyorsa yığıt yanlış seçimdir.

Sabit kapasiteli bir gerçekleştirimde ikinci bir sınır vardır: kapasite dolduğunda
**taşma** oluşur. Bilgisayarlar Nasıl Çalışır kursundaki yığıt taşması, bu durumun
çağrı yığıtındaki karşılığıydı.

#### Maliyet Tablosu

| Yapı | Erişim | Arama | Ekleme | Silme |
|---|---|---|---|---|
| Dinamik dizi | $O(1)$ | $O(n)$ | sona $O(1)$ amortize | ortadan $O(n)$ |
| Bağlı liste | $O(n)$ | $O(n)$ | başa $O(1)$ | baştan $O(1)$ |
| **Yığıt** | yalnız tepe $O(1)$ | — | $O(1)$ | $O(1)$ |

#### Özet

- Soyut veri tipi, sunulan işlemleri ve anlamlarını tanımlar; yerleşimi belirtmez.
- Yığıt, son giren ilk çıkar kuralıyla tanımlanır ve dört işlemi sabit zamanlıdır.
- Kısıtlı arayüz bir eksiklik değil, yanlış kullanımı önleyen bir tasarım kararıdır.
- Dinamik dizi ve bağlı liste, yığıtı aynı maliyetlerle gerçekler; seçim, tek işlem
  süresi ve önbellek davranışına göre yapılır.
- Çağrı yönetimi, geri alma, eşleşme denetimi ve geri izleme yığıtla çözülen problem
  ailesidir.
- Boş yığıttan çekme hata üretir; sabit kapasiteli gerçekleştirimde taşma ikinci sınırdır.

#### Sonraki Adım

Bazı problemlerde beklenen davranış tersidir: ilk gelen ilk işlenmelidir — bir iş
kuyruğunda, bir yazıcı sırasında, bir ağ tamponunda. Sonraki ders bu modeli ve sabit
bellekle sürekli akış işlemeyi sağlayan halka arabelleği ele alacak.

### Kuyruklar ve Çift Uçlu Kuyruklar

Source: https://academia.sh/tr/kurslar/veri-yapilari/kuyruklar

İlk giren ilk çıkar modeli, halka arabellekle sabit bellekte kuyruk, çift uçlu kuyruk ve kullanım alanları.

Yığıt, en son eklenene öncelik verir. Bazı problemlerde beklenen tam tersidir: bir iş
kuyruğunda önce gelen önce işlenmeli, bir ağ tamponunda paketler geliş sırasını
korumalıdır.

**Kuyruk (queue)**, bu kuralı tanımlayan soyut veri tipidir: **ilk giren, ilk çıkar.**

#### Kuyruk İşlemleri

| İşlem | Anlamı | Hedef maliyet |
|---|---|---|
| `ekle` (enqueue) | Sona eleman ekler | $O(1)$ |
| `al` (dequeue) | Baştaki elemanı çıkarır ve döndürür | $O(1)$ |
| `ön` (front) | Baştakini çıkarmadan gösterir | $O(1)$ |
| `boş_mu` | Kuyruğun boş olup olmadığını söyler | $O(1)$ |

Yığıttan tek farkı, çıkarmanın hangi uçtan yapıldığıdır. Bu küçük fark, gerçekleştirimi
belirgin biçimde zorlaştırır: yığıtta her iki işlem de aynı uçta olduğu için tek bir
dizin yeterliyken, kuyrukta iki ucun ayrı ayrı izlenmesi gerekir.

#### Saf Dizi Gerçekleştiriminin Sorunu

Kuyruk bir dinamik diziyle kurulursa, sona ekleme ucuzdur ancak baştan almak tüm
elemanların bir sıra sola kaydırılmasını gerektirir — $O(n)$. Bin elemanlık bir kuyrukta
her `al` çağrısı geriye kalan dokuz yüz doksan dokuz elemanı kaydırır.

Kaydırmadan kaçınmanın ilk fikri, baş dizinini ilerletmektir: eleman silinmez, yalnızca
"artık kuyrukta değil" sayılır. Bu, `al` işlemini sabit zamanlı yapar ama yeni bir sorun
üretir — dizinin başındaki alan boşalır ve hiç geri kazanılmaz. Sürekli çalışan bir
kuyruk, kullanılmayan alanı sonsuza kadar büyütür.

#### Halka Arabellek

Çözüm, dizinin sonuna varıldığında başa dönmektir. Sabit kapasiteli bir bloğun uçları
birbirine bağlanmış gibi düşünülür; bu yapıya **halka arabellek (circular buffer)** denir.

İki dizin tutulur: `bas`, sıradaki alınacak elemanı; `son`, sıradaki yazılacak yeri
gösterir. İlerleme, kapasiteye göre kalan alınarak yapılır:

$$
\text{yeni konum} = (\text{konum} + 1) \bmod \text{kapasite}
$$

Kalan işleci, İşleçler dersinde tanıtılmıştı; buradaki kullanımı onun kanonik örneğidir.

```python
class HalkaArabellek:
    """Sabit kapasiteli kuyruk; uçlara ulaşınca başa döner."""

    def __init__(self, kapasite: int) -> None:
        self._veri: list = [None] * kapasite
        self._kapasite = kapasite
        self._bas = 0
        self._sayi = 0

    def __len__(self) -> int:
        return self._sayi

    def dolu_mu(self) -> bool:
        return self._sayi == self._kapasite

    def bos_mu(self) -> bool:
        return self._sayi == 0

    def ekle(self, deger) -> None:
        if self.dolu_mu():
            raise OverflowError("arabellek dolu")
        son = (self._bas + self._sayi) % self._kapasite    # yazılacak konum
        self._veri[son] = deger
        self._sayi += 1

    def al(self):
        if self.bos_mu():
            raise IndexError("boş arabellekten alınamaz")
        deger = self._veri[self._bas]
        self._veri[self._bas] = None                       # referansı bırak
        self._bas = (self._bas + 1) % self._kapasite       # başa dön
        self._sayi -= 1
        return deger


kuyruk = HalkaArabellek(3)
kuyruk.ekle(12); kuyruk.ekle(18); kuyruk.ekle(7)
print(len(kuyruk), kuyruk.dolu_mu())        # 3 True

print(kuyruk.al(), kuyruk.al())             # 12 18
kuyruk.ekle(25); kuyruk.ekle(14)            # boşalan yerlere başa dönerek yazılır
print(len(kuyruk))                          # 3
print(kuyruk.al(), kuyruk.al(), kuyruk.al())   # 7 25 14
```

Kapasitesi üç olan arabellek, beş eleman taşımıştır: yeni elemanlar, boşalan
konumlara başa dönülerek yazılmıştır. Hiçbir eleman kaydırılmamış, hiç yeniden ayırma
yapılmamıştır.

Dolu arabellekte ekleme kararı bir tasarım seçimidir. Üç seçenek yaygındır: hata
üretmek (yukarıdaki gibi), çağıranı bekletmek, ya da en eski elemanın üzerine yazmak.
Üçüncüsü, yalnızca son $k$ ölçümün tutulduğu kayıt tamponlarında tercih edilir.

#### Bağlı Liste ile Kuyruk

Kapasite sınırı istenmiyorsa, baş ve son işaretçilerinin ikisini birden tutan bir bağlı
liste kullanılır: sona ekleme son işaretçisiyle, baştan alma baş işaretçisiyle sabit
zamanda yapılır.

Bedeli önceki derste tanımlanmıştı: düğüm başına işaretçi ek yükü ve dağınık yerleşim.
Pratikte yaygın çözüm ikisinin birleşimidir — bağlı listenin düğümleri tek eleman değil,
küçük bitişik bloklar taşır. Böylece hem sınırsız büyüme hem makul önbellek davranışı
elde edilir.

#### Çift Uçlu Kuyruk

**Çift uçlu kuyruk (deque)**, her iki uçtan ekleme ve çıkarmaya izin verir. Yığıt ve
kuyruğun ikisini birden kapsar: yalnızca bir uç kullanılırsa yığıt, iki uç ayrı ayrı
kullanılırsa kuyruk gibi davranır.

Halka arabellek, çift uçlu kuyruğu da doğal olarak destekler; baş dizini geriye doğru da
döndürülebilir.

Tipik kullanımı, kayan pencere problemleridir: bir uçtan yeni ölçüm girer, diğer uçtan
pencere dışında kalan çıkar. Programlama Temelleri kursunda tanıtılan kayan pencere
kalıbının veri yapısı karşılığı budur.

#### Kullanım Alanları

- **İş kuyrukları.** Üretici–tüketici düzeninde işler sıraya alınır; sıra korunur.
- **Tamponlama.** Farklı hızda çalışan iki bileşen arasında halka arabellek kullanılır;
  Bilgisayarlar Nasıl Çalışır kursundaki aygıt iletişimi bu düzendedir.
- **Enine arama.** Bu kursun son konusunda görüleceği gibi, çizgelerde katman katman
  gezinme bir kuyrukla yürür.
- **Zamanlama.** İşletim sisteminin hazır süreç listesi, adil paylaşımda kuyruk
  düzenindedir.

Elemanların geliş sırasının değil önem sırasının belirleyici olduğu durumlarda, kuyruk
yetmez; **öncelik kuyruğu** gerekir. O yapı, ağaçlar konusundaki yığın dersinde ele
alınacaktır.

#### Kuyruk Uzunluğu Bir Ölçüttür

Bir kuyruk yalnızca veri yapısı değil, iki bileşen arasındaki hız farkının göstergesidir.
Kuyruk uzunluğu sürekli artıyorsa, üretim hızı tüketim hızını aşıyor demektir.

Sınırsız kapasiteli bir kuyrukta bu durum uzun süre gizli kalır: bellek dolana kadar
hiçbir belirti görünmez, sonra sistem birden çöker. Sınırlı kapasiteli kuyrukta ise
sınıra ulaşıldığında karar vermek zorunludur — üreticiyi bekletmek, yeni işi reddetmek
veya en eskisini düşürmek.

Üreticinin bekletilmesi, yavaşlığın kaynağa doğru yayılmasıdır ve **geri basınç** olarak
adlandırılır. Bilgisayarlar Nasıl Çalışır kursunda aygıtlar arası iletişimde geçen bu
kavram, dağıtık sistemlerde de aynı biçimde işler.

Bu nedenle üretim ortamında kuyruk uzunluğu izlenen bir ölçüttür: uzunluğun eğilimi,
darboğazın nerede olduğunu doğrudan gösterir.

#### Maliyet Tablosu

| Yapı | Baştan alma | Sona ekleme | Başa ekleme | Kapasite |
|---|---|---|---|---|
| Dinamik dizi (saf kuyruk) | $O(n)$ | $O(1)$ amortize | $O(n)$ | Sınırsız |
| Halka arabellek | $O(1)$ | $O(1)$ | $O(1)$ | Sabit |
| Bağlı liste (baş + son) | $O(1)$ | $O(1)$ | $O(1)$ | Sınırsız |
| Çift uçlu kuyruk | $O(1)$ | $O(1)$ | $O(1)$ | Değişir |

#### Özet

- Kuyruk, ilk giren ilk çıkar kuralıyla tanımlanır; yığıttan tek farkı çıkarmanın
  yapıldığı uçtur.
- Dizi üzerinde saf gerçekleştirimde baştan alma kaydırma gerektirir; baş dizinini
  ilerletmek ise kullanılmayan alan biriktirir.
- Halka arabellek, kalan işleciyle uçları birleştirir ve sabit kapasiteyle her iki
  işlemi sabit zamanlı yapar.
- Dolu arabellekte davranış — hata, bekleme veya üzerine yazma — bir tasarım kararıdır.
- Baş ve son işaretçili bağlı liste, sınırsız kapasiteli kuyruk verir; bedeli işaretçi
  ek yükü ve yerelliktir.
- Çift uçlu kuyruk her iki uca izin verir ve kayan pencere problemlerinin doğal yapısıdır.

#### Sonraki Adım

Buraya kadar sıralı erişim ve uçlardan işlem ele alındı. Sıralı bir veri kümesinde
arama ise hâlâ doğrusal: bağlı listede ikili arama yapılamıyor, çünkü ortadaki elemana
sıçranamıyor. Sonraki ders, bağlantılı yapıya katmanlar ekleyerek bu sıçramayı mümkün
kılan olasılıksal bir çözümü ele alacak.

### Atlama Listeleri

Source: https://academia.sh/tr/kurslar/veri-yapilari/atlama-listeleri

Sıralı bağlı listeye katman ekleyerek arama maliyetini düşürmek, olasılıksal yükseklik ve beklenen maliyet.

Sıralı bir dizide ikili arama $O(\log n)$'dir: ortadaki elemana doğrudan sıçranabilir.
Sıralı bir bağlı listede aynı arama $O(n)$ kalır, çünkü sıçrama yoktur — ortadaki
elemana ulaşmak için tüm bağların izlenmesi gerekir.

**Atlama listesi (skip list)**, bağlantılı yapıyı korurken sıçramayı geri getirir.
Yöntemi, listenin üzerine seyrek katmanlar eklemektir.

#### Katman Fikri

Bir demiryolu hattı düşünün: her istasyonda duran hat, birkaç istasyonda bir duran hızlı
hat ve yalnızca büyük duraklarda duran ekspres hat. Uzak bir istasyona giderken önce
ekspresle mümkün olduğunca yaklaşılır, sonra alt hatlara inilir.

Atlama listesi aynı düzendir. En alt katman tüm elemanları içeren sıralı bağlı listedir.
Üstündeki her katman, bir alttakinin elemanlarının bir kısmını taşır. Arama en üst
katmandan başlar:

1. Bulunduğun katmanda, bir sonraki eleman hedeften küçük olduğu sürece ilerle.
2. İlerleyemiyorsan bir katman aşağı in.
3. En alt katmanda dur; aranan eleman, o noktadaki bir sonraki elemandır ya da yoktur.

Her katman elemanların yaklaşık yarısını taşıyorsa, katman sayısı $\log_2 n$ olur ve her
katmanda ortalama sabit sayıda adım atılır. Beklenen arama maliyeti bu nedenle
$O(\log n)$'dir.

#### Yükseklik Nasıl Belirlenir

Katmanların düzenli tutulması gerekseydi — her ikinci eleman bir üst katmanda, her
dördüncü eleman iki üst katmanda — ekleme ve silme, tüm yapıyı yeniden düzenlemeyi
gerektirirdi. Bu, dengeli ağaçların çözdüğü problemin aynısıdır ve benzer karmaşıklıkta
kod demektir.

Atlama listesinin çözümü farklıdır: **her yeni eleman kendi yüksekliğini rastgele
seçer.** Yaygın kural, arka arkaya yazı gelen para atışı sayısıdır — eleman en az bir
katmanda bulunur; olasılığın yarısıyla ikinci katmana, dörtte biriyle üçüncüye çıkar.

Sonuç, katman doluluklarının **ortalamada** istenen orana yakın çıkmasıdır. Hiçbir
yeniden dengeleme yapılmaz; yapı kendiliğinden dengeli kalır.

Bedeli, güvencenin türüdür. Kötü bir rastgelelik dizisinde tüm elemanlar tek katmanda
kalabilir ve arama $O(n)$'e düşebilir. Bu olasılık eleman sayısı büyüdükçe hızla azalır
ama sıfır değildir. Atlama listesi **beklenen** maliyet güvencesi verir, en kötü durum
güvencesi vermez.

Ayrım önemlidir: en kötü durum güvencesi isteyen sistemler dengeli ağaçları seçer.

#### Aramanın Gösterimi

Aşağıdaki yapı, yükseklikleri örnek olsun diye elle verilmiş bir atlama listesidir.
Rastgelelik yerine sabit yükseklikler kullanmak, aramanın nasıl yürüdüğünü
tekrarlanabilir biçimde göstermeye yarar.

```python
class AtlamaDugumu:
    def __init__(self, deger: int, yukseklik: int) -> None:
        self.deger = deger
        self.ileri: list = [None] * yukseklik      # her katman için bir bağ


def liste_kur(elemanlar: list[tuple[int, int]], ust: int) -> AtlamaDugumu:
    """(değer, yükseklik) çiftlerinden sıralı atlama listesi kurar."""
    bas = AtlamaDugumu(-1, ust)                    # sınır düğümü
    son = [bas] * ust                              # her katmanın son düğümü
    for deger, yukseklik in elemanlar:
        dugum = AtlamaDugumu(deger, yukseklik)
        for k in range(yukseklik):
            son[k].ileri[k] = dugum
            son[k] = dugum
    return bas


def ara(bas: AtlamaDugumu, hedef: int, ust: int) -> tuple[bool, int]:
    """Hedefi arar; (bulundu, atılan adım sayısı) döndürür."""
    dugum = bas
    adim = 0
    for k in range(ust - 1, -1, -1):               # en üst katmandan aşağı
        while dugum.ileri[k] is not None and dugum.ileri[k].deger < hedef:
            dugum = dugum.ileri[k]                 # aynı katmanda ilerle
            adim += 1
        adim += 1                                  # bir katman aşağı in
    aday = dugum.ileri[0]
    return (aday is not None and aday.deger == hedef), adim


UST = 3
elemanlar = [(7, 3), (12, 1), (14, 2), (18, 1), (25, 3), (30, 1), (42, 2)]
bas = liste_kur(elemanlar, UST)

print(ara(bas, 30, UST))     # (True, 5)
print(ara(bas, 13, UST))     # (False, 5)
print(ara(bas, 7, UST))      # (True, 3)
```

`30` değeri aranırken üst katman yalnız `7` ile `25`'i taşıdığı için `25` düğümüne iki
adımda ulaşılır; alt katmanlara
inildiğinde geriye yalnızca birkaç eleman kalmıştır. Aynı arama tek katmanlı sıralı bir
listede, altı bağ izlemeyi gerektirirdi.

İkinci çağrı, listede bulunmayan bir değeri arar ve aynı yolu izler; arama başarısız
olsa da maliyet aynı mertebededir.

#### Ekleme ve Silme

Ekleme, aramanın kendisidir: her katmanda durulan son düğüm kaydedilir, yeni düğümün
yüksekliği belirlenir ve o yükseklik kadar katmanda bağlar yeniden yazılır. Beklenen
maliyet yine $O(\log n)$'dir.

Silme aynı biçimde yürür; düğümün bulunduğu her katmanda bağ atlanır.

Dikkat çekici olan, hiçbir işlemin **yeniden dengeleme** içermemesidir. Dengeli
ağaçlarda ekleme sonrası uygulanan dönme işlemleri burada yoktur; denge, olasılıktan
gelir. Bu, atlama listesinin kodunun dengeli ağaçlardan belirgin biçimde kısa
olmasının nedenidir.

İkinci pratik üstünlük eşzamanlılıktadır: değişiklikler yerel olduğu için, birden çok
iş parçacığının aynı yapı üzerinde çalışması dengeli ağaçlara göre daha az kilitleme
gerektirir. Bazı veritabanı ve bellek içi depo gerçekleştirimlerinde sıralı dizin yapısı
olarak seçilmesinin nedeni budur.

#### Katman Sayısının Sınırlanması

Yükseklik rastgele seçildiğinde, kuramsal olarak çok yüksek bir düğüm üretilebilir.
Gerçekleştirimler bu nedenle bir üst sınır koyar: katman sayısı, beklenen eleman
sayısının logaritması dolayında sabitlenir.

Sınırın etkisi ihmal edilebilir. Bir elemanın $k$ katmana çıkma olasılığı $2^{-k}$
mertebesinde olduğundan, milyon elemanlık bir yapıda yirmi katmanın üzerine çıkma
olasılığı yok denecek kadar küçüktür. Sınır, yalnızca bellek düzenini öngörülebilir
tutar: her düğümün taşıyabileceği en fazla bağ sayısı bilinir.

İkinci pratik ayrıntı, üst sınırın veri büyüklüğüne göre seçilmesidir. Çok küçük
seçilirse katmanlar doygunlaşır ve arama doğrusala yaklaşır; çok büyük seçilmesinin
maliyeti ise yalnızca birkaç boş bağdır. Bu asimetri nedeniyle sınır, cömert seçilir.

#### Olasılıksal Veri Yapıları

Atlama listesi, daha geniş bir ailenin ilk örneğidir: **olasılıksal veri yapıları**.
Ortak özellikleri, kesin güvence yerine olasılıksal güvence vermeleri ve karşılığında
daha basit veya daha ucuz olmalarıdır.

Aile, üyeliği yanlış pozitif olasılığıyla sınayan süzgeçleri ve tekil eleman sayısını
küçük bellekle kestiren sayıcıları da içerir. Bu yapılar, kesin yanıtın gerekmediği veya
maliyetinin kabul edilemez olduğu ölçeklerde kullanılır ve veri yoğun sistemlerin
tasarımında ayrı bir konudur.

#### Maliyet Tablosu

| Yapı | Arama | Ekleme | Silme | Güvence |
|---|---|---|---|---|
| Sıralı dizi | $O(\log n)$ | $O(n)$ | $O(n)$ | Kesin |
| Sıralı bağlı liste | $O(n)$ | $O(1)$* | $O(1)$* | Kesin |
| Atlama listesi | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | Beklenen |

\* Konum elde tutuluyorsa.

#### Özet

- Sıralı bağlı listede ikili arama yapılamaz; atlama listesi, üzerine seyrek katmanlar
  ekleyerek sıçramayı geri getirir.
- Arama en üst katmanda ilerler, ilerleyemeyince bir alt katmana iner; katman sayısı
  logaritmiktir.
- Yükseklik her eleman için rastgele seçilir; böylece yeniden dengeleme gerekmez.
- Verilen güvence beklenen maliyettir, en kötü durum değildir; kesin güvence isteyen
  sistemler dengeli ağaçları seçer.
- Kodun kısalığı ve eşzamanlılıkta daha az kilitleme gerektirmesi, yapının pratik
  üstünlükleridir.
- Atlama listesi, olasılıksal veri yapıları ailesinin bir üyesidir.

#### Sonraki Adım

Bu konu boyunca arama, en iyi durumda logaritmik kaldı: eleman sayısı büyüdükçe maliyet
büyümeye devam ediyor. Oysa bir değerin nerede saklandığı, değerin kendisinden
hesaplanabilirse arama tek adıma inebilir. Sonraki konu, bu fikri kuran karma tablolarını
ve fikrin sınırlarını ele alacak.

## Sözlükler ve Kümeler

Karma tabloları, çakışma çözümleme, küme yapıları ve ayrık kümeler.

### Karma Tabloları

Source: https://academia.sh/tr/kurslar/veri-yapilari/karma-tablolari

Anahtardan konum hesaplama, karma fonksiyonunun nitelikleri, yük çarpanı ve ortalama sabit maliyetin koşulları.

Önceki konu, aramayı en iyi durumda logaritmik maliyete indirdi. Daha aşağısı mümkün
müdür? Sıralama ve karşılaştırma temelli her yapı için değildir; karşılaştırmayla arama
yapan yapılar bu sınıra takılır.

Farklı bir fikir gerekir: **elemanın nerede saklandığını, elemanın kendisinden
hesaplamak.** Aranan değer verildiğinde konumu hesaplanabiliyorsa, arama tek adıma iner.

#### Doğrudan Adresleme

Fikrin en yalın hâli şudur: anahtar bir tam sayıysa ve aralığı küçükse, anahtarın
kendisi dizin olarak kullanılabilir.

```python
# Anahtarlar 0-9 aralığında olsun; anahtar doğrudan dizindir.
tablo = [None] * 10
tablo[3] = "üç"
tablo[7] = "yedi"
print(tablo[3], tablo[7])        # üç yedi
```

Erişim sabit zamanlıdır ve hiçbir arama yapılmaz. Sorun, anahtar uzayının
büyüklüğüdür: anahtarlar dokuz haneli kimlik numaralarıysa, doğrudan adresleme bir
milyar gözlü bir dizi ister. Anahtarlar dizgi ise dizin olarak hiç kullanılamaz.

#### Karma Fonksiyonu

**Karma fonksiyonu (hash function)**, herhangi bir anahtarı sabit bir aralıktaki tam
sayıya eşler. Bu sayı, tablodaki konumu (kovayı) belirler:

$$
\text{konum} = h(\text{anahtar}) \bmod m
$$

Burada $m$ tablo boyutudur. Anahtar uzayı ne kadar büyük olursa olsun, konum $0$ ile
$m-1$ arasına iner.

Bu, doğrudan adreslemenin bellek sorununu çözer — ancak yeni bir sorun getirir: iki
farklı anahtar aynı konuma düşebilir. Bu duruma **çakışma (collision)** denir ve
kaçınılmazdır. Anahtar uzayı tablo boyutundan büyük olduğu sürece, en az iki anahtarın
aynı konuma eşleneceği kesindir. Bu, güvercin yuvası ilkesinin doğrudan sonucudur:
$n$ nesne $m < n$ kutuya dağıtıldığında en az bir kutuya birden çok nesne düşer.

Çakışmalarla nasıl başa çıkılacağı sonraki dersin konusudur. Bu ders, çakışmaların
**nadir** olmasını sağlayan koşullarla ilgilenir.

#### İyi Bir Karma Fonksiyonu

Üç nitelik aranır.

**Belirlilik.** Aynı anahtar her zaman aynı değeri vermelidir. Program çalıştığı sürece
değişmeyen bir eşleme olmalıdır; aksi hâlde saklanan veri bulunamaz.

**Düzgün dağılım.** Anahtarlar kovalara mümkün olduğunca eşit dağılmalıdır. Bir kovaya
yığılma, o kovadaki aramayı doğrusala çevirir. İyi bir fonksiyonda, anahtarın tek bir
bitinin değişmesi çıktının yaklaşık yarısını değiştirir; bu özellik **çığ etkisi** olarak
adlandırılır.

**Hız.** Karma hesabı, aramanın kendisinden pahalı olmamalıdır. Kriptografik karma
fonksiyonları çığ etkisini güçlü biçimde sağlar ancak veri yapısı için gereğinden
yavaştır; tablo için hafif fonksiyonlar kullanılır.

Dizgiler için yaygın bir yöntem, karakterleri bir taban üzerinden polinom gibi
değerlendirmektir:

```python
def dizgi_karma(metin: str, taban: int = 31, mod: int = 1_000_003) -> int:
    """Karakterleri polinom biçiminde değerlendirir."""
    deger = 0
    for karakter in metin:
        deger = (deger * taban + ord(karakter)) % mod
    return deger


print(dizgi_karma("olcum"))          # 826819
print(dizgi_karma("olcun"))          # 826820  — tek harf farkı
print(dizgi_karma("mucol"))          # 247712  — aynı harfler, farklı sıra
```

Tabanın çarpan olarak kullanılması, karakter sırasının sonuca yansımasını sağlar:
aynı harflerden oluşan farklı dizgiler farklı değer üretir. Sıra dikkate alınmasaydı,
harflerin toplamı kullanılan bir fonksiyonda tüm harf permütasyonları çakışırdı.

#### Yük Çarpanı

Tablonun doluluk oranı, başarımın belirleyicisidir:

$$
\alpha = \frac{n}{m}
$$

$n$ eleman sayısı, $m$ kova sayısıdır. Yük çarpanı büyüdükçe çakışma olasılığı artar;
küçüldükçe bellek boşa harcanır.

Gerçekleştirimler bir eşik belirler (yaygın olarak $0{,}7$ dolayında) ve eşik aşıldığında
tabloyu büyütür. Büyütme, dinamik dizideki gibi kapasiteyi katlamak ve **tüm elemanları
yeniden yerleştirmektir** — çünkü konum, tablo boyutuna bağlıdır. Bu işleme **yeniden
karma (rehash)** denir ve maliyeti $O(n)$'dir; amortize edildiğinde ekleme başına sabit
kalır.

#### Karma Değeri ile Konum Ayrı Şeylerdir

İki kavramın karıştırılması yaygındır. **Karma değeri**, anahtardan hesaplanan sayıdır ve
tablo boyutundan bağımsızdır. **Konum**, o değerin tablo boyutuna indirgenmiş hâlidir.

Ayrımın pratik sonucu, karma değerinin saklanabilmesidir. Gerçekleştirimler her göze,
anahtarın yanında karma değerini de yazar. İki kazanç sağlar: yeniden karma sırasında
değerler yeniden hesaplanmaz, yalnızca yeni tablo boyutuna göre indirgenir; ve arama
sırasında anahtarlar karşılaştırılmadan önce karma değerleri karşılaştırılır — farklıysa
pahalı eşitlik sınamasına hiç girilmez.

İkinci kazanç, anahtarların uzun dizgiler olduğu durumlarda belirgindir: iki tam sayıyı
karşılaştırmak, iki dizgiyi karakter karakter karşılaştırmaktan çok daha ucuzdur.

#### Ortalama ve En Kötü Durum

Karma tablosunun maliyet vaadi koşulludur:

| Durum | Arama, ekleme, silme |
|---|---|
| Ortalama (düzgün dağılım, sınırlı yük çarpanı) | $O(1)$ |
| En kötü durum (tüm anahtarlar aynı kovada) | $O(n)$ |

En kötü durum yalnızca kuramsal değildir. Karma fonksiyonu biliniyorsa, aynı kovaya
düşen anahtarlar kasıtlı olarak üretilebilir; bu, sunucuyu doğrusal maliyete zorlayan bir
saldırı biçimidir. Savunma, karma fonksiyonuna çalışma anında belirlenen bir tohum
eklemektir — böylece kovaların dağılımı dışarıdan öngörülemez. Bu konu, uygulama
güvenliği müfredatında ayrıca ele alınır.

#### Anahtarın Değişmezliği

Bir anahtar tabloya konduktan sonra değiştirilirse, karma değeri de değişir; eleman artık
bulunduğu kovada aranmaz ve erişilemez hâle gelir.

Bu nedenle anahtar olarak **değiştirilemez** değerler kullanılır. Programlama Temelleri
kursunda tanıtılan değiştirilemez–değiştirilebilir ayrımının pratik sonuçlarından biri
budur: diller çoğu zaman değiştirilebilir nesnelerin anahtar olmasını doğrudan yasaklar.

İkinci kural, eşitlik ile karma tutarlılığıdır: eşit sayılan iki anahtar aynı karma
değerini üretmelidir. Eşitlik davranışı özelleştirilirken karma hesabının güncellenmemesi,
sessizce bozulan tablolara yol açar.

#### Maliyet Tablosu

| Yapı | Arama | Ekleme | Silme | Sıra korunur mu |
|---|---|---|---|---|
| Sıralı dizi | $O(\log n)$ | $O(n)$ | $O(n)$ | Evet |
| Atlama listesi | $O(\log n)$ beklenen | $O(\log n)$ | $O(\log n)$ | Evet |
| Karma tablosu | $O(1)$ ortalama | $O(1)$ ortalama | $O(1)$ ortalama | Hayır |

Bazı gerçekleştirimler, kova düzeninden bağımsız olarak **ekleme sırasını** ayrıca
korur; bu, sıralama değil ekleme sırasıdır ve anahtarların büyüklüğüyle ilgisi yoktur.
Aralık sorgusu yine yapılamaz.

Son sütun, karma tablosunun ödediği bedeldir: elemanlar kova sırasına göre dağıldığı
için anahtar sırası korunmaz. Sıralı gezinme veya aralık sorgusu gerekiyorsa, ağaç
tabanlı yapılar seçilir.

Son bir uyarı: karma değeri bir kimlik değildir. İki farklı anahtarın aynı karma değerini
üretmesi olağandır; bu nedenle karma eşleşmesi bulunduğunda anahtarların kendisi de
karşılaştırılır. Bu adımın atlanması, sessizce yanlış değer döndüren bir tabloya yol açar.

#### Özet

- Karma tablosu, konumu anahtardan hesaplayarak aramayı ortalama sabit zamana indirir.
- Doğrudan adresleme yalnızca küçük ve tam sayı anahtar uzaylarında uygulanabilir; karma
  fonksiyonu bu kısıtı kaldırır.
- İyi bir karma fonksiyonu belirli, düzgün dağıtan ve hızlıdır; çığ etkisi düzgün
  dağılımın göstergesidir.
- Çakışma kaçınılmazdır; yük çarpanı doluluk oranıdır ve eşik aşıldığında tablo
  büyütülerek tüm elemanlar yeniden yerleştirilir.
- En kötü durum doğrusaldır ve kasıtlı olarak tetiklenebilir; tohumlu karma bu riski
  azaltır.
- Anahtarlar değiştirilemez olmalı, eşitlik ile karma tutarlı kalmalıdır.

#### Sonraki Adım

Çakışmanın kaçınılmaz olduğu kuruldu ama ne yapılacağı söylenmedi. Aynı kovaya düşen iki
eleman nereye konur ve bu karar arama maliyetini nasıl etkiler? Sonraki ders iki ana
çözüm ailesini — zincirleme ve açık adreslemeyi — karşılaştıracak.

### Çakışma Çözümleme

Source: https://academia.sh/tr/kurslar/veri-yapilari/cakisma-cozumleme

Zincirleme ve açık adresleme, yoklama stratejileri, kümelenme, silme sorunu ve iki ailenin karşılaştırması.

Önceki ders çakışmanın kaçınılmaz olduğunu gösterdi: anahtar uzayı tablodan büyükse, en
az iki anahtar aynı kovaya düşer. Bu ders, düştüklerinde ne yapılacağını ele alır.

İki çözüm ailesi vardır ve ikisi de yaygın kullanılır. Ayrım tek bir soruda toplanır:
çakışan eleman **kovanın içinde** mi yoksa **tablonun başka bir konumunda** mı saklanır?

#### Zincirleme

**Zincirlemede (chaining)** her kova, o kovaya düşen elemanların listesini tutar. Tablo
bir dizi listedir; ekleme, ilgili listeye eklemektir.

```python
class ZincirliTablo:
    def __init__(self, kova_sayisi: int = 8) -> None:
        self._kovalar: list[list] = [[] for _ in range(kova_sayisi)]
        self.karsilastirma = 0                 # ölçüm için

    def _konum(self, anahtar) -> int:
        return hash(anahtar) % len(self._kovalar)

    def koy(self, anahtar, deger) -> None:
        kova = self._kovalar[self._konum(anahtar)]
        for i, (mevcut, _) in enumerate(kova):
            if mevcut == anahtar:
                kova[i] = (anahtar, deger)     # var olan anahtar güncellenir
                return
        kova.append((anahtar, deger))

    def al(self, anahtar):
        kova = self._kovalar[self._konum(anahtar)]
        for mevcut, deger in kova:
            self.karsilastirma += 1
            if mevcut == anahtar:
                return deger
        raise KeyError(anahtar)

    def sil(self, anahtar) -> None:
        kova = self._kovalar[self._konum(anahtar)]
        for i, (mevcut, _) in enumerate(kova):
            if mevcut == anahtar:
                kova.pop(i)                     # listeden çıkarmak yeterli
                return
        raise KeyError(anahtar)


tablo = ZincirliTablo()
for ad, olcum in [("kuzey", 12), ("guney", 18), ("dogu", 7), ("bati", 25)]:
    tablo.koy(ad, olcum)

print(tablo.al("dogu"))        # 7
tablo.sil("dogu")
print(tablo.al("bati"))        # 25
```

Silmenin sade olduğuna dikkat edin: eleman listeden çıkarılır, başka hiçbir şey
etkilenmez.

Zincirlemenin maliyeti, kova başına düşen ortalama eleman sayısıdır — yani yük
çarpanı. Arama, kovayı bulmak (sabit) artı kovadaki listeyi taramaktır ($O(\alpha)$).
Yük çarpanı sabit tutulduğu sürece ortalama maliyet sabittir.

Yük çarpanı zincirlemede $1$'i aşabilir: kovalar liste tuttuğu için tablo "dolmaz". Bu
esneklik, yeniden boyutlandırmayı geciktirmeye izin verir.

#### Açık Adresleme

**Açık adreslemede (open addressing)** tüm elemanlar tablonun kendi gözlerinde durur.
Çakışma olduğunda, belirli bir kurala göre başka bir göz denenir; bu denemelere
**yoklama (probing)** denir.

En yalın kural **doğrusal yoklamadır**: bir sonraki göze bak, dolu ise bir sonrakine,
tablonun sonuna gelince başa dön.

```python
BOS = object()        # hiç kullanılmamış göz
SILINDI = object()    # silinmiş göz (mezar taşı)

class AcikTablo:
    def __init__(self, kapasite: int = 8) -> None:
        self._gozler: list = [BOS] * kapasite
        self.yoklama = 0

    def _konum(self, anahtar) -> int:
        return hash(anahtar) % len(self._gozler)

    def koy(self, anahtar, deger) -> None:
        i = self._konum(anahtar)
        while self._gozler[i] is not BOS and self._gozler[i] is not SILINDI:
            if self._gozler[i][0] == anahtar:
                break                                   # güncelleme
            i = (i + 1) % len(self._gozler)             # doğrusal yoklama
            self.yoklama += 1
        self._gozler[i] = (anahtar, deger)

    def al(self, anahtar):
        i = self._konum(anahtar)
        while self._gozler[i] is not BOS:                # BOS görülünce arama biter
            self.yoklama += 1
            if self._gozler[i] is not SILINDI and self._gozler[i][0] == anahtar:
                return self._gozler[i][1]
            i = (i + 1) % len(self._gozler)
        raise KeyError(anahtar)

    def sil(self, anahtar) -> None:
        i = self._konum(anahtar)
        while self._gozler[i] is not BOS:
            if self._gozler[i] is not SILINDI and self._gozler[i][0] == anahtar:
                self._gozler[i] = SILINDI                # mezar taşı bırakılır
                return
            i = (i + 1) % len(self._gozler)
        raise KeyError(anahtar)


tablo = AcikTablo()
for ad, olcum in [("kuzey", 12), ("guney", 18), ("dogu", 7)]:
    tablo.koy(ad, olcum)
print(tablo.al("guney"))       # 18
tablo.sil("guney")
print(tablo.al("dogu"))        # 7
```

#### Silmenin Sorunu

Açık adreslemede silme, göze yalnızca "boş" yazarak yapılamaz. Arama, ilk boş gözü
görünce durduğu için, silinen göz aramanın yolunu keser: aynı zincirin ilerisindeki
elemanlar bulunamaz hâle gelir.

Çözüm, silinen gözü ayrı bir işaretle — **mezar taşıyla** — doldurmaktır. Arama mezar
taşını görünce devam eder, ekleme ise oraya yazabilir.

Bedeli birikimdir: çok sayıda silme sonrası tablo mezar taşlarıyla dolar ve aramalar
uzar. Gerçekleştirimler, mezar taşı oranı bir eşiği aştığında tabloyu yeniden
düzenler.

#### Kümelenme

Doğrusal yoklamanın bilinen zayıflığı **birincil kümelenmedir**: dolu gözlerin ardışık
blokları oluşur ve her yeni çakışma bloğu uzatır. Blok uzadıkça, o bölgeye düşen her
anahtarın yoklama sayısı artar; büyüme kendi kendini besler.

İki alternatif kural bunu azaltır:

- **Karesel yoklama:** Adım aralığı sabit değil, artan bir kare dizisidir. Ardışık
  bloklar oluşmaz; ancak aynı konumdan başlayan anahtarlar aynı sırayı izler (ikincil
  kümelenme).
- **Çift karma:** Adım aralığı, ikinci bir karma fonksiyonundan hesaplanır. Her anahtar
  farklı bir sıra izler; kümelenme en aza iner, karşılığında ikinci karma hesabı gerekir.

Doğrusal yoklamanın bir üstünlüğü vardır ve önemsiz değildir: ardışık gözlere bakması,
önbellek satırı içinde kalmak anlamına gelir. Bilgisayarlar Nasıl Çalışır kursundaki
yerellik gözlemi burada doğrusal yoklamayı, kuramsal olarak daha iyi olan alternatiflere
karşı rekabetçi kılar.

#### İki Ailenin Karşılaştırması

| Ölçüt | Zincirleme | Açık adresleme |
|---|---|---|
| Yük çarpanı sınırı | $1$'i aşabilir | $1$'i aşamaz; eşik daha düşük tutulur |
| Bellek | Düğüm/liste ek yükü | Ek yapı yok, boş gözler var |
| Önbellek davranışı | Zayıf (dağınık liste) | İyi (bitişik gözler) |
| Silme | Doğrudan | Mezar taşı gerekir |
| En kötü durum | Tek kovada uzun liste | Tabloyu dolaşan uzun yoklama |
| Kovadaki yapı değiştirilebilir | Evet (liste yerine ağaç) | Hayır |

Son satır, pratik bir güvenlik önlemine kapı açar: kova uzunluğu bir eşiği aşarsa liste
yerine dengeli bir ağaç kullanılır ve en kötü durum $O(n)$ yerine $O(\log n)$ olur. Bu
tasarım, kasıtlı çakışma saldırılarına karşı savunma olarak yaygınlaşmıştır.

#### Maliyet Tablosu

| Yapı | Ortalama arama | En kötü arama | Silme |
|---|---|---|---|
| Zincirleme | $O(1 + \alpha)$ | $O(n)$ | $O(1 + \alpha)$ |
| Zincirleme (ağaçlı kova) | $O(1 + \alpha)$ | $O(\log n)$ | $O(\log n)$ |
| Açık adresleme | $O\left(\frac{1}{1-\alpha}\right)$ (başarısız) | $O(n)$ | Mezar taşıyla $O(1)$* |

\* Mezar taşı birikimi arttıkça bozulur.

Üçüncü satırdaki ifade, yük çarpanı $1$'e yaklaştıkça maliyetin neden hızla arttığını
gösterir: $\alpha = 0{,}9$ için **bulunamayan** bir anahtar ortalama on yoklama ister. Var
olan bir anahtarı bulmak daha ucuzdur — arama ilk eşleşmede durduğu için aynı yükte
yaklaşık iki buçuk yoklama yeter. Açık adreslemede eşik bu nedenle daha düşük tutulur.

#### Özet

- Zincirlemede çakışan elemanlar kovadaki bir listede, açık adreslemede tablonun başka
  gözlerinde saklanır.
- Zincirlemede ortalama maliyet yük çarpanına bağlıdır ve yük çarpanı $1$'i aşabilir.
- Açık adreslemede silme, mezar taşı gerektirir; aksi hâlde arama yolu kesilir.
- Doğrusal yoklama birincil kümelenme üretir; karesel yoklama ve çift karma bunu azaltır.
- Doğrusal yoklamanın önbellek davranışı, kuramsal dezavantajını pratikte telafi eder.
- Kova içi yapının ağaca dönüştürülmesi, en kötü durumu logaritmik yapar ve çakışma
  saldırılarına karşı savunma sağlar.

#### Sonraki Adım

Karma tablosu anahtar–değer eşlemesi kurar. Bazı problemlerde değer gerekmez; yalnızca
"bu eleman var mı" sorusu sorulur. Sonraki ders, bu soruya odaklanan küme yapılarını ve
küçük evrenlerde bit düzeyi işlemlerle kurulan çok verimli bir gerçekleştirimi ele alacak.

### Kümeler ve Çok Kümeler

Source: https://academia.sh/tr/kurslar/veri-yapilari/kumeler

Üyelik odaklı soyut tip, karma ve sıralı gerçekleştirimler, bit kümeleri ve sayaçlı çok kümeler.

Karma tablosu bir anahtarı bir değere eşler. Bazı problemlerde değer yoktur; sorulan tek
soru **"bu eleman var mı"** olur. Yinelenenlerin ayıklanması, bir kimliğin listede olup
olmadığının sınanması, iki koleksiyonun ortak elemanlarının bulunması bu sınıftandır.

**Küme (set)**, üyelik odaklı soyut veri tipidir: her eleman ya vardır ya yoktur, sayısı
tutulmaz, sırası tanımlı değildir.

#### Küme İşlemleri

| İşlem | Anlamı |
|---|---|
| `ekle` | Elemanı kümeye katar; zaten varsa değişiklik olmaz |
| `sil` | Elemanı çıkarır |
| `iceriyor_mu` | Üyelik sınaması |
| `birlesim` | İki kümenin tüm elemanları |
| `kesisim` | İkisinde birden bulunanlar |
| `fark` | Birincide olup ikincide olmayanlar |
| `alt_kume_mu` | Kapsama sınaması |

İlk üçü tekil elemanla, son dördü küme çiftiyle çalışır. Maliyetleri farklı düşünülür:
tekil işlemler eleman sayısından bağımsız olabilirken, küme işlemleri en az bir kümeyi
gezmek zorundadır.

#### Gerçekleştirim Seçenekleri

**Karma kümesi**, değeri olmayan bir karma tablosudur. Tekil işlemler ortalama sabit
zamanlıdır; sıra korunmaz.

**Sıralı küme**, elemanları sıralı tutan bir yapıyla (dengeli ağaç veya atlama listesi)
kurulur. Tekil işlemler logaritmiktir; karşılığında elemanlar sıralı gezilebilir ve
aralık sorgusu yapılabilir — "değeri 10 ile 20 arasında olanlar" gibi.

Seçim ölçütü nettir: sıra veya aralık gerekmiyorsa karma kümesi, gerekiyorsa sıralı
küme.

#### Bit Kümesi

Elemanlar $0$ ile $N-1$ arasındaki tam sayılarsa ve $N$ makul büyüklükteyse, üçüncü ve
çok daha verimli bir gerçekleştirim vardır: her eleman için tek bir bit.

**Bit kümesi (bitset)**, üyeliği bit düzeyinde tutar. Bilgisayarlar Nasıl Çalışır
kursundaki bit düzeyi işlemler burada doğrudan kullanılır.

```python
class BitKumesi:
    """0..N-1 aralığındaki tam sayıları bit düzeyinde tutar."""

    def __init__(self, evren: int) -> None:
        self.evren = evren
        self._bitler = 0                       # tek bir büyük tam sayı

    def ekle(self, deger: int) -> None:
        self._bitler |= 1 << deger             # ilgili biti kur

    def sil(self, deger: int) -> None:
        self._bitler &= ~(1 << deger)          # ilgili biti sıfırla

    def iceriyor_mu(self, deger: int) -> bool:
        return ((self._bitler >> deger) & 1) == 1

    def birlesim(self, digeri: "BitKumesi") -> "BitKumesi":
        sonuc = BitKumesi(self.evren)
        sonuc._bitler = self._bitler | digeri._bitler
        return sonuc

    def kesisim(self, digeri: "BitKumesi") -> "BitKumesi":
        sonuc = BitKumesi(self.evren)
        sonuc._bitler = self._bitler & digeri._bitler
        return sonuc

    def elemanlar(self) -> list[int]:
        return [i for i in range(self.evren) if self.iceriyor_mu(i)]

    def __len__(self) -> int:
        return bin(self._bitler).count("1")    # kurulu bit sayısı


a = BitKumesi(16)
b = BitKumesi(16)
for d in (1, 3, 5, 7):
    a.ekle(d)
for d in (3, 5, 9):
    b.ekle(d)

print(a.elemanlar(), b.elemanlar())            # [1, 3, 5, 7] [3, 5, 9]
print(a.kesisim(b).elemanlar())                # [3, 5]
print(a.birlesim(b).elemanlar())               # [1, 3, 5, 7, 9]
print(len(a), a.iceriyor_mu(7), a.iceriyor_mu(8))   # 4 True False
```

İki üstünlüğü vardır ve ikisi de büyüktür.

**Bellek.** Eleman başına bir bit kullanılır. Bir milyon elemanlık evren, 125 kilobayta
sığar; aynı kümeyi karma kümesiyle tutmak, eleman başına onlarca bayt ister.

**Küme işlemleri sözcük düzeyinde paraleldir.** İki bit kümesinin kesişimi, tek bir VE
işlemidir; işlemci 64 elemanı tek komutta işler. Karma kümesinde aynı işlem, elemanların
tek tek gezilmesini gerektirir.

Koşulu ise dardır: evren küçük ve yoğun olmalıdır. Elemanlar milyarlar arasında dağınık
birkaç değerse, bit kümesi bellek israfına döner. Bu durumda seyrek gösterimler veya
karma kümesi tercih edilir.

Bit kümeleri, veritabanı dizinlerinde satır kümelerini birleştirmek, çizge
algoritmalarında ziyaret edilmiş düğümleri işaretlemek ve izin kümelerini tutmak için
yaygın kullanılır.

#### Çok Küme

Küme, bir elemanın var olup olmadığını söyler; **kaç kez** var olduğunu söylemez. Sayı
gerektiğinde **çok küme (multiset)** kullanılır: her elemanla birlikte bir sayaç tutulur.

```python
def frekans(olcumler: list[int]) -> dict[int, int]:
    """Her değerin kaç kez geçtiğini sayar."""
    sayac: dict[int, int] = {}
    for olcum in olcumler:
        sayac[olcum] = sayac.get(olcum, 0) + 1
    return sayac


olcumler = [12, 18, 7, 12, 25, 12, 18]
print(frekans(olcumler))                       # {12: 3, 18: 2, 7: 1, 25: 1}
print(max(frekans(olcumler).items(), key=lambda c: c[1]))   # (12, 3)
```

Çok küme, aslında değeri sayı olan bir eşlemedir; ayrı bir yapı olarak anılmasının
nedeni, küme işlemlerinin sayaçlarla tanımlanmasıdır: birleşimde sayaçların en büyüğü,
kesişimde en küçüğü alınır.

Tipik kullanımı sayım problemleridir: sözcük frekansları, en sık geçen değerler, örneklem
dağılımları. Veri analitiği müfredatındaki frekans çözümlemeleri bu yapının üzerine
kurulur.

#### Küme mi Liste mi

Yaygın bir başarım hatası, üyelik sınamasının liste üzerinde yapılmasıdır. Liste araması
doğrusaldır; aynı sınama küme üzerinde ortalama sabittir.

```python
kimlikler = list(range(100_000))
kume = set(kimlikler)

# Liste üzerinde üyelik: her sorgu tüm listeyi tarayabilir.
print(99_999 in kimlikler)      # True — en kötü durumda 100.000 karşılaştırma
# Küme üzerinde üyelik: karma ile tek adım.
print(99_999 in kume)           # True — kova hesabı ve birkaç karşılaştırma
```

Fark, sınama sayısıyla çarpılır: bir liste içinde $m$ sorgu yapmak $O(n \cdot m)$,
kümede $O(m)$'dir. Bir döngü içinde yapılan üyelik sınaması bu nedenle standart bir
gözden geçirme noktasıdır.

Kümeye dönüştürmenin de bir maliyeti vardır — tüm elemanların eklenmesi $O(n)$. Tek bir
sorgu için dönüştürmek anlamsızdır; sorgu sayısı arttıkça dönüşüm kendini öder.

#### Küme İşlemlerinin Maliyeti

İki kümenin kesişimi hesaplanırken küçük kümenin gezilip büyük kümede üyelik sınanması,
tersinden yapmaktan ucuzdur:

$$
O(\min(\lvert A\rvert, \lvert B\rvert)) \quad \text{yerine} \quad O(\lvert A\rvert)
$$

Bu ayrıntı, büyük veri kümeleriyle çalışırken belirgin fark yaratır ve kütüphane
gerçekleştirimlerinin çoğu bunu kendiliğinden yapar.

Sıralı kümelerde ise farklı bir yol vardır: iki sıralı diziyi birleştirir gibi tek
geçişte ilerlemek, $O(\lvert A\rvert + \lvert B\rvert)$ maliyetle tüm küme işlemlerini verir ve ek bellek
gerektirmez.

#### Maliyet Tablosu

| Yapı | Üyelik | Ekleme | Kesişim | Sıra |
|---|---|---|---|---|
| Karma kümesi | $O(1)$ ortalama | $O(1)$ ortalama | $O(\min(\lvert A\rvert, \lvert B\rvert))$ | Yok |
| Sıralı küme | $O(\log n)$ | $O(\log n)$ | $O(\lvert A\rvert + \lvert B\rvert)$ | Var |
| Bit kümesi | $O(1)$ | $O(1)$ | $O(N / w)$* | Değere göre |

\* $w$, işlemcinin sözcük genişliği; $N$ evren büyüklüğü.

#### Özet

- Küme, üyelik odaklı soyut tiptir; eleman ya vardır ya yoktur, sayısı ve sırası
  tutulmaz.
- Karma kümesi tekil işlemleri ortalama sabit zamanda yapar ama sıra korumaz; sıralı
  küme logaritmik maliyetle sıra ve aralık sorgusu sağlar.
- Bit kümesi, küçük ve yoğun tam sayı evrenlerinde eleman başına tek bit kullanır ve
  küme işlemlerini sözcük düzeyinde paralel yapar.
- Çok küme, elemanla birlikte sayaç tutar; sayım problemlerinin doğal yapısıdır.
- İki küme kesiştirilirken küçük olanın gezilmesi, maliyeti küçük kümenin boyutuna
  indirir.

#### Sonraki Adım

Buraya kadar kümeler bağımsız düşünüldü. Bazı problemlerde ise sorulan soru farklıdır:
"bu iki eleman aynı grupta mı?" ve gruplar zamanla birleşiyor. Sonraki ders, bu soruyu
neredeyse sabit zamanda yanıtlayan ayrık küme yapısını ele alacak.

### Ayrık Kümeler

Source: https://academia.sh/tr/kurslar/veri-yapilari/ayrik-kumeler

Dinamik gruplama problemi, birleştir–bul yapısı, sıraya göre birleştirme, yol sıkıştırma ve kullanım alanları.

Bir ağdaki iki bilgisayarın birbirine — doğrudan ya da aracılarla — bağlı olup olmadığı
sorulsun. Bağlantılar zamanla ekleniyor, hiç kaldırılmıyor. İki soru dönüşümlü olarak
geliyor: *"şu ikisi aynı grupta mı?"* ve *"şu iki grubu birleştir."*

Bu, **ayrık kümeler (disjoint sets)** yapısının — diğer adıyla **birleştir–bul
(union–find)** — çözdüğü problemdir. Adı, kümelerin kesişimsiz olmasından gelir: her
eleman tam olarak bir gruba aittir.

#### İki İşlem

| İşlem | Anlamı |
|---|---|
| `bul(x)` | `x`'in ait olduğu grubun temsilcisini döndürür |
| `birlestir(x, y)` | İki elemanın gruplarını tek grupta toplar |

"Aynı grupta mı" sorusu ayrı bir işlem gerektirmez: iki elemanın temsilcileri aynıysa
aynı gruptadırlar.

**Temsilci**, grubun herhangi bir elemanıdır; hangi eleman olduğu önemsizdir, önemli olan
aynı gruptaki tüm elemanların aynı temsilciyi bulmasıdır.

#### Orman Gösterimi

Yapı, her grubu bir ağaç olarak tutar; ağacın kökü grubun temsilcisidir. Tüm gruplar bir
arada bir **orman** oluşturur.

Gösterim tek bir dizidir: `ust[x]`, `x`'in bir üst düğümünü tutar. Kök, kendini gösterir.

```
ust:  [0, 0, 1, 3, 3]
       ↑
       0 ve 3 kök (kendini gösteriyor)

grup 1: 0 ← 1 ← 2        grup 2: 3 ← 4
```

`bul` işlemi, kök bulunana kadar üst bağları izler. `birlestir`, iki kökten birini
diğerine bağlar.

Bu saf hâliyle yapı, kötü durumda dejenere olabilir: her birleştirme kökü uzun bir
zincirin ucuna eklerse ağaç bir bağlı listeye döner ve `bul` işlemi $O(n)$ olur.

#### İki İyileştirme

**Sıraya göre birleştirme.** Birleştirmede, küçük ağacın kökü büyüğüne bağlanır.
Böylece derinlik ancak eşit büyüklükteki iki ağaç birleştiğinde artar; ağaç yüksekliği
$O(\log n)$ ile sınırlanır. Büyüklük ölçütü olarak eleman sayısı veya tahmini yükseklik
(sıra) kullanılır. İkisi de aynı sınırı verir; eleman sayısı, grup büyüklüğünün ayrıca
sorulabilmesi gibi bir yan yarar sağladığı için sık tercih edilir. Yol sıkıştırma
uygulandığında tahmini yükseklik gerçek yüksekliği aşabilir — bu, ölçütün yalnızca
birleştirme kararında kullanıldığı ve kesinliğinin gerekmediği anlamına gelir.

**Yol sıkıştırma.** `bul` işlemi kökü bulurken, yol üzerindeki tüm düğümleri doğrudan
köke bağlar. Bir sonraki sorgu aynı yolu tekrar izlemez. İşlem, sorgunun yan ürünü
olarak yapıyı düzleştirir.

İkisi birlikte uygulandığında, $m$ işlemin toplam maliyeti neredeyse doğrusaldır: işlem
başına düşen amortize maliyet, pratikte sabit kabul edilebilecek kadar yavaş büyüyen bir
fonksiyonla sınırlıdır. Kesin ifade ve kanıtı **İleri Algoritmalar** kursuna aittir; bu
kurs için yeterli olan, iki iyileştirmenin birlikte kullanıldığıdır.

```python
class AyrikKumeler:
    """Birleştir–bul; sıraya göre birleştirme ve yol sıkıştırma ile."""

    def __init__(self, n: int) -> None:
        self._ust = list(range(n))       # başlangıçta herkes kendi grubunda
        self._boyut = [1] * n
        self.grup_sayisi = n

    def bul(self, x: int) -> int:
        kok = x
        while self._ust[kok] != kok:     # köke kadar çık
            kok = self._ust[kok]
        while self._ust[x] != kok:       # yol sıkıştırma: yolu köke bağla
            self._ust[x], x = kok, self._ust[x]
        return kok

    def birlestir(self, x: int, y: int) -> bool:
        a, b = self.bul(x), self.bul(y)
        if a == b:
            return False                 # zaten aynı grupta
        if self._boyut[a] < self._boyut[b]:
            a, b = b, a                  # büyük ağaç kök olsun
        self._ust[b] = a
        self._boyut[a] += self._boyut[b]
        self.grup_sayisi -= 1
        return True

    def ayni_grupta_mi(self, x: int, y: int) -> bool:
        return self.bul(x) == self.bul(y)


ak = AyrikKumeler(6)                     # 0..5 arası altı eleman
ak.birlestir(0, 1)
ak.birlestir(1, 2)
ak.birlestir(3, 4)

print(ak.ayni_grupta_mi(0, 2))           # True
print(ak.ayni_grupta_mi(0, 3))           # False
print(ak.grup_sayisi)                    # 3   — {0,1,2}, {3,4}, {5}

print(ak.birlestir(0, 2))                # False — zaten birlikteydiler
ak.birlestir(2, 4)
print(ak.ayni_grupta_mi(1, 3), ak.grup_sayisi)   # True 2
```

`birlestir` işleminin mantıksal değer döndürmesi pratik bir ayrıntıdır: çağıran,
gerçekten bir birleşme olup olmadığını öğrenir. Bu bilgi, sonraki bölümdeki kullanım
alanlarında doğrudan işe yarar.

#### İzleme

Yapının nasıl düzleştiğini görmek için üst dizisi adım adım incelenebilir:

```python
ak = AyrikKumeler(5)
ak.birlestir(1, 2)
ak.birlestir(3, 4)
ak.birlestir(2, 4)
print(ak._ust)               # [0, 1, 1, 1, 3]  — 3'ün kökü hâlâ dolaylı

ak.bul(4)                    # yol sıkıştırma çalışır
print(ak._ust)               # [0, 1, 1, 1, 1]  — 4 doğrudan köke bağlandı
```

İlk çıktıda `4` düğümünün kökü iki adımda bulunuyordu (`4 → 3 → 1`); tek bir `bul`
çağrısından sonra bağ doğrudan köke işaret ediyor. Sıkıştırma ayrı bir bakım işlemi
değildir — sorgunun kendisi yapıyı iyileştirir.

#### Neyi Yapamaz

Yapının bilinen sınırı, **ayırmanın desteklenmemesidir**. Gruplar birleşir, ayrılmaz.
Bir bağlantı kaldırıldığında grupların yeniden hesaplanması gerekir; bu, yapıyı sıfırdan
kurmak demektir.

İkinci sınır, grup üyelerinin listelenememesidir. Yapı yalnızca "aynı grupta mı"
sorusunu yanıtlar; bir grubun elemanlarını saymak veya listelemek için ek kayıt tutulur.

Bu kısıtlar tesadüf değildir: yapının hızı, tam olarak bu bilgileri tutmamasından gelir.

#### Kullanım Alanları

**Bağlı bileşenler.** Bir çizgede hangi düğümlerin birbirine ulaşabildiği, kenarlar
eklendikçe bu yapıyla izlenir. Bu kursun son konusunda aynı soru gezinme algoritmalarıyla
da yanıtlanacak; ayrık kümeler, kenarların akış hâlinde geldiği durumda daha uygundur.

**Minimum kapsayan ağaç.** Kenarları ağırlığa göre sıralayıp döngü oluşturmayanları
seçen algoritma, "bu kenar döngü oluşturur mu" sorusunu ayrık kümelerle sorar: iki uç
zaten aynı gruptaysa kenar atlanır. Algoritmanın kendisi **Algoritmalar** kursunda ele
alınır.

**Denklik sınıfları.** "Şu ikisi aynı sayılır" biçimindeki kuralların birikimiyle oluşan
gruplar — aynı kişiye ait hesapların birleştirilmesi, aynı nesneyi gösteren kayıtların
eşleştirilmesi — doğrudan bu yapıyla tutulur.

**Izgara problemleri.** Bir ızgarada bitişik hücrelerin birleştirilmesiyle oluşan
bölgeler (görüntüdeki bağlı alanlar, sızma modelleri) aynı biçimde izlenir.

Yapının bir başka özelliği, işlemlerin **sırasından bağımsız** sonuç vermesidir: aynı
birleştirme kümesi hangi sırayla uygulanırsa uygulansın, oluşan gruplar aynıdır. Değişen
yalnızca ağaçların iç biçimidir; bu da sorguların sonucunu etkilemez.

#### Maliyet Tablosu

| Gerçekleştirim | `bul` | `birlestir` |
|---|---|---|
| Saf orman | $O(n)$ | $O(n)$ |
| Sıraya göre birleştirme | $O(\log n)$ | $O(\log n)$ |
| + yol sıkıştırma | Amortize neredeyse sabit | Amortize neredeyse sabit |

#### Özet

- Ayrık kümeler yapısı, elemanları kesişimsiz gruplara ayırır ve iki işlem sunar: grubun
  temsilcisini bulmak ve iki grubu birleştirmek.
- Gruplar bir orman olarak tutulur; kök, grubun temsilcisidir.
- Sıraya göre birleştirme, küçük ağacı büyüğe bağlayarak yüksekliği logaritmik tutar.
- Yol sıkıştırma, `bul` sırasında yol üzerindeki düğümleri doğrudan köke bağlayarak
  yapıyı düzleştirir.
- İkisi birlikte, işlem başına amortize neredeyse sabit maliyet verir.
- Yapı ayırmayı ve grup elemanlarını listelemeyi desteklemez; hızı bu bilgileri
  tutmamasından gelir.

#### Sonraki Adım

Bu konuda gruplar için ağaç gösterimi kullanıldı ama ağaçların kendisi tanımlanmadı.
Sonraki konu, ağaçları başlı başına ele alacak: terminoloji, gezinme yöntemleri, arama
ağaçları, denge sorunu ve öncelik kuyruğunu gerçekleyen yığın yapısı.

## Ağaçlar

Ağaç terminolojisinden dengeli arama ağaçlarına, yığınlara, sözcük ağaçlarına ve aralık yapılarına.

### Ağaç Terminolojisi

Source: https://academia.sh/tr/kurslar/veri-yapilari/agac-terminolojisi

Kök, çocuk, yaprak, derinlik ve yükseklik kavramları; ağacın tanımı, gösterim seçenekleri ve kullanım alanları.

Buraya kadarki yapılar doğrusaldı: her elemanın en fazla bir öncesi ve bir sonrası vardı.
Ayrık kümeler dersinde bu kırıldı — gruplar, her düğümün bir üstü olduğu ama bir üstün
birden çok altı olabildiği yapılarla tutuldu.

Bu konu, o yapıyı başlı başına ele alır. **Ağaç (tree)**, dallanan ilişkileri
modelleyen temel yapıdır ve bilgisayar biliminin her katmanında karşımıza çıkar.

#### Tanım

Ağaç, iki koşulu sağlayan bir düğüm–bağ yapısıdır:

1. Tüm düğümler birbirine bağlıdır; hiçbiri kopuk değildir.
2. Hiçbir döngü yoktur; iki düğüm arasında tam olarak bir yol vardır.

Bu iki koşulun sayısal sonucu şudur: $n$ düğümlü bir ağacın tam olarak $n - 1$ bağı
vardır. Bir bağ daha eklenirse döngü oluşur, bir bağ çıkarılırsa yapı ikiye ayrılır.

Ağaçların çoğu **köklüdür**: bir düğüm kök seçilir ve tüm bağlar ondan uzağa doğru
yönlenmiş sayılır. Bu kurs boyunca "ağaç" denildiğinde köklü ağaç kastedilir.

#### Terimler

```
                 (12)          ← kök, derinlik 0
                /    \
            (18)      (7)      ← derinlik 1
           /   \        \
       (25)   (14)      (30)   ← derinlik 2, hepsi yaprak
```

| Terim | Anlamı | Örnekte |
|---|---|---|
| Kök | Üstü olmayan tek düğüm | 12 |
| Ebeveyn | Bir düğümün bir üstü | 18'in ebeveyni 12 |
| Çocuk | Bir düğümün bir altı | 12'nin çocukları 18 ve 7 |
| Kardeş | Aynı ebeveynin çocukları | 25 ve 14 |
| Yaprak | Çocuğu olmayan düğüm | 25, 14, 30 |
| İç düğüm | En az bir çocuğu olan düğüm | 12, 18, 7 |
| Ata | Kökten düğüme giden yoldaki düğümler | 25'in ataları: 18, 12 |
| Soy | Bir düğümün altındaki tüm düğümler | 18'in soyu: 25, 14 |
| Alt ağaç | Bir düğüm ve tüm soyu | 18 köklü alt ağaç |
| Derinlik | Kökten düğüme giden bağ sayısı | 25'in derinliği 2 |
| Yükseklik | Düğümden en uzak yaprağa bağ sayısı | 12'nin yüksekliği 2 |
| Dallanma çarpanı | Bir düğümün çocuk sayısı | 12 için 2 |

**Derinlik ve yükseklik** sık karıştırılır. Derinlik yukarıdan, yükseklik aşağıdan
ölçülür. Kökün derinliği sıfır, yapraklarınki en büyüktür; yaprakların yüksekliği sıfır,
kökünki en büyüktür. Ağacın yüksekliği, kökün yüksekliğidir.

Birden çok kopuk ağacın oluşturduğu yapıya **orman** denir. Ayrık kümeler dersindeki
gösterim bir ormandı: her grup ayrı bir ağaçtı.

#### Ağaçlar Nerede Görünür

Ağaç, "her şeyin bir üstü var ama bir üstün birden çok altı olabilir" biçiminde
tanımlanan her ilişkinin yapısıdır:

- **Dosya sistemi.** Dizinler ve dosyalar; kök dizinden yapraklara. Linux müfredatındaki
  dizin hiyerarşisi bu yapıdadır.
- **Belge yapısı.** İşaretleme dillerinde iç içe etiketler; her etiketin bir kapsayıcısı,
  birden çok içeriği vardır.
- **Ayrıştırma ağacı.** Bilgisayarlar Nasıl Çalışır kursunda kurulan soyut sözdizim
  ağacı; ifade önceliği ağacın biçiminde kodlanıyordu.
- **Karar yapıları.** Her düğümde bir soru, her dalda bir yanıt; makine öğrenmesindeki
  karar ağaçları bu düzendedir.
- **Kuruluş şemaları ve kategori hiyerarşileri.** Doğrudan modelleme.

Bu kadar geniş bir kullanım alanı, ağaçlar üzerinde tanımlı işlemlerin — gezinme, arama,
derinlik hesabı — her yerde tekrar tekrar karşımıza çıkması demektir.

#### Gösterim Seçenekleri

Ağaç üç ana biçimde saklanır.

**Çocuk listeleri.** Her düğüm, çocuklarının listesini tutar. Genel ağaçlar için en
doğal gösterimdir; dallanma çarpanı değişken olabilir. Bedeli, düğüm başına bir liste
yapısıdır.

**İlk çocuk – sonraki kardeş.** Her düğüm iki bağ tutar: ilk çocuğu ve bir sonraki
kardeşi. Değişken sayıda çocuk, sabit sayıda bağla temsil edilir; genel ağaç, ikili bir
yapıya indirgenmiş olur.

**Dizi gösterimi.** Düğümler bir dizide tutulur ve ilişki, dizin aritmetiğiyle
hesaplanır. Yalnızca ağacın biçimi düzenliyse uygulanabilir; sonraki derste ikili ağaçlar
için tanımlanacaktır.

```python
class AgacDugumu:
    """Genel ağaç düğümü: değer ve çocuk listesi."""

    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.cocuklar: list["AgacDugumu"] = []

    def cocuk_ekle(self, cocuk: "AgacDugumu") -> "AgacDugumu":
        self.cocuklar.append(cocuk)
        return cocuk


def yukseklik(dugum: AgacDugumu) -> int:
    """Düğümden en uzak yaprağa olan bağ sayısı."""
    if not dugum.cocuklar:
        return 0                                  # yaprağın yüksekliği sıfır
    return 1 + max(yukseklik(c) for c in dugum.cocuklar)


def dugum_sayisi(dugum: AgacDugumu) -> int:
    return 1 + sum(dugum_sayisi(c) for c in dugum.cocuklar)


def yaprak_sayisi(dugum: AgacDugumu) -> int:
    if not dugum.cocuklar:
        return 1
    return sum(yaprak_sayisi(c) for c in dugum.cocuklar)


kok = AgacDugumu(12)
sol = kok.cocuk_ekle(AgacDugumu(18))
sag = kok.cocuk_ekle(AgacDugumu(7))
sol.cocuk_ekle(AgacDugumu(25))
sol.cocuk_ekle(AgacDugumu(14))
sag.cocuk_ekle(AgacDugumu(30))

print(yukseklik(kok), dugum_sayisi(kok), yaprak_sayisi(kok))   # 2 6 3
print(yukseklik(sol), yukseklik(sag))                          # 1 1
```

Üç işlevin de özyinelemeli yazılması tesadüf değildir: ağacın tanımı özyinelemelidir —
bir ağaç, bir kök ve onun alt ağaçlarıdır. Programlama Temelleri kursunda "problem
tanımı dallanıyorsa özyineleme doğaldır" denmişti; ağaçlar bu ifadenin kanonik örneğidir.

#### Yapıyı Doğrulamak

Bir yapının gerçekten ağaç olup olmadığı iki koşulla sınanır: bağ sayısı düğüm sayısının
bir eksiği olmalı ve yapı bağlı olmalıdır. İkisi birlikte döngüsüzlüğü de güvenceye alır.

Pratikte üçüncü bir sınama da yapılır: her düğüme yalnızca bir üstten gelinmelidir. Bir
düğüme iki ayrı ebeveynden bağ varsa yapı ağaç değil, genel bir çizgedir; gezinme
algoritmaları o düğümü iki kez ziyaret eder ve sonuç bozulur.

#### Yükseklik Neden Önemli

Ağaç üzerindeki hemen tüm işlemlerin maliyeti, düğüm sayısıyla değil **yükseklikle**
orantılıdır: kökten yaprağa inen bir yol izlenir.

Bu, bir soruyu doğrudan önemli kılar: $n$ düğümlü bir ağacın yüksekliği ne olabilir?

- **En iyi durum:** Her düğüm çocuklarını dengeli dağıtırsa yükseklik $O(\log n)$'dir.
- **En kötü durum:** Her düğümün tek çocuğu varsa ağaç bir bağlı listeye dönüşür ve
  yükseklik $O(n)$ olur.

Bu nedenle ağaç yapılarının değerlendirilmesinde sorulacak ilk soru, yüksekliğin neyle
sınırlandığıdır. İki uç arasındaki fark, bu konunun geri kalanının ana meselesidir: arama ağaçlarının
dengeli tutulması, tam olarak yüksekliği logaritmik sınırda tutma çabasıdır.

#### Özet

- Ağaç, döngüsüz ve bağlı bir düğüm yapısıdır; $n$ düğümlü ağacın $n-1$ bağı vardır.
- Köklü ağaçta bağlar kökten uzağa yönlenir; kök dışındaki her düğümün tam bir ebeveyni
  vardır.
- Derinlik kökten aşağı, yükseklik düğümden yaprağa ölçülür; ağacın yüksekliği kökün
  yüksekliğidir.
- Ağaçlar dosya sistemlerinden ayrıştırma yapılarına kadar dallanan her ilişkinin
  modelidir.
- Gösterim, çocuk listeleri, ilk çocuk–sonraki kardeş veya dizin aritmetiği ile yapılır.
- İşlem maliyetleri düğüm sayısıyla değil yükseklikle orantılıdır; yükseklik dengeye
  bağlı olarak logaritmik ile doğrusal arasında değişir.

#### Sonraki Adım

Genel ağaçlarda dallanma çarpanı değişkendir ve bu, gösterimi ile analizi zorlaştırır.
Sonraki ders, her düğümün en fazla iki çocuğu olduğu özel durumu — ikili ağaçları — ve bu
kısıtın getirdiği düzenli gösterim olanaklarını ele alacak.

### İkili Ağaçlar

Source: https://academia.sh/tr/kurslar/veri-yapilari/ikili-agaclar

En fazla iki çocuk kısıtı, dolu ve tam ağaç tanımları, yükseklik–düğüm sayısı ilişkisi ve dizi gösterimi.

Genel ağaçta bir düğümün kaç çocuğu olacağı belirsizdir; bu, gösterimi ve maliyet
çözümlemesini zorlaştırır. **İkili ağaç (binary tree)**, dallanmayı en fazla ikiye
sınırlar: her düğümün bir sol ve bir sağ çocuğu olabilir, ikisi de olmayabilir.

Kısıt yalnızca sadeleştirme değildir. İki çocuk, "büyük mü küçük mü", "sol mu sağ mı",
"evet mi hayır mı" biçimindeki ikili kararların doğal karşılığıdır; bu nedenle arama
ağaçları, karar ağaçları ve ifade ağaçları hep ikilidir.

#### Sol ve Sağ Ayrı Bilgidir

Genel ağaçta çocukların sırası çoğu zaman anlamsızdır. İkili ağaçta ise sol ve sağ
**ayrı konumlardır**: tek çocuğu olan bir düğümün o çocuğu sol mu sağ mı, yapının
parçasıdır.

Bu ayrım, sonraki derslerde anlam kazanır: arama ağacında sol küçükleri, sağ büyükleri
taşır; çıkarma işlemini gösteren bir ifade ağacında sol ile sağın yer değiştirmesi sonucu
değiştirir.

#### Biçim Sınıfları

Üç tanım sık kullanılır ve karıştırılır.

**Dolu (full) ikili ağaç:** Her düğümün ya sıfır ya iki çocuğu vardır; tek çocuklu düğüm
yoktur.

**Tam (complete) ikili ağaç:** Son seviye dışındaki tüm seviyeler tümüyle doludur ve son
seviyedeki düğümler soldan sağa yerleşiktir. Boşluk yalnızca sağ uçta olabilir.

**Kusursuz (perfect) ikili ağaç:** Tüm seviyeler tümüyle doludur; yapraklar aynı
derinliktedir.

```
   dolu ama tam değil      tam ama kusursuz değil      kusursuz
        (a)                        (a)                    (a)
       /   \                      /   \                  /   \
     (b)   (c)                  (b)   (c)              (b)   (c)
          /   \                /   \   /              /  \   /  \
        (d)   (e)            (d)  (e)(f)            (d) (e)(f) (g)
```

Kusursuz bir ağaç hem doludur hem tamdır. Tam ağaç kavramı, sonraki derslerde yığın
yapısının temeli olacaktır: boşlukların yalnızca sağ uçta olması, ağacın diziye
sığdırılmasını mümkün kılar.

#### Yükseklik ve Düğüm Sayısı

İkili ağaçta her seviyede en fazla $2^d$ düğüm bulunur ($d$ derinlik). Buradan iki sınır
çıkar.

Yüksekliği $h$ olan bir ikili ağacın **en fazla** düğüm sayısı:

$$
1 + 2 + 4 + \dots + 2^{h} = 2^{h+1} - 1
$$

Tersinden okunduğunda, $n$ düğümlü bir ikili ağacın **en az** yüksekliği:

$$
h \geq \log_2(n + 1) - 1
$$

En kötü durumda ise her düğümün tek çocuğu vardır ve yükseklik $n - 1$ olur.

Bu iki sınır, bir önceki dersin kapanış sorusunu sayısallaştırır. Bin düğümlü bir ikili
ağacın yüksekliği, dengeliyse dokuz dolayında, dejenere ise dokuz yüz doksan dokuzdur.
Arama maliyeti yükseklikle orantılı olduğuna göre, aradaki fark yüz kattan fazladır.

#### Bağlantılı Gösterim

Genel gösterim, her düğümün iki bağ tutmasıdır:

```python
class IkiliDugum:
    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.sol: "IkiliDugum | None" = None
        self.sag: "IkiliDugum | None" = None


def dugum_sayisi(dugum: IkiliDugum | None) -> int:
    if dugum is None:
        return 0
    return 1 + dugum_sayisi(dugum.sol) + dugum_sayisi(dugum.sag)


def yukseklik(dugum: IkiliDugum | None) -> int:
    if dugum is None:
        return -1                       # boş ağacın yüksekliği -1 kabul edilir
    return 1 + max(yukseklik(dugum.sol), yukseklik(dugum.sag))


def dolu_mu(dugum: IkiliDugum | None) -> bool:
    if dugum is None:
        return True
    if (dugum.sol is None) != (dugum.sag is None):
        return False                    # tek çocuklu düğüm bulundu
    return dolu_mu(dugum.sol) and dolu_mu(dugum.sag)


kok = IkiliDugum(12)
kok.sol = IkiliDugum(18)
kok.sag = IkiliDugum(7)
kok.sol.sol = IkiliDugum(25)
kok.sol.sag = IkiliDugum(14)

print(dugum_sayisi(kok), yukseklik(kok))    # 5 2
print(dolu_mu(kok))                          # True
kok.sag.sol = IkiliDugum(30)                 # 7 düğümüne tek çocuk eklendi
print(dolu_mu(kok))                          # False
```

Boş ağacın yüksekliğinin $-1$ kabul edilmesi bir sözleşmedir; tek düğümlü ağacın
yüksekliği böylece $0$ çıkar ve önceki dersteki tanımla tutarlı kalır.

#### Dizi Gösterimi

Ağaç **tam** ise, bağlara hiç gerek kalmaz. Düğümler seviye seviye, soldan sağa bir
diziye yerleştirilir; ilişki dizin aritmetiğiyle hesaplanır:

$$
\text{sol}(i) = 2i + 1, \qquad \text{sağ}(i) = 2i + 2, \qquad \text{ebeveyn}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor
$$

```python
agac = [12, 18, 7, 25, 14, 30]      # tam ikili ağaç, seviye sırasıyla

def sol(i: int) -> int: return 2 * i + 1
def sag(i: int) -> int: return 2 * i + 2
def ebeveyn(i: int) -> int: return (i - 1) // 2

print(agac[0], agac[sol(0)], agac[sag(0)])       # 12 18 7
print(agac[sol(1)], agac[sag(1)])                # 25 14
print(agac[ebeveyn(5)], agac[ebeveyn(4)])        # 7 18
```

Gösterimin üstünlükleri, birinci konudaki dizi tartışmasının aynısıdır: işaretçi ek yükü
yoktur ve düğümler bitişik durduğu için önbellek davranışı iyidir.

Kısıtı ise ağacın tam olmasıdır. Ağaç seyrekse — örneğin dejenere bir zincirse — dizi
gösterimi $2^{h+1}$ göz ister ve büyük bölümü boş kalır. Bu nedenle dizi gösterimi,
biçimi güvence altında olan yapılarda kullanılır; yığın bunun başlıca örneğidir.

#### Dengeli Ne Demektir

"Dengeli" sözcüğü tek bir tanıma sahip değildir. Üç ölçüt yaygındır: her düğümde alt
ağaç yüksekliklerinin farkının sınırlı olması, her düğümde alt ağaç boyutlarının oranının
sınırlı olması ve yaprakların aynı derinlikte olması.

Üçü de aynı amaca hizmet eder — yüksekliği logaritmik tutmak — ama farklı yapılar farklı
ölçütü seçer. Sonraki derslerde bunların üçü de karşınıza çıkacak: yükseklik farkı AVL
ağaçlarında, siyah düğüm sayısı kırmızı–siyah ağaçlarda, aynı derinlik ise 2-3
ağaçlarında kullanılır.

#### İkili Ağaçların Sayısı

Bir yan not, ağaç biçimlerinin ne kadar çeşitli olduğunu gösterir: $n$ düğümlü farklı
ikili ağaç biçimi sayısı hızla büyür — üç düğümle beş, dört düğümle on dört farklı biçim
vardır. Bu sayılar Katalan sayıları olarak bilinir ve bir sayma probleminin çözümüdür:
$n$ düğüm için kök seçildiğinde sol ve sağ alt ağaçlara kalan düğümlerin her bölüşümü
ayrı bir biçim üretir, bu yüzden sayı düğüm başına yaklaşık dört katına çıkar.

Pratik sonucu şudur: aynı veri kümesi, ekleme sırasına göre çok farklı biçimlerde
saklanabilir ve biçim, maliyeti belirler. Bu biçimlerin yalnızca küçük bir bölümü
dengelidir; rastgele bir biçime güvenmek, en kötü duruma açık kalmak demektir. Dengeleme kavramının gerekçesi budur.

#### Özet

- İkili ağaçta her düğümün en fazla iki çocuğu vardır ve sol ile sağ ayrı konumlardır.
- Dolu ağaçta tek çocuklu düğüm yoktur; tam ağaçta boşluk yalnızca son seviyenin sağ
  ucundadır; kusursuz ağaçta tüm seviyeler doludur.
- Yüksekliği $h$ olan ağaç en fazla $2^{h+1}-1$ düğüm taşır; $n$ düğümlü ağacın en az
  yüksekliği logaritmiktir, en kötü durumda ise doğrusaldır.
- Bağlantılı gösterimde her düğüm iki bağ tutar; boş ağacın yüksekliği $-1$ sayılır.
- Tam ağaçlar diziyle gösterilebilir: sol $2i+1$, sağ $2i+2$, ebeveyn $\lfloor (i-1)/2
  \rfloor$.
- Aynı veri kümesi birçok farklı ağaç biçimiyle saklanabilir; biçim maliyeti belirler.

#### Sonraki Adım

Ağaç kuruldu ama üzerinde henüz gezinilmedi. Bir ağacın tüm düğümlerini ziyaret etmenin
birden çok yolu vardır ve hangi yolun seçildiği, elde edilen sıralamayı belirler. Sonraki
ders dört temel gezinme düzenini ve her birinin hangi problemde kullanıldığını ele alacak.

### Ağaç Gezinmeleri

Source: https://academia.sh/tr/kurslar/veri-yapilari/agac-gezinmeleri

Ön, iç ve son sıralı gezinme, seviye sıralı gezinme, özyinelemeli ve yığıtla yazılmış biçimler, kullanım alanları.

Doğrusal bir yapıyı gezmenin tek bir doğal yolu vardır: baştan sona. Ağaçta ise her
düğümde en az iki yön bulunur ve hangi sırayla ilerleneceği bir karardır.

Bu ders dört temel gezinme düzenini tanımlar. Dördü de her düğüme tam bir kez uğrar,
dolayısıyla maliyetleri $O(n)$'dir; ayrıldıkları nokta **ziyaret sırasıdır** ve bu sıra,
gezinmenin hangi problemi çözebileceğini belirler.

#### Üç Derinlik Gezinmesi

İkili ağaçta bir düğümde üç iş vardır: düğümün kendisini ziyaret etmek, sol alt ağacı
gezmek, sağ alt ağacı gezmek. Düğümün ziyaretinin bu üçlü içindeki yeri, gezinmenin adını
verir.

- **Ön sıralı (preorder):** Önce düğüm, sonra sol, sonra sağ.
- **İç sıralı (inorder):** Önce sol, sonra düğüm, sonra sağ.
- **Son sıralı (postorder):** Önce sol, sonra sağ, sonra düğüm.

Sol alt ağacın her zaman sağdan önce gezildiğine dikkat edin; üç düzen de bu ortak
kuralı paylaşır.

```
            (12)
           /    \
       (18)      (7)
      /   \        \
   (25)   (14)     (30)
```

| Gezinme | Sıra |
|---|---|
| Ön sıralı | 12, 18, 25, 14, 7, 30 |
| İç sıralı | 25, 18, 14, 12, 7, 30 |
| Son sıralı | 25, 14, 18, 30, 7, 12 |

```python
class IkiliDugum:
    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.sol: "IkiliDugum | None" = None
        self.sag: "IkiliDugum | None" = None


def on_sirali(dugum, sonuc=None):
    sonuc = [] if sonuc is None else sonuc
    if dugum is not None:
        sonuc.append(dugum.deger)          # önce düğüm
        on_sirali(dugum.sol, sonuc)
        on_sirali(dugum.sag, sonuc)
    return sonuc


def ic_sirali(dugum, sonuc=None):
    sonuc = [] if sonuc is None else sonuc
    if dugum is not None:
        ic_sirali(dugum.sol, sonuc)
        sonuc.append(dugum.deger)          # ortada düğüm
        ic_sirali(dugum.sag, sonuc)
    return sonuc


def son_sirali(dugum, sonuc=None):
    sonuc = [] if sonuc is None else sonuc
    if dugum is not None:
        son_sirali(dugum.sol, sonuc)
        son_sirali(dugum.sag, sonuc)
        sonuc.append(dugum.deger)          # en son düğüm
    return sonuc


kok = IkiliDugum(12)
kok.sol = IkiliDugum(18); kok.sag = IkiliDugum(7)
kok.sol.sol = IkiliDugum(25); kok.sol.sag = IkiliDugum(14)
kok.sag.sag = IkiliDugum(30)

print(on_sirali(kok))       # [12, 18, 25, 14, 7, 30]
print(ic_sirali(kok))       # [25, 18, 14, 12, 7, 30]
print(son_sirali(kok))      # [25, 14, 18, 30, 7, 12]
```

Üç işlev arasındaki tek fark, `append` satırının konumudur. Bu, gezinme düzenlerinin
neden aynı ailenin üyeleri sayıldığını gösterir.

#### Hangi Gezinme Nerede

Sıra farkı, problem uygunluğunu belirler.

**Ön sıralı**, düğümü çocuklarından önce işler. Bir yapıyı **kopyalamak** veya
**dizileştirmek** için uygundur: üst düğüm oluşturulmadan alt düğümler bağlanamaz. Dizin
ağacını yazdırırken önce dizinin adının, sonra içindekilerin gelmesi de bu düzendir.

**İç sıralı**, ikili arama ağaçlarında elemanları **sıralı** verir. Sonraki dersin ana
sonucu budur; şimdilik yalnızca sıranın anlamlı olabildiği not edilir.

**Son sıralı**, düğümü çocuklarından sonra işler. Bir ağacı **serbest bırakmak** için
zorunludur: çocuklar bırakılmadan üst düğüm bırakılırsa çocuklara erişim kaybolur. Aynı
nedenle **ifade değerlendirmede** kullanılır — bir işlecin değeri, işlenenleri
hesaplanmadan bulunamaz. Yığıtlar dersindeki son ek gösterimi, bir ifade ağacının son
sıralı gezinmesidir.

**Seviye sıralı**, ağacı katman katman gezer ve sonraki bölümün konusudur.

#### Yığıtla Gezinme

Özyinelemeli yazım, çağrı yığıtını örtük olarak kullanır. Aynı gezinme, yığıt açıkça
tutularak da yazılabilir; Programlama Temelleri kursundaki "yığıtı elle taşımak"
dönüşümünün ağaçlardaki uygulamasıdır.

```python
def on_sirali_yigitla(kok) -> list[int]:
    """Ön sıralı gezinme; özyineleme yerine açık yığıt."""
    if kok is None:
        return []
    sonuc, yigit = [], [kok]
    while yigit:
        dugum = yigit.pop()
        sonuc.append(dugum.deger)
        if dugum.sag is not None:
            yigit.append(dugum.sag)        # sağ önce itilir
        if dugum.sol is not None:
            yigit.append(dugum.sol)        # sol sonra: önce o çekilir
    return sonuc


print(on_sirali_yigitla(kok))    # [12, 18, 25, 14, 7, 30]
```

Sağ çocuğun önce itilmesi, yığıtın ters sırayla çalışmasındandır: son giren ilk çıkar,
dolayısıyla sol çocuk önce işlenir. Bu ayrıntı atlandığında gezinme sağdan sola olur ve
sonuç sessizce değişir.

Açık yığıt kullanmanın gerekçesi, önceki kursta belirtilenle aynıdır: derinlik veriyle
büyüdüğünde çağrı yığıtı tükenebilir. Derin ağaçlarla çalışan üretim kodu bu nedenle
sıklıkla açık yığıt kullanır.

#### Seviye Sıralı Gezinme

Dördüncü düzen, derinlik değil **genişlik** boyunca ilerler: önce kök, sonra derinlik
1'deki tüm düğümler, sonra derinlik 2'dekiler.

Yapısı, derinlik gezinmesinin aynısıdır; tek fark, yığıt yerine **kuyruk**
kullanılmasıdır.

```python
from collections import deque

def seviye_sirali(kok) -> list[int]:
    if kok is None:
        return []
    sonuc, kuyruk = [], deque([kok])
    while kuyruk:
        dugum = kuyruk.popleft()           # ilk giren ilk çıkar
        sonuc.append(dugum.deger)
        if dugum.sol is not None:
            kuyruk.append(dugum.sol)
        if dugum.sag is not None:
            kuyruk.append(dugum.sag)
    return sonuc


def seviyelere_gore(kok) -> list[list[int]]:
    """Her seviyeyi ayrı listede döndürür."""
    if kok is None:
        return []
    sonuc, kuyruk = [], deque([kok])
    while kuyruk:
        seviye = []
        for _ in range(len(kuyruk)):       # o anki kuyruk uzunluğu = seviye genişliği
            dugum = kuyruk.popleft()
            seviye.append(dugum.deger)
            if dugum.sol is not None:
                kuyruk.append(dugum.sol)
            if dugum.sag is not None:
                kuyruk.append(dugum.sag)
        sonuc.append(seviye)
    return sonuc


print(seviye_sirali(kok))        # [12, 18, 7, 25, 14, 30]
print(seviyelere_gore(kok))      # [[12], [18, 7], [25, 14, 30]]
```

Yığıt yerine kuyruk kullanmanın gezinme düzenini tümüyle değiştirmesi, bu iki soyut
tipin neden ayrı ayrı tanımlandığını somutlaştırır. Aynı ikilik, çizgeler konusundaki
derine ve enine arama arasında birebir tekrarlanacaktır.

`seviyelere_gore` işlevindeki döngü, kuyruğun o anki uzunluğunu okuyarak seviye sınırını
belirler — yeni eklenenler bir sonraki tura kalır.

#### Maliyet

Gezinme, ağaç üzerinde tanımlı hemen her işlemin temelidir: düğüm sayma, yükseklik
hesaplama, kopyalama, karşılaştırma ve serbest bırakma — hepsi bir gezinme düzeninin
özelleşmiş hâlidir.

Dört gezinme de her düğüme bir kez uğrar: zaman maliyeti $O(n)$'dir.

Bellek maliyetleri ayrışır. Derinlik gezinmeleri yığıtta en fazla ağacın yüksekliği kadar
düğüm tutar — dengeli ağaçta $O(\log n)$, dejenere ağaçta $O(n)$. Seviye sıralı gezinme
ise kuyrukta en geniş seviyenin genişliği kadar düğüm tutar; kusursuz bir ağaçta bu, son
seviyedeki düğüm sayısıdır, yani $O(n)$.

Geniş ve sığ ağaçlarda derinlik gezinmesi, derin ve dar ağaçlarda seviye gezinmesi daha
az bellek kullanır.

#### Özet

- Ön, iç ve son sıralı gezinmeler yalnızca düğümün ziyaret anıyla ayrılır; üçü de sol
  alt ağacı sağdan önce gezer.
- Ön sıralı kopyalama ve dizileştirmeye, son sıralı serbest bırakma ve ifade
  değerlendirmeye, iç sıralı arama ağaçlarında sıralı çıktıya uygundur.
- Özyinelemeli gezinme çağrı yığıtını örtük kullanır; açık yığıtla yazılan biçim derin
  ağaçlarda güvenlidir.
- Yığıt yerine kuyruk kullanıldığında gezinme seviye sıralı olur.
- Dört gezinmenin de zaman maliyeti $O(n)$'dir; bellek maliyeti derinlik gezinmelerinde
  yüksekliğe, seviye gezinmesinde en geniş seviyeye bağlıdır.

#### Sonraki Adım

Gezinme, ağacın tamamını dolaşır. Oysa bir değeri **aramak** için tüm ağacı gezmek
gerekmemelidir; her düğümde doğru dalın seçilebilmesi yeterlidir. Sonraki ders, bunu
mümkün kılan sıralama kuralını — ikili arama ağacını — tanımlayacak.

### İkili Arama Ağaçları

Source: https://academia.sh/tr/kurslar/veri-yapilari/ikili-arama-agaclari

Sıralama değişmezi, arama–ekleme–silme işlemleri, üç silme durumu ve dejenere ağaç sorunu.

Önceki ders, ağacın tüm düğümlerini gezmenin $O(n)$ olduğunu gösterdi. Arama için bu
yeterli değildir; bir dizide doğrusal arama da aynı maliyettedir ve ağaç hiçbir kazanç
sağlamaz.

Kazanç, ağaca bir **düzen** eklendiğinde ortaya çıkar. Her düğümde hangi dala gidileceği
karşılaştırmayla belirlenebiliyorsa, arama tüm ağacı değil yalnızca bir yolu gezer.

#### Sıralama Değişmezi

**İkili arama ağacı (binary search tree)**, şu koşulu her düğümde sağlayan ikili ağaçtır:

> Sol alt ağaçtaki tüm değerler düğümün değerinden küçük, sağ alt ağaçtaki tüm değerler
> büyüktür.

Koşulun **tüm alt ağaç** için geçerli olması gerekir; yalnızca doğrudan çocuklara bakmak
yetmez. Bu, Programlama Temelleri kursunda tanımlanan anlamıyla bir **değişmezdir**: her
işlemden önce ve sonra doğru kalmalıdır.

```
            (12)
           /    \
        (7)      (25)
       /   \        \
    (3)    (10)     (30)
```

Bu ağaçta `25` köklü alt ağacın tüm değerleri $12$'den büyüktür; `7` köklü alt ağacınkiler
küçüktür. Aynı koşul her düğümde ayrı ayrı sağlanır.

Değişmezin doğrudan bir sonucu vardır ve önceki dersle bağlantılıdır: **iç sıralı gezinme,
değerleri artan sırada verir.** Sol alt ağaç önce gezildiği, sonra düğüm ziyaret
edildiği, en son sağ alt ağaç gezildiği için sıra kendiliğinden oluşur.

#### Arama

Arama, kökten başlar ve her düğümde tek bir karşılaştırma yapar:

- Aranan değer düğüme eşitse bulunmuştur.
- Küçükse sol alt ağaca, büyükse sağ alt ağaca inilir.
- Boş bir bağa ulaşılırsa değer ağaçta yoktur.

Her adımda alt ağaçlardan biri tümüyle elenir. Bu, sıralı dizideki ikili aramanın ağaç
üzerindeki karşılığıdır ve maliyeti **yükseklikle** orantılıdır.

```python
class DugumBST:
    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.sol: "DugumBST | None" = None
        self.sag: "DugumBST | None" = None


def ara(kok: DugumBST | None, hedef: int) -> tuple[bool, int]:
    """Hedefi arar; (bulundu, karşılaştırma sayısı) döndürür."""
    adim = 0
    dugum = kok
    while dugum is not None:
        adim += 1
        if hedef == dugum.deger:
            return True, adim
        dugum = dugum.sol if hedef < dugum.deger else dugum.sag
    return False, adim


def ekle(kok: DugumBST | None, deger: int) -> DugumBST:
    """Değeri yerine yerleştirir; kökü döndürür. Yinelenen değer eklenmez."""
    if kok is None:
        return DugumBST(deger)
    if deger < kok.deger:
        kok.sol = ekle(kok.sol, deger)
    elif deger > kok.deger:
        kok.sag = ekle(kok.sag, deger)
    return kok


def ic_sirali(dugum, sonuc=None):
    sonuc = [] if sonuc is None else sonuc
    if dugum is not None:
        ic_sirali(dugum.sol, sonuc)
        sonuc.append(dugum.deger)
        ic_sirali(dugum.sag, sonuc)
    return sonuc


kok = None
for deger in (12, 7, 25, 3, 10, 30):
    kok = ekle(kok, deger)

print(ic_sirali(kok))        # [3, 7, 10, 12, 25, 30]  — sıralı
print(ara(kok, 10))          # (True, 3)
print(ara(kok, 11))          # (False, 3)
```

`10` değeri üç karşılaştırmada bulunur: `12 → 7 → 10`. Altı elemanlık ağaçta doğrusal
arama en kötü durumda altı karşılaştırma yapardı.

#### Ekleme

Ekleme, başarısız bir aramadır: değerin bulunması gereken yer aranır ve boş bağa
ulaşıldığında yeni düğüm oraya bağlanır. Yeni düğüm her zaman **yaprak** olur; var olan
hiçbir bağ değişmez.

Bu sadelik, sıralama değişmezinin korunmasını da kendiliğinden sağlar: düğüm, arama
yolunun sonuna konduğu için tüm ata düğümlerin koşullarını zaten sağlar.

Yinelenen değerlerin ne olacağı bir tasarım kararıdır: yok sayılabilir, sağ alt ağaca
konabilir veya düğümde bir sayaç tutulabilir. Yukarıdaki gerçekleştirim ilkini seçmiştir;
çok küme davranışı isteniyorsa sayaç yaklaşımı uygundur.

#### Silme: Üç Durum

Silme, ağacın en dikkat isteyen işlemidir; silinen düğümün çocuk sayısına göre üç durum
vardır.

**Yaprak düğüm.** Doğrudan kaldırılır; ebeveynin ilgili bağı boşaltılır.

**Tek çocuklu düğüm.** Düğüm kaldırılır ve tek çocuğu, silinen düğümün yerine bağlanır.
Alt ağacın tamamı yukarı taşınmış olur; sıralama değişmezi korunur.

**İki çocuklu düğüm.** Doğrudan kaldırılamaz — iki alt ağaç tek bağa sığmaz. Çözüm,
düğümün değerini **ardılıyla** değiştirmektir: sağ alt ağacın en küçük değeri. Bu değer,
silinen düğümden büyük ama sağ alt ağaçtaki tüm değerlerden küçük olduğu için yerine
geçebilir. Ardıl düğümün sol çocuğu olamayacağından, onun silinmesi ilk iki duruma iner.

```python
def en_kucuk(dugum: DugumBST) -> DugumBST:
    while dugum.sol is not None:
        dugum = dugum.sol
    return dugum


def sil(kok: DugumBST | None, deger: int) -> DugumBST | None:
    if kok is None:
        return None
    if deger < kok.deger:
        kok.sol = sil(kok.sol, deger)
    elif deger > kok.deger:
        kok.sag = sil(kok.sag, deger)
    else:
        if kok.sol is None:                 # yaprak veya tek çocuk (sağ)
            return kok.sag
        if kok.sag is None:                 # tek çocuk (sol)
            return kok.sol
        ardil = en_kucuk(kok.sag)           # iki çocuk: ardılla değiştir
        kok.deger = ardil.deger
        kok.sag = sil(kok.sag, ardil.deger)
    return kok


kok = None
for deger in (12, 7, 25, 3, 10, 30):
    kok = ekle(kok, deger)

kok = sil(kok, 3)            # yaprak
print(ic_sirali(kok))        # [7, 10, 12, 25, 30]

kok = sil(kok, 25)           # tek çocuklu
print(ic_sirali(kok))        # [7, 10, 12, 30]

kok = sil(kok, 12)           # iki çocuklu: kök
print(ic_sirali(kok))        # [7, 10, 30]
```

Her silmeden sonra iç sıralı gezinmenin sıralı kalması, değişmezin korunduğunun
göstergesidir. Bu, bir veri yapısının doğruluğunu sınamanın standart yoludur: değişmezi
her işlemden sonra denetlemek.

#### Dejenere Ağaç Sorunu

İkili arama ağacının vaadi, tüm işlemlerin yükseklikle orantılı olmasıdır. Vaadin değeri,
yüksekliğin küçük olmasına bağlıdır — ve bunun hiçbir güvencesi yoktur.

Değerler artan sırada eklenirse her yeni düğüm sağa bağlanır; ağaç bir bağlı listeye
dönüşür:

```python
artan = None
for deger in (3, 7, 10, 12, 25, 30):        # sıralı ekleme
    artan = ekle(artan, deger)

karisik = None
for deger in (12, 7, 25, 3, 10, 30):        # dengeli sıra
    karisik = ekle(karisik, deger)

print(ara(artan, 30))        # (True, 6)  — tüm düğümler gezildi
print(ara(karisik, 30))      # (True, 3)
```

Aynı altı değer, aynı yapı, iki kat fark. Girdi sıralı geldiğinde — ki gerçek verilerde
sık karşılaşılan bir durumdur — ağaç en kötü hâline geçer.

Bu, sonraki üç dersin çıkış noktasıdır: ağacın yüksekliğini, ekleme sırasından bağımsız
olarak logaritmik tutmak.

#### Maliyet Tablosu

| Yapı | Arama | Ekleme | Silme | Sıralı gezinme |
|---|---|---|---|---|
| Karma tablosu | $O(1)$ ortalama | $O(1)$ ortalama | $O(1)$ ortalama | Desteklemez |
| İkili arama ağacı (dengeli) | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
| İkili arama ağacı (dejenere) | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |

#### Özet

- İkili arama ağacı, her düğümde sol alt ağacın küçük, sağ alt ağacın büyük değerler
  taşıması değişmezine dayanır.
- Değişmezin sonucu olarak iç sıralı gezinme değerleri artan sırada verir.
- Arama her adımda bir alt ağacı eler; maliyet yükseklikle orantılıdır.
- Ekleme, başarısız aramanın sonuna yaprak bağlamaktır; var olan bağlar değişmez.
- Silmede üç durum vardır; iki çocuklu düğüm, sağ alt ağacın en küçüğüyle değiştirilerek
  ilk iki duruma indirgenir.
- Yükseklik güvencesi yoktur: sıralı gelen girdi ağacı bağlı listeye çevirir ve tüm
  işlemler doğrusala düşer.

#### Sonraki Adım

Sorun tanımlandı: yükseklik, ekleme sırasına bağlı. Çözüm, ağacı her değişiklikten sonra
denetlemek ve gerekiyorsa yeniden düzenlemektir. Sonraki ders, bu düzenlemeyi yapan
dönme işlemini ve dengeyi güvenceye alan iki klasik ağaç ailesini ele alacak.

### Dengeli Arama Ağaçları

Source: https://academia.sh/tr/kurslar/veri-yapilari/dengeli-arama-agaclari

Dönme işlemi, AVL denge ölçütü ve dört durum, kırmızı–siyah ağaçların renk değişmezleri ve iki ailenin karşılaştırması.

Önceki ders bir sorunla bitti: ikili arama ağacının yüksekliği, ekleme sırasına bağlıdır
ve sıralı girdi ağacı bağlı listeye çevirir.

Çözüm, ağacı her değişiklikten sonra denetlemek ve dengesizlik oluştuğunda **yeniden
düzenlemektir**. Bu dersin konusu, düzenlemeyi yapan işlem ve onu ne zaman uygulayacağını
söyleyen iki klasik kural kümesidir.

#### Dönme

**Dönme (rotation)**, bir bağı yeniden yönlendirerek ağacın yüksekliğini değiştiren yerel
bir işlemdir. En önemli özelliği, **sıralama değişmezini bozmamasıdır.**

```
    sağa dönme (y ekseninde)          sola dönme
         (y)                (x)              (x)                (y)
        /   \              /   \            /   \              /   \
     (x)     C     →      A    (y)        A     (y)     →    (x)     C
    /   \                     /   \            /   \        /   \
   A     B                   B     C          B     C      A     B
```

Sağa dönmede `x` yukarı, `y` aşağı iner; `B` alt ağacı `x`'in sağından `y`'nin soluna
geçer. Sıralama açısından hiçbir şey değişmez: `A < x < B < y < C` ilişkisi her iki
biçimde de geçerlidir. Değişen tek şey yüksekliktir.

Dönme sabit sayıda bağ yazar; maliyeti $O(1)$'dir.

```python
class DugumAVL:
    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.sol: "DugumAVL | None" = None
        self.sag: "DugumAVL | None" = None
        self.yukseklik = 0                      # yaprak: 0


def h(dugum: DugumAVL | None) -> int:
    return -1 if dugum is None else dugum.yukseklik


def guncelle(dugum: DugumAVL) -> None:
    dugum.yukseklik = 1 + max(h(dugum.sol), h(dugum.sag))


def denge(dugum: DugumAVL | None) -> int:
    """Sol yükseklik eksi sağ yükseklik."""
    return 0 if dugum is None else h(dugum.sol) - h(dugum.sag)


def saga_dondur(y: DugumAVL) -> DugumAVL:
    x = y.sol
    y.sol = x.sag                # B alt ağacı yer değiştirir
    x.sag = y
    guncelle(y); guncelle(x)     # önce alttaki güncellenir
    return x                     # yeni kök


def sola_dondur(x: DugumAVL) -> DugumAVL:
    y = x.sag
    x.sag = y.sol
    y.sol = x
    guncelle(x); guncelle(y)
    return y
```

Yükseklik güncellemesinin sırası önemlidir: aşağıdaki düğüm önce güncellenmelidir, çünkü
üsttekinin yüksekliği ona bağlıdır.

#### AVL Ağacı

**AVL ağacı**, her düğümde şu koşulu zorunlu kılar:

> Sol ve sağ alt ağaçların yükseklik farkı en fazla birdir.

Bu fark, düğümün **denge çarpanıdır**. Değeri $-1$, $0$ veya $+1$ olmalıdır; $\pm 2$
olduğunda dengesizlik vardır ve düzeltilir.

Koşul katıdır ve karşılığında sıkı bir yükseklik sınırı verir: $n$ düğümlü bir AVL
ağacının yüksekliği $1{,}44 \log_2 n$'i aşmaz. Arama, ekleme ve silme bu nedenle her zaman
$O(\log n)$'dir — dejenere durum olanaksızdır.

#### Dört Durum

Ekleme sonrası dengesizlik dört biçimde ortaya çıkar. Adları, dengesiz düğümden itibaren
eklenen düğüme giden yolu tarif eder.

| Durum | Belirti | Çözüm |
|---|---|---|
| Sol–sol | Denge $> 1$, sol çocuğun dengesi $\geq 0$ | Sağa dönme |
| Sağ–sağ | Denge $< -1$, sağ çocuğun dengesi $\leq 0$ | Sola dönme |
| Sol–sağ | Denge $> 1$, sol çocuğun dengesi $< 0$ | Sol çocuğu sola döndür, sonra sağa dönme |
| Sağ–sol | Denge $< -1$, sağ çocuğun dengesi $> 0$ | Sağ çocuğu sağa döndür, sonra sola dönme |

Son iki durumda tek dönme yetmez: dengesizlik "zikzak" biçimindedir ve önce düzleştirilir,
sonra düzeltilir.

```python
def ekle_avl(kok: DugumAVL | None, deger: int) -> DugumAVL:
    if kok is None:
        return DugumAVL(deger)
    if deger < kok.deger:
        kok.sol = ekle_avl(kok.sol, deger)
    elif deger > kok.deger:
        kok.sag = ekle_avl(kok.sag, deger)
    else:
        return kok                                   # yinelenen değer

    guncelle(kok)
    d = denge(kok)

    if d > 1 and denge(kok.sol) >= 0:                # sol–sol
        return saga_dondur(kok)
    if d < -1 and denge(kok.sag) <= 0:               # sağ–sağ
        return sola_dondur(kok)
    if d > 1:                                        # sol–sağ
        kok.sol = sola_dondur(kok.sol)
        return saga_dondur(kok)
    if d < -1:                                       # sağ–sol
        kok.sag = saga_dondur(kok.sag)
        return sola_dondur(kok)
    return kok


def ic_sirali(dugum, sonuc=None):
    sonuc = [] if sonuc is None else sonuc
    if dugum is not None:
        ic_sirali(dugum.sol, sonuc)
        sonuc.append(dugum.deger)
        ic_sirali(dugum.sag, sonuc)
    return sonuc


# Sıralı ekleme: sade arama ağacında dejenere olurdu.
kok = None
for deger in (3, 7, 10, 12, 25, 30):
    kok = ekle_avl(kok, deger)

print(ic_sirali(kok))        # [3, 7, 10, 12, 25, 30]
print(kok.deger)             # 12   — kök kendiliğinden ortaya yerleşti
print(h(kok))                # 2    — dejenere ağaçta 5 olurdu
```

Altı değerin artan sırada eklenmesi, önceki derste yüksekliği beş olan bir zincir
üretiyordu. AVL kuralı aynı girdide yüksekliği ikide tutar; dönmeler ekleme sırasında
kendiliğinden çalışmıştır.

Bir eklemeden sonra en fazla **bir** dönme (veya çift dönme) gerekir; yükseklik
güncellemeleri ise kökten aşağı olan yol boyunca yapılır. Ekleme maliyeti bu nedenle
$O(\log n)$ kalır.

#### Kırmızı–Siyah Ağaçlar

İkinci klasik aile, dengeyi yüksekliklerle değil **renklerle** izler. Her düğüm kırmızı
veya siyah boyanır ve dört değişmez korunur:

1. Kök siyahtır.
2. Kırmızı bir düğümün çocukları siyahtır — iki kırmızı düğüm ardışık olamaz.
3. Kökten herhangi bir boş bağa giden tüm yollarda aynı sayıda siyah düğüm bulunur.
4. Boş bağlar siyah sayılır.

Üçüncü koşul, ağacın "siyah yükseklik" açısından mükemmel dengeli olmasını sağlar. En uzun
yol, en kısa yolun en fazla iki katı olabilir — çünkü en uzun yol kırmızı ve siyahın
dönüşümlüsü, en kısa yol tümüyle siyahtır. Buradan yükseklik sınırı çıkar:

$$
h \leq 2 \log_2 (n + 1)
$$

AVL'nin $1{,}44 \log_2 n$ sınırından daha gevşektir; ağaç biraz daha derin olabilir.
Karşılığında, dengeyi korumak için gereken yeniden düzenleme sayısı azdır: ekleme ve
silmede sabit sayıda dönme yeterlidir, AVL'de ise silme sırasında kök yoluna kadar dönme
zinciri oluşabilir.

#### İki Aileyi Seçmek

| Ölçüt | AVL | Kırmızı–siyah |
|---|---|---|
| Yükseklik sınırı | $\approx 1{,}44 \log_2 n$ | $\approx 2 \log_2 n$ |
| Arama | Biraz daha hızlı | Biraz daha yavaş |
| Ekleme/silme | Daha çok dönme | Daha az dönme |
| Uygun kullanım | Okuma ağırlıklı | Yazma ağırlıklı |

Genel amaçlı kütüphanelerin sıralı eşleme ve sıralı küme yapıları çoğunlukla
kırmızı–siyah ağaç kullanır: güncelleme maliyetinin daha öngörülebilir olması, genel
kullanımda arama farkından daha değerlidir.

Her iki ailenin de ortak bedeli, kod karmaşıklığıdır. Silme durumları özellikle çoktur ve
elle yazılan gerçekleştirimlerde hata kaynağıdır. Doğrusal yapılar konusundaki atlama
listesi, aynı beklenen maliyeti çok daha kısa kodla verdiği için bir alternatiftir —
farkı, güvencenin beklenen olması ve kesin olmamasıdır.

#### Özet

- Dönme, bağları yeniden yönlendirerek yüksekliği değiştiren ve sıralama değişmezini
  koruyan sabit maliyetli bir işlemdir.
- AVL ağacında her düğümün denge çarpanı $-1$, $0$ veya $+1$ olmalıdır; ihlal dört
  durumdan biriyle giderilir.
- Zikzak biçimli dengesizlikler (sol–sağ, sağ–sol) önce tek dönmeyle düzleştirilir.
- AVL yükseklik sınırı yaklaşık $1{,}44 \log_2 n$'dir; dejenere durum olanaksızdır.
- Kırmızı–siyah ağaç dengeyi renk değişmezleriyle izler; sınırı daha gevşektir ama
  güncellemede daha az dönme gerektirir.
- Okuma ağırlıklı yükte AVL, yazma ağırlıklı yükte kırmızı–siyah tercih edilir.

#### Sonraki Adım

İkili ağaçlarda denge, dönmelerle sonradan onarılıyor. Farklı bir yaklaşım, düğüm başına
birden çok anahtar tutup ağacın **tüm yapraklarını aynı derinlikte** tutmaktır. Sonraki
ders bu fikri kuran 2-3 ağaçlarını ele alacak.

### 2-3 ve 2-3-4 Ağaçları

Source: https://academia.sh/tr/kurslar/veri-yapilari/2-3-agaclari

Düğüm başına çok anahtar, bölünerek yukarı büyüme, kusursuz derinlik dengesi ve kırmızı–siyah ağaçlarla eşlik.

Önceki ders dengeyi dönmelerle onarıyordu: ağaç bozulur, sonra düzeltilir. Bu dersin
yaklaşımı farklıdır — ağaç **hiçbir zaman bozulmaz**, çünkü büyüme biçimi dengeyi tanım
gereği korur.

Fikir, ikili kısıtından vazgeçmektir: bir düğüm birden çok anahtar taşıyabilir.

#### İki Düğüm Türü

**2-3 ağacında** iki tür düğüm bulunur:

- **2-düğüm:** Bir anahtar, iki çocuk. Sol alt ağaç küçükleri, sağ alt ağaç büyükleri
  taşır — sıradan bir arama ağacı düğümü.
- **3-düğüm:** İki anahtar, üç çocuk. Sol alt ağaç birinci anahtardan küçükleri, orta alt
  ağaç iki anahtar arasındakileri, sağ alt ağaç ikinci anahtardan büyükleri taşır.

```
        [7 | 12]            ← 3-düğüm: iki anahtar, üç çocuk
       /    |    \
    [3]   [10]  [25 | 30]
```

Yapının belirleyici kuralı şudur: **tüm yapraklar aynı derinliktedir.** Bu, sonradan
sağlanan bir özellik değil, ekleme yönteminin doğrudan sonucudur.

#### Arama

Arama, ikili ağaçtakine benzer; tek fark, düğüm içinde birden çok anahtarın
karşılaştırılmasıdır. Anahtar düğümde bulunursa arama biter; bulunmazsa değerin hangi
aralığa düştüğüne bakılarak ilgili çocuğa inilir.

Düğüm içindeki karşılaştırma sayısı en fazla ikidir, yani sabittir. Maliyet yine
yükseklikle orantılıdır.

#### Ekleme: Aşağıdan Yukarı Büyüme

Ekleme her zaman bir yaprağa yapılır. Üç durum vardır:

**Yaprak 2-düğümse**, anahtar eklenir ve düğüm 3-düğüme dönüşür. Ağacın biçimi değişmez.

**Yaprak 3-düğümse**, geçici olarak üç anahtarlı bir düğüm oluşur. Bu düğüm **bölünür**:
ortadaki anahtar bir üst düğüme **terfi eder**, kalan iki anahtar iki ayrı 2-düğüm olur.

**Terfi eden anahtar üst düğümü de taşırırsa**, aynı bölünme bir üst seviyede tekrarlanır.
Bölünme köke kadar sürebilir; kök bölünürse yeni bir kök oluşur ve **ağacın yüksekliği
bir artar.**

Son madde, yapının denge güvencesinin kaynağıdır. Ağaç yapraklardan değil **kökten**
büyür; tüm yapraklar aynı anda bir seviye aşağı iner, dolayısıyla derinlik farkı hiçbir
zaman oluşmaz.

```python
class Dugum23:
    """2-3 ağacı düğümü: bir veya iki anahtar; sıfır, iki veya üç çocuk."""

    def __init__(self, anahtarlar: list[int], cocuklar: list | None = None) -> None:
        self.anahtarlar = anahtarlar
        self.cocuklar = cocuklar or []

    def yaprak_mi(self) -> bool:
        return not self.cocuklar


def _ekle(dugum: Dugum23, deger: int):
    """(düğüm, terfi) döndürür; terfi = (anahtar, sol, sağ) ya da None."""
    if dugum.yaprak_mi():
        anahtarlar = sorted(dugum.anahtarlar + [deger])
        if len(anahtarlar) <= 2:
            return Dugum23(anahtarlar), None            # 2-düğüm → 3-düğüm
        orta = anahtarlar[1]                            # taştı: ortayı terfi ettir
        return None, (orta, Dugum23([anahtarlar[0]]), Dugum23([anahtarlar[2]]))

    i = 0
    while i < len(dugum.anahtarlar) and deger > dugum.anahtarlar[i]:
        i += 1
    alt, terfi = _ekle(dugum.cocuklar[i], deger)
    if terfi is None:
        dugum.cocuklar[i] = alt
        return dugum, None

    anahtar, sol, sag = terfi                           # alttan bir anahtar geldi
    anahtarlar = dugum.anahtarlar[:i] + [anahtar] + dugum.anahtarlar[i:]
    cocuklar = dugum.cocuklar[:i] + [sol, sag] + dugum.cocuklar[i + 1:]
    if len(anahtarlar) <= 2:
        return Dugum23(anahtarlar, cocuklar), None
    orta = anahtarlar[1]                                # bu düğüm de taştı
    return None, (orta,
                  Dugum23([anahtarlar[0]], cocuklar[:2]),
                  Dugum23([anahtarlar[2]], cocuklar[2:]))


def ekle(kok: Dugum23 | None, deger: int) -> Dugum23:
    if kok is None:
        return Dugum23([deger])
    dugum, terfi = _ekle(kok, deger)
    if terfi is None:
        return dugum
    anahtar, sol, sag = terfi
    return Dugum23([anahtar], [sol, sag])               # kök bölündü: yükseklik arttı


def seviyeler(kok: Dugum23) -> list[list[list[int]]]:
    """Ağacı seviye seviye, düğümlerin anahtar listeleriyle gösterir."""
    sonuc, sira = [], [kok]
    while sira:
        sonuc.append([d.anahtarlar for d in sira])
        yeni = []
        for d in sira:
            yeni.extend(d.cocuklar)
        sira = yeni
    return sonuc


kok = None
for deger in (3, 7, 10, 12, 25, 30):          # sıralı ekleme
    kok = ekle(kok, deger)
    print(deger, "->", seviyeler(kok))

# 3  -> [[[3]]]
# 7  -> [[[3, 7]]]
# 10 -> [[[7]], [[3], [10]]]
# 12 -> [[[7]], [[3], [10, 12]]]
# 25 -> [[[7, 12]], [[3], [10], [25]]]
# 30 -> [[[7, 12]], [[3], [10], [25, 30]]]
```

Çıktı, büyümenin nasıl yürüdüğünü adım adım gösterir. Üçüncü eklemede kök taşar,
bölünür ve ağaç iki seviyeye çıkar. Beşinci eklemede bir yaprak taşar; orta anahtar
köke terfi eder ve kök 3-düğüme dönüşür.

Dikkat çekici olan, girdinin **sıralı** olmasıdır. Aynı sıra, sade ikili arama ağacında
yüksekliği beş olan bir zincir üretiyordu; burada yükseklik birdir.

#### 2-3-4 Ağaçları

Aynı fikir bir adım genişletilirse **2-3-4 ağacı** elde edilir: düğümler bir, iki veya üç
anahtar taşıyabilir. Bölünme eşiği dört anahtara çıkar; kural aynıdır.

Ek esneklik, bölünmelerin daha seyrek olmasını sağlar. Buna karşılık düğüm içi
karşılaştırma sayısı artar ve düğüm yapısı büyür.

#### Kırmızı–Siyah Ağaçlarla Eşlik

2-3-4 ağaçları ile önceki dersteki kırmızı–siyah ağaçlar arasında birebir bir karşılık
vardır: bir 2-3-4 ağacı, düğümleri ikili yapıya açılarak kırmızı–siyah ağaca çevrilebilir.

Karşılık şöyle kurulur: 2-düğüm siyah bir düğümdür; 3-düğüm, siyah bir düğüm ve ona
bağlı bir kırmızı çocuktur; 4-düğüm ise siyah bir düğüm ve iki kırmızı çocuğudur.
Kırmızı bağlar, "aslında aynı düğümün parçası" demektir.

Bu eşlik, kırmızı–siyah kurallarının kaynağını açıklar. İki ardışık kırmızı düğümün
yasaklanması, bir düğümün üçten fazla anahtar taşımamasıdır. Tüm yollarda siyah sayısının
eşit olması, tüm yaprakların aynı derinlikte olmasıdır.

Yani iki yapı aynı fikrin iki gösterimidir: biri düğüm başına çok anahtar tutar, diğeri
aynı bilgiyi ikili ağaçta renklerle kodlar. İkili gösterim, düğüm yapısının sabit
kalmasını sağladığı için gerçekleştirimde tercih edilir.

#### Yükseklik Sınırı

Tüm yapraklar aynı derinlikte olduğundan yükseklik doğrudan hesaplanır. Her düğüm en az
iki, en fazla üç çocuk taşıdığına göre:

$$
\log_3 (n+1) - 1 \leq h \leq \log_2 (n+1) - 1
$$

Her iki uçta da logaritmiktir; arama, ekleme ve silme $O(\log n)$'dir. Silme işlemi
eklemenin aynadaki görüntüsüdür: düğüm anahtarsız kalırsa kardeşinden ödünç alır, kardeş
de veremiyorsa iki düğüm birleştirilir ve eksilme bir üst seviyeye taşınır.

Silmede dikkat edilecek nokta, eksilmenin de köke doğru yayılabilmesidir: birleşme
zinciri köke ulaşırsa kök tek çocuğuyla değiştirilir ve ağacın yüksekliği bir azalır.
Büyüme gibi küçülme de yalnızca kökten olur; denge bu nedenle hiç bozulmaz.

#### Özet

- 2-3 ağacında düğümler bir veya iki anahtar taşır; 2-düğümün iki, 3-düğümün üç çocuğu
  vardır.
- Tüm yapraklar aynı derinliktedir ve bu, ekleme yönteminin doğrudan sonucudur.
- Taşan düğüm bölünür, orta anahtar üst düğüme terfi eder; kök bölündüğünde yükseklik
  bir artar.
- Ağaç yapraklardan değil kökten büyüdüğü için dengesizlik oluşmaz; sıralı girdi bile
  dejenere ağaç üretmez.
- 2-3-4 ağacı aynı fikrin üç anahtara genişletilmiş hâlidir ve kırmızı–siyah ağaçla
  birebir eşlenir.
- Yükseklik $\log_3(n+1) - 1$ ile $\log_2(n+1) - 1$ arasındadır; tüm işlemler
  logaritmiktir.

#### Sonraki Adım

Düğüm başına anahtar sayısı ikiden üçe çıkarıldığında ağaç sığlaştı. Sayı yüzlere
çıkarılırsa ne olur? Bu soru, verinin bellekte değil diskte durduğu durumlarda kritik
hâle gelir. Sonraki ders, blok tabanlı depolamaya göre tasarlanmış B-ağaçlarını ele alacak.

### B-Ağaçları

Source: https://academia.sh/tr/kurslar/veri-yapilari/b-agaclari

Blok tabanlı depolamaya göre tasarım, yüksek dallanma çarpanı, B+ ağacı yaprak zinciri ve dizin kullanımı.

Önceki ders, düğüm başına anahtar sayısını artırmanın ağacı sığlaştırdığını gösterdi. Bu
dersin sorusu şudur: sayı neden ikide veya üçte durdurulsun?

Yanıt, verinin nerede durduğuna bağlıdır. Veri bellekteyse fark küçüktür — bellek erişimi
zaten ucuzdur. Veri **diskteyse** durum değişir ve bu değişim, bir veri yapısı ailesinin
tümüyle bu koşula göre tasarlanmasına yol açmıştır.

#### Blok Gerçeği

Bilgisayarlar Nasıl Çalışır kursundaki bellek hiyerarşisi, kalıcı depolamayı en alt
katmana yerleştiriyordu: erişim, ana bellekten mertebelerce yavaştır.

İkinci ve daha belirleyici gerçek şudur: kalıcı depolama **blok** düzeyinde okunur. Tek
bir bayt istense de bloğun tamamı — kilobaytlar mertebesinde — getirilir. Dolayısıyla
maliyeti belirleyen şey okunan bayt sayısı değil, **kaç blok okunduğudur**.

Bu, ağaç tasarımını doğrudan değiştirir. Bellek içi bir ağaçta hedef, karşılaştırma
sayısını azaltmaktır; disk üzerindeki bir ağaçta hedef, **düğüm ziyareti sayısını**
azaltmaktır. Her düğüm ziyareti bir blok okumasıdır.

Sonuç açıktır: düğüm, bloğu dolduracak kadar büyük olmalıdır. Düğüm bloktan küçük olursa
getirilen bloğun bir bölümü boşa gider; büyük olursa tek bir düğüm için birden çok blok
okunur. İki durumda da okuma sayısı gereksiz yere artar.

#### B-Ağacı

**B-ağacı**, 2-3 ağacının genelleştirilmiş hâlidir. Bir $t$ parametresi (en küçük derece)
seçilir ve şu kurallar korunur:

- Kök dışındaki her düğüm en az $t-1$, en fazla $2t-1$ anahtar taşır.
- Anahtar sayısı $k$ olan iç düğümün $k+1$ çocuğu vardır.
- Tüm yapraklar aynı derinliktedir.

$t = 2$ alındığında 2-3-4 ağacı elde edilir; pratikte $t$, düğümün bir bloğa sığacağı
en büyük değer olarak seçilir — yüzler mertebesinde.

Ekleme ve silme, önceki dersteki bölünme ve birleştirme kurallarının aynısıdır. Taşan
düğüm ikiye bölünür, orta anahtar terfi eder; anahtarsız kalan düğüm kardeşinden ödünç
alır ya da onunla birleşir.

#### Yüksekliğin Sonucu

Dallanma çarpanının yüksek olması, yüksekliği çarpıcı biçimde düşürür:

$$
h \approx \log_{b} n
$$

Burada $b$ ortalama dallanma çarpanıdır.

```python
import math

def yukseklik(kayit_sayisi: int, dallanma: int) -> int:
    """Verilen dallanma çarpanıyla ağacın yaklaşık yüksekliği."""
    return math.ceil(math.log(kayit_sayisi, dallanma))


for dallanma in (2, 3, 100, 500):
    print(dallanma, yukseklik(1_000_000, dallanma), yukseklik(1_000_000_000, dallanma))

# 2   20 30
# 3   13 19
# 100 3  5
# 500 3  4
```

Bir milyon kayıt, ikili ağaçta yirmi düğüm ziyareti gerektirir; dallanma çarpanı yüz olan
bir B-ağacında üç. Disk erişimi baskın maliyet olduğunda bu, yirmi blok okuması ile üç
blok okuması arasındaki farktır.

Bir milyar kayıtta bile derinlik beştir. Kökün ve üst seviyelerin bellekte önbelleklenmesi
düşünüldüğünde, gerçek disk erişimi genellikle bir veya iki bloğa iner.

#### B+ Ağacı

Yaygın olarak kullanılan varyant **B+ ağacıdır** ve iki değişiklik içerir:

**Kayıtlar yalnızca yapraklarda tutulur.** İç düğümler yalnızca yönlendirme anahtarları
taşır. Bu, iç düğümlerin daha çok anahtar sığdırmasını sağlar — dallanma çarpanı artar,
ağaç daha da sığlaşır.

**Yapraklar birbirine bağlıdır.** Her yaprak, bir sonrakini gösterir; yapraklar sıralı
bir bağlı liste oluşturur.

İkinci değişiklik, aralık sorgularını dönüştürür. "Değeri 100 ile 200 arasında olan tüm
kayıtlar" sorgusu, sade B-ağacında ağacın tekrar tekrar gezilmesini gerektirirdi. B+
ağacında ise başlangıç noktası bir kez aranır, ardından yaprak zinciri boyunca sıralı
ilerlenir.

Bu, veritabanı dizinlerinin neredeyse tamamının B+ ağacı olmasının nedenidir: hem tekil
arama hem aralık taraması aynı yapıyla verimli yapılır. Veritabanları müfredatındaki
dizin tasarımı bu yapının üzerine kurulur.

#### Karşılaştırma

| Ölçüt | Dengeli ikili ağaç | B / B+ ağacı |
|---|---|---|
| Düğüm boyutu | Küçük (birkaç bağ) | Blok boyutunda |
| Yükseklik ($10^6$ kayıt) | ~20 | ~3 |
| Uygun ortam | Bellek | Disk, ağ, blok tabanlı depolama |
| Aralık sorgusu | Ağaç gezinmesi | B+ ağacında yaprak zinciri |
| Düğüm içi arama | Yok | İkili arama veya doğrusal tarama |

Son satır bir ayrıntıyı açığa çıkarır: B-ağacında toplam **karşılaştırma** sayısı, ikili
ağaçtan az değildir. Anahtarlar düğüm içinde de aranır ve toplamda benzer sayıda
karşılaştırma yapılır. Kazanılan şey karşılaştırma değil, **blok okuma** sayısıdır.

Bu, veri yapısı seçiminin donanım bağlamından ayrılamayacağını gösteren en net örnektir:
aynı algoritma, farklı bir bellek hiyerarşisinde farklı bir yapıyı doğru kılar.

#### Düğüm İçi Arama

Düğüm başına yüzlerce anahtar bulunduğunda, düğüm içinde doğru çocuğu seçmek de bir arama
problemine dönüşür. İki seçenek vardır ve seçim, önceki kursların gözlemleriyle
belirlenir.

**İkili arama**, karşılaştırma sayısını logaritmik yapar. **Doğrusal tarama** daha çok
karşılaştırma yapar ama anahtarları bitişik okur ve önbellek satırlarından tam olarak
yararlanır.

Düğüm bir bloğa sığdığına ve blok zaten bellekte olduğuna göre, iki yöntem arasındaki
fark küçüktür; gerçekleştirimler çoğu zaman ikisini birleştirir — küçük düğümlerde
doğrusal, büyük düğümlerde ikili arama.

Bu ayrıntı, kursun tekrarlayan dersini bir kez daha gösterir: karşılaştırma sayısı tek
başına bir ölçüt değildir; hangi belleğe kaç kez gidildiği de sayılmalıdır.

#### Yazma Yükü ve Dayanıklılık

Blok tabanlı depolamanın ikinci gerçeği, yazmanın okumadan pahalı olmasıdır. Bir düğümün
tek bir anahtarı değişse bile, bloğun tamamı yeniden yazılır.

Bu, iki tasarım kararını doğurur. Düğümlerin **yarıdan fazla dolu** tutulması, bölünme ve
birleştirme sıklığını azaltır. Yazmaların **toplu** yapılması ise aynı bloğa art arda
gelen değişikliklerin tek bir yazmada birleşmesini sağlar.

Kalıcılık gereksinimi de buradan çıkar: bir bölünme sırasında sistem durursa yapı tutarsız
kalabilir. Veritabanları bu riski, değişiklikleri önce bir günlüğe yazarak yönetir —
Bilgisayarlar Nasıl Çalışır kursundaki yazma öncesi günlük fikrinin veri yapısı
düzeyindeki karşılığıdır.

#### Kullanım Alanları

- **Veritabanı dizinleri.** Birincil ve ikincil dizinler B+ ağacı olarak tutulur.
- **Dosya sistemleri.** Dizin girdilerinin ve blok eşlemelerinin saklanması.
- **Anahtar–değer depoları.** Sıralı erişim gerektiren gerçekleştirimler.
- **Dosya biçimleri.** Büyük veri dosyalarına gömülü dizin blokları.

Bu yapıların ortak özelliği, bellek hiyerarşisinin hangi katmanına göre tasarlandıklarının
açıkça bilinmesidir; aynı ağaç, farklı bir katman için farklı parametrelerle kurulur.

Yazma ağırlıklı iş yüklerinde alternatif bir aile — günlük yapılı birleştirme ağaçları —
tercih edilebilir: yazmaları toplu hâle getirip sıralı diske yazarlar. İki ailenin
karşılaştırması veritabanları müfredatının konusudur.

#### Özet

- Kalıcı depolama blok düzeyinde okunur; maliyeti belirleyen, okunan blok sayısıdır.
- B-ağacında düğüm boyutu bloğa eşitlenir; dallanma çarpanı yüzler mertebesine çıkar.
- Yükseklik $\log_b n$ ile orantılıdır; bir milyon kayıt için üç düğüm ziyareti yeterlidir.
- Kurallar 2-3 ağacının genelleştirilmiş hâlidir: bölünme, terfi, ödünç alma ve
  birleştirme.
- B+ ağacında kayıtlar yalnızca yapraklarda tutulur ve yapraklar zincirlenir; aralık
  sorguları sıralı taramaya iner.
- Kazanç karşılaştırma sayısında değil, blok okuma sayısındadır.

#### Sonraki Adım

Buraya kadarki ağaçlar sıralamayı tam olarak korudu. Bazı problemlerde ise yalnızca **en
küçük** (veya en büyük) elemana hızlı erişim gerekir; tam sıralama gereksiz bir maliyettir.
Sonraki ders, bu gevşetilmiş koşulla çalışan yığın yapısını ve onun gerçeklediği öncelik
kuyruğunu ele alacak.

### Yığınlar

Source: https://academia.sh/tr/kurslar/veri-yapilari/yiginlar

Öncelik kuyruğu, yığın koşulu, dizi gösterimi, yukarı ve aşağı süzme, yığın kurmanın doğrusal maliyeti.

Kuyruklar dersinde bir soru açıkta bırakılmıştı: elemanların geliş sırasının değil
**önem sırasının** belirleyici olduğu durumlarda ne yapılır? Bir işletim sistemi hangi
süreci çalıştıracağına, bir yönlendirme algoritması hangi düğümü genişleteceğine öncelik
bakarak karar verir.

**Öncelik kuyruğu (priority queue)**, bu soruya yanıt veren soyut veri tipidir: elemanlar
eklenir, çıkarıldığında **en öncelikli** olan gelir.

#### Tam Sıralama Gerekmez

Öncelik kuyruğu sıralı bir yapıyla gerçeklenebilir — her eklemede sıraya sokulur, en
baştaki çıkarılır. Ancak bu, gereğinden fazla iş yapar: kuyruk yalnızca **bir sonraki**
elemanı bilmek zorundadır; geri kalanının tam sırası önemsizdir.

**Yığın (heap)**, tam sıralama ile hiç sıralamamak arasındaki dengeyi kurar. Koşulu
şudur:

> Her düğümün değeri, çocuklarının değerlerinden küçük veya eşittir (en küçük yığın).

Bu **kısmi** bir sıralamadır. Kardeşler arasında hiçbir ilişki yoktur; yalnızca ebeveyn–
çocuk ekseninde düzen korunur. Kökün en küçük eleman olması bu koşulun doğrudan sonucudur.

En büyük yığın, koşulun tersidir ve kökte en büyük elemanı tutar.

#### Tam Ağaç ve Dizi Gösterimi

Yığın her zaman **tam ikili ağaçtır**: seviyeler soldan sağa doldurulur, boşluk yalnızca
son seviyenin sağ ucundadır. Bu biçim güvencesi, ikili ağaçlar dersindeki dizi
gösterimini uygulanabilir kılar:

$$
\text{sol}(i) = 2i+1, \qquad \text{sağ}(i) = 2i+2, \qquad \text{ebeveyn}(i) = \left\lfloor \tfrac{i-1}{2} \right\rfloor
$$

Yığının işaretçi tutmamasının iki sonucu vardır: bellek ek yükü yoktur ve elemanlar
bitişik durduğu için önbellek davranışı iyidir. Ağaç yapısı yalnızca kavramsaldır; veri
düz bir dizidir.

#### İki Süzme İşlemi

Yığın koşulu, iki yerel onarım işlemiyle korunur.

**Yukarı süzme (sift-up)**, eklemede kullanılır. Yeni eleman dizinin sonuna — yani ağacın
son yaprağına — konur ve koşul sağlanana kadar ebeveyniyle yer değiştirerek yukarı
taşınır.

**Aşağı süzme (sift-down)**, çıkarmada kullanılır. Kök çıkarıldığında yerine son eleman
konur ve koşul sağlanana kadar küçük çocuğuyla yer değiştirerek aşağı iner.

Her iki işlem de kökten yaprağa giden bir yol boyunca ilerler; maliyetleri $O(\log n)$'dir.

```python
class Yigin:
    """En küçük yığın: kök her zaman en küçük elemandır."""

    def __init__(self) -> None:
        self._veri: list[int] = []

    def __len__(self) -> int:
        return len(self._veri)

    def ekle(self, deger: int) -> None:
        self._veri.append(deger)
        self._yukari_suz(len(self._veri) - 1)

    def en_kucuk(self) -> int:
        if not self._veri:
            raise IndexError("yığın boş")
        return self._veri[0]

    def cikar(self) -> int:
        if not self._veri:
            raise IndexError("yığın boş")
        en_kucuk = self._veri[0]
        son = self._veri.pop()
        if self._veri:
            self._veri[0] = son            # son eleman köke taşınır
            self._asagi_suz(0)
        return en_kucuk

    def _yukari_suz(self, i: int) -> None:
        while i > 0:
            ebeveyn = (i - 1) // 2
            if self._veri[i] >= self._veri[ebeveyn]:
                break                      # koşul sağlandı
            self._veri[i], self._veri[ebeveyn] = self._veri[ebeveyn], self._veri[i]
            i = ebeveyn

    def _asagi_suz(self, i: int) -> None:
        n = len(self._veri)
        while True:
            en_kucuk, sol, sag = i, 2 * i + 1, 2 * i + 2
            if sol < n and self._veri[sol] < self._veri[en_kucuk]:
                en_kucuk = sol
            if sag < n and self._veri[sag] < self._veri[en_kucuk]:
                en_kucuk = sag
            if en_kucuk == i:
                break
            self._veri[i], self._veri[en_kucuk] = self._veri[en_kucuk], self._veri[i]
            i = en_kucuk


y = Yigin()
for olcum in (25, 7, 30, 12, 18, 3):
    y.ekle(olcum)

print(y.en_kucuk(), len(y))        # 3 6
print([y.cikar() for _ in range(6)])   # [3, 7, 12, 18, 25, 30]
```

Elemanların çıkarma sırasında sıralı gelmesi, yığının sıralı olduğu anlamına gelmez:
dizinin kendisi hiçbir zaman tümüyle sıralı değildir. Sıralı çıktı, her çıkarmanın en
küçüğü seçmesinden doğar.

#### Yığın Kurmanın Maliyeti

Elde bir dizi varsa ve tümü yığın hâline getirilecekse, her elemanı tek tek eklemek
$O(n \log n)$ sürer. Daha iyi bir yol vardır: dizideki **son iç düğümden** başlayarak
geriye doğru aşağı süzme uygulamak.

```python
def yigin_kur(veri: list[int]) -> Yigin:
    """Var olan diziyi yerinde yığına çevirir: O(n)."""
    y = Yigin()
    y._veri = list(veri)
    for i in range(len(veri) // 2 - 1, -1, -1):     # son iç düğümden köke
        y._asagi_suz(i)
    return y


y = yigin_kur([25, 7, 30, 12, 18, 3])
print(y.en_kucuk())                 # 3
print([y.cikar() for _ in range(6)])    # [3, 7, 12, 18, 25, 30]
```

Bu yöntemin maliyeti sezginin aksine $O(n \log n)$ değil, $O(n)$'dir. Gerekçesi düğüm
dağılımındadır: düğümlerin yarısı yapraktır ve hiç süzülmez; dörtte biri bir seviye,
sekizde biri iki seviye süzülür. Toplam, her düğümün en yüksek maliyeti ödediği
varsayımından belirgin biçimde küçük çıkar. Kesin çözümleme **Algoritmalar** kursuna
aittir.

#### Kullanım Alanları

**Öncelikli zamanlama.** İşletim sistemi süreç seçimi, olay güdümlü simülasyonlarda bir
sonraki olayın seçilmesi.

**Çizge algoritmaları.** En kısa yol ve minimum kapsayan ağaç algoritmaları, sıradaki en
ucuz kenarı yığından çeker. Bu algoritmalar **Algoritmalar** kursunda ele alınır.

**En büyük k eleman.** Milyonlarca değer arasından en büyük yüzü bulmak için tümünü
sıralamak gerekmez: yüz elemanlık bir yığın tutulur, her yeni değer kökle karşılaştırılır.
Bellek $O(k)$, maliyet $O(n \log k)$ olur.

**Akan ortanca.** Programlama Temelleri kursunda tanıtılan iki yığın kalıbı: küçük yarıyı
en büyük yığında, büyük yarıyı en küçük yığında tutmak, ortancayı sabit zamanda verir.

**Sıralama.** Tüm elemanları yığına koyup tek tek çıkarmak $O(n \log n)$ bir sıralama
algoritmasıdır; yığın sıralaması olarak bilinir.

Bir ayrıntı, öncelik kuyruğu kullanan algoritmalarda önem kazanır: yığında bulunan bir
elemanın önceliği sonradan değişirse, yapı kendiliğinden düzelmez. Bu durum için ya
öncelik güncelleme işlemi ayrıca gerçeklenir ya da eski kayıt geçersiz sayılıp yenisi
eklenir; ikinci yol daha basittir ve yığında geçersiz kayıtlar biriktirir.

#### Maliyet Tablosu

| İşlem | Yığın | Sıralı dizi | Sırasız dizi |
|---|---|---|---|
| En küçüğü görme | $O(1)$ | $O(1)$ | $O(n)$ |
| Ekleme | $O(\log n)$ | $O(n)$ | $O(1)$ |
| En küçüğü çıkarma | $O(\log n)$ | $O(1)$* | $O(n)$ |
| Yığın kurma | $O(n)$ | $O(n \log n)$ | $O(1)$ |
| Arama (rastgele eleman) | $O(n)$ | $O(\log n)$ | $O(n)$ |

\* Baştan silme kaydırma gerektiriyorsa $O(n)$.

Son satır, yığının sınırıdır: kök dışındaki bir elemanı aramak için tüm yapı gezilir.
Yığın, sıralama için değil **uç elemana erişim** için tasarlanmıştır.

#### Özet

- Öncelik kuyruğu, çıkarıldığında en öncelikli elemanı veren soyut tiptir.
- Yığın koşulu kısmi bir sıralamadır: ebeveyn çocuklarından küçüktür, kardeşler arasında
  ilişki yoktur.
- Yığın her zaman tam ikili ağaçtır ve diziyle gösterilir; işaretçi ek yükü yoktur.
- Ekleme yukarı süzme, çıkarma aşağı süzme ile koşulu onarır; ikisi de logaritmiktir.
- Var olan bir diziden yığın kurmak, tek tek eklemekten ucuzdur ve doğrusal zamanlıdır.
- Yığın, uç elemana erişim için tasarlanmıştır; rastgele eleman araması doğrusaldır.

#### Sonraki Adım

Buraya kadarki arama yapıları anahtarları bütün olarak karşılaştırdı. Anahtarlar dizgi
olduğunda farklı bir olanak doğar: ortak önekler bir kez saklanabilir ve karşılaştırma
karakter karakter yapılabilir. Sonraki ders bu fikri kuran sözcük ağaçlarını ele alacak.

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

Source: https://academia.sh/tr/kurslar/veri-yapilari/sozcuk-agaclari

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.

### Aralık ve Fenwick Ağaçları

Source: https://academia.sh/tr/kurslar/veri-yapilari/aralik-agaclari

Aralık sorgusu ile nokta güncellemesinin birlikte gerektiği durumlar, aralık ağacı ve Fenwick ağacı.

Bir ölçüm dizisinde şu iki işlem art arda yapılsın: belirli bir aralıktaki değerlerin
toplamını sor ve tek bir değeri güncelle. İkisi de sık yapılıyorsa, buraya kadarki
yapıların hiçbiri iyi bir yanıt vermez.

#### İki Uç Çözüm

**Ham dizi.** Güncelleme tek bir yazmadır: $O(1)$. Aralık toplamı ise aralıktaki tüm
elemanları gezer: $O(n)$.

**Ön ek toplamı dizisi.** Baştan itibaren biriken toplamlar önceden hesaplanırsa, herhangi
bir aralığın toplamı iki değerin farkıdır: $O(1)$. Buna karşılık tek bir değer
değiştiğinde, ondan sonraki tüm ön ek toplamları yeniden hesaplanmalıdır: $O(n)$.

```python
olcumler = [12, 18, 7, 25, 14, 30]

on_ek = [0] * (len(olcumler) + 1)
for i, deger in enumerate(olcumler):
    on_ek[i + 1] = on_ek[i] + deger

print(on_ek)                      # [0, 12, 30, 37, 62, 76, 106]
print(on_ek[4] - on_ek[1])        # 50   — 1..3 aralığı: 18 + 7 + 25
```

İki çözüm de bir işlemi sabit, diğerini doğrusal yapar. Her ikisi de sık yapılıyorsa
ikisi de yetersizdir; aranan, **her ikisini birden logaritmik** yapan bir yapıdır.

#### Aralık Ağacı

**Aralık ağacı (segment tree)**, diziyi ikili olarak böler: kök tüm diziyi, çocukları
yarılarını, onların çocukları çeyreklerini temsil eder. Her düğüm, kendi aralığının
özetini — burada toplamını — saklar.

```
                [0..5] = 106
             /                \
        [0..2] = 37        [3..5] = 69
        /      \            /       \
   [0..1]=30  [2..2]=7  [3..4]=39  [5..5]=30
    /    \                 /   \
 [0]=12 [1]=18         [3]=25 [4]=14
```

Yukarıdaki şekil ağacın **kavramsal** biçimidir. Aşağıdaki gerçekleştirim ağacı düz bir
`2n` dizide tutar ve `n` bir ikinin kuvveti olmadığında iç düğümler bu yarılarla birebir
örtüşmez: altı elemanlı dizide kökün çocukları `[0..2]` ile `[3..5]` değil, `[2..5]` ile
`[0..1]` olur. Sorguların yanıtı değişmez, yalnız düğümlerin kapsadığı aralıklar kayar.

**Sorgu**, istenen aralığı ağaçtaki düğümlerin birleşimi olarak yazar. Herhangi bir
aralık, en fazla $O(\log n)$ düğümle kaplanabilir; bu, sorgu maliyetinin kaynağıdır.

**Güncelleme**, ilgili yaprağı değiştirir ve kökten yaprağa giden yol üzerindeki tüm
özetleri yeniden hesaplar — yine $O(\log n)$.

```python
class AralikAgaci:
    """Toplam sorgusu ve nokta güncellemesi; ikisi de O(log n)."""

    def __init__(self, veri: list[int]) -> None:
        self._n = len(veri)
        self._agac = [0] * (2 * self._n)         # yapraklar ikinci yarıda
        for i, deger in enumerate(veri):
            self._agac[self._n + i] = deger
        for i in range(self._n - 1, 0, -1):      # iç düğümler alttan yukarı
            self._agac[i] = self._agac[2 * i] + self._agac[2 * i + 1]

    def guncelle(self, dizin: int, deger: int) -> None:
        i = self._n + dizin
        self._agac[i] = deger
        i //= 2
        while i >= 1:                            # köke kadar özetleri tazele
            self._agac[i] = self._agac[2 * i] + self._agac[2 * i + 1]
            i //= 2

    def toplam(self, sol: int, sag: int) -> int:
        """[sol, sag) yarı açık aralığının toplamı."""
        sonuc = 0
        l, r = self._n + sol, self._n + sag
        while l < r:
            if l % 2 == 1:                       # sol sınır sağ çocuksa al
                sonuc += self._agac[l]
                l += 1
            if r % 2 == 1:                       # sağ sınır sağ çocuksa al
                r -= 1
                sonuc += self._agac[r]
            l //= 2
            r //= 2
        return sonuc


agac = AralikAgaci([12, 18, 7, 25, 14, 30])
print(agac.toplam(0, 6))          # 106  — tüm dizi
print(agac.toplam(1, 4))          # 50   — 18 + 7 + 25
agac.guncelle(2, 100)             # 7 yerine 100
print(agac.toplam(1, 4))          # 143
print(agac.toplam(0, 6))          # 199
```

Yapının genelliği dikkat çekicidir: birleştirme işlemi toplama yerine en büyük, en küçük,
en büyük ortak bölen veya birleşme özelliği olan herhangi bir işlem olabilir. Yalnızca
düğümlerde saklanan özet ile birleştirme satırı değişir.

#### Fenwick Ağacı

**Fenwick ağacı** (ikili dizinli ağaç), yalnızca ön ek toplamlarıyla ilgilenen daha
kompakt bir yapıdır. Aynı işi $n$ gözlük tek bir diziyle yapar; aralık ağacının yarısı
kadar bellek kullanır ve kodu belirgin biçimde kısadır.

Fikri, her dizinin belirli bir aralığın toplamını saklamasıdır ve bu aralığın uzunluğu,
dizinin ikilik gösterimindeki **en düşük kurulu bitle** belirlenir. Bilgisayarlar Nasıl
Çalışır kursundaki `x & -x` deyimi burada doğrudan kullanılır.

```python
class FenwickAgaci:
    """Ön ek toplamı ve nokta güncellemesi; O(log n)."""

    def __init__(self, boyut: int) -> None:
        self._agac = [0] * (boyut + 1)           # 1 tabanlı dizin

    def ekle(self, dizin: int, artis: int) -> None:
        i = dizin + 1
        while i < len(self._agac):
            self._agac[i] += artis
            i += i & -i                          # bir sonraki sorumlu dizin

    def on_ek(self, dizin: int) -> int:
        """[0, dizin) aralığının toplamı."""
        sonuc, i = 0, dizin
        while i > 0:
            sonuc += self._agac[i]
            i -= i & -i                          # en düşük kurulu biti düşür
        return sonuc

    def aralik(self, sol: int, sag: int) -> int:
        return self.on_ek(sag) - self.on_ek(sol)


f = FenwickAgaci(6)
for i, deger in enumerate([12, 18, 7, 25, 14, 30]):
    f.ekle(i, deger)

print(f.on_ek(6))            # 106
print(f.aralik(1, 4))        # 50
f.ekle(2, 93)                # 7 + 93 = 100
print(f.aralik(1, 4))        # 143
```

Fenwick ağacı güncellemeyi **artış** olarak alır; bir değeri doğrudan belirlemek için
eski değerle farkı eklenir. Bu, yapının ön ek toplamı odaklı tasarımının bir sonucudur.

#### Hangi Yapı Ne Zaman

| Yapı | Aralık sorgusu | Nokta güncellemesi | Bellek | Genellik |
|---|---|---|---|---|
| Ham dizi | $O(n)$ | $O(1)$ | $n$ | Tam |
| Ön ek toplamı | $O(1)$ | $O(n)$ | $n$ | Yalnız toplama |
| Aralık ağacı | $O(\log n)$ | $O(\log n)$ | $2n$ | Birleşmeli her işlem |
| Fenwick ağacı | $O(\log n)$ | $O(\log n)$ | $n$ | Toplama ve tersi olan işlemler |

Seçim ölçütleri:

- Veri değişmiyorsa **ön ek toplamı** en iyisidir; ek yapı gereksizdir.
- Yalnızca toplam sorgulanıyorsa **Fenwick** yeterlidir: daha az bellek, daha kısa kod.
- En küçük/en büyük gibi tersi olmayan işlemler veya aralık güncellemesi gerekiyorsa
  **aralık ağacı** kullanılır.

Aralık ağacının bir uzantısı, aralık güncellemelerini de logaritmik yapar: güncelleme
hemen alta yayılmaz, düğümde bir "bekleyen değişiklik" olarak tutulur ve ancak o alt
ağaca inildiğinde uygulanır. Bu teknik, ileri algoritma konularında ele alınır.

#### Kullanım Alanları

Aralık sorguları, zaman serisi ve sıralı veri üzerinde çalışan sistemlerin ortak
ihtiyacıdır: bir zaman aralığındaki ölçümlerin toplamı veya en büyüğü, sıralamada belirli
bir aralıktaki kayıt sayısı, oyun dünyasında bir bölgedeki nesnelerin sayımı.

Veri değişmiyorsa aynı sorular önceden hesaplanmış özetlerle yanıtlanır; bu yapıların
varlık nedeni, verinin **değişmeye devam etmesidir**.

#### Özet

- Ham dizi güncellemeyi, ön ek toplamı sorguyu sabit yapar; ikisi birden sık
  gerekiyorsa ikisi de yetersizdir.
- Aralık ağacı diziyi ikili böler ve her düğümde alt aralığın özetini saklar; sorgu ve
  güncelleme $O(\log n)$'dir.
- Herhangi bir aralık, en fazla logaritmik sayıda düğümle kaplanır.
- Birleştirme işlemi değiştirilerek aynı yapı en küçük, en büyük veya başka birleşmeli
  işlemler için kullanılır.
- Fenwick ağacı yalnızca ön ek toplamlarıyla ilgilenir; yarı bellek ve daha kısa kodla
  aynı maliyeti verir.
- Yapıların varlık nedeni verinin değişmesidir; sabit veride önceden hesaplanmış özetler
  yeterlidir.

#### Sonraki Adım

Aralık sorguları tek boyutluydu: dizinler bir çizgi üzerinde. Konum verisi iki veya daha
çok boyutluysa — harita üzerindeki noktalar, öznitelik uzayındaki kayıtlar — bölme fikri
nasıl genişletilir? Sonraki ders, bu konunun son yapısı olan çok boyutlu ağaçları ele
alacak.

### Çok Boyutlu Ağaçlar

Source: https://academia.sh/tr/kurslar/veri-yapilari/cok-boyutlu-agaclar

Uzamsal sorgular, k-d ağacında dönüşümlü bölme, en yakın komşu araması, budama ve boyut laneti.

Buraya kadarki arama yapıları tek bir eksende sıralıyordu: her düğümde "küçük mü büyük
mü" sorusu tek bir değere göre yanıtlanıyordu.

Bazı veriler tek eksene sığmaz. Harita üzerindeki bir nokta iki koordinat, bir sensör
kaydı sıcaklık ve nem, bir belge gömmesi yüzlerce sayı taşır. Bu verilerde sorulan sorular
da farklıdır: **"şu noktaya en yakın kayıt hangisi"** veya **"şu dikdörtgen içindeki tüm
noktalar"**.

#### Tek Boyutlu Yapılar Neden Yetmez

Noktalar yalnızca birinci koordinata göre sıralanırsa, o eksende yakın olan noktalar
bulunabilir. Ancak birinci koordinatı yakın iki nokta, ikinci koordinatta çok uzak
olabilir; sıralama, gerçek yakınlık hakkında bilgi vermez.

İki ayrı dizin — biri her eksen için — tutulsa bile sonuç değişmez: her dizin bir eksende
aday listesi verir, ama kesişimleri hesaplamak tüm adayları gezmeyi gerektirir.

Gereken şey, uzayı **tüm boyutları birlikte** dikkate alarak bölen bir yapıdır.

#### k-d Ağacı

**k-d ağacı**, ikili arama ağacının çok boyutlu genellemesidir. Tek farkı, her düğümde
karşılaştırmanın hangi boyuta göre yapıldığıdır: bölme boyutu, **derinliğe göre
dönüşümlü** seçilir.

İki boyutlu bir kümede kök birinci koordinata, çocukları ikinci koordinata, torunları
yine birinciye göre böler. Her düğüm, uzayı bir doğruyla ikiye ayırır; alt ağaçlar bu
yarı düzlemlere karşılık gelir.

```python
class KdDugum:
    def __init__(self, nokta: tuple[float, ...], eksen: int) -> None:
        self.nokta = nokta
        self.eksen = eksen
        self.sol: "KdDugum | None" = None
        self.sag: "KdDugum | None" = None


def kd_kur(noktalar: list[tuple[float, ...]], derinlik: int = 0) -> KdDugum | None:
    """Ortanca noktayı seçerek dengeli k-d ağacı kurar."""
    if not noktalar:
        return None
    boyut = len(noktalar[0])
    eksen = derinlik % boyut                       # dönüşümlü bölme
    sirali = sorted(noktalar, key=lambda p: p[eksen])
    orta = len(sirali) // 2
    dugum = KdDugum(sirali[orta], eksen)
    dugum.sol = kd_kur(sirali[:orta], derinlik + 1)
    dugum.sag = kd_kur(sirali[orta + 1:], derinlik + 1)
    return dugum


noktalar = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
kok = kd_kur(noktalar)
print(kok.nokta, kok.eksen)                        # (7, 2) 0
print(kok.sol.nokta, kok.sag.nokta)                # (5, 4) (9, 6)
```

Kurulumda ortanca nokta seçilir; böylece iki alt ağaç eşit büyüklükte olur ve yükseklik
$O(\log n)$'de kalır. Ortanca seçimi sıralamayla yapıldığında kurulum
$O(n \log^2 n)$ sürer; doğrusal zamanlı seçim algoritmasıyla $O(n \log n)$'e iner. Seçim
algoritmaları **Algoritmalar** kursunun konusudur.

#### En Yakın Komşu Araması

Aramanın çekirdek fikri budamadır: bir alt ağaç, o ana kadar bulunan en iyi adaydan
kesinlikle daha uzaksa hiç gezilmez.

Adımlar şunlardır:

1. Sorgu noktasının hangi tarafa düştüğüne bakarak ağaçta aşağı in; ulaşılan yaprak ilk
   adaydır.
2. Geri dönerken her düğümde, düğümün kendisinin daha yakın olup olmadığını sına.
3. Bölme doğrusuna olan uzaklık, şu ana kadarki en iyi uzaklıktan **küçükse** öbür alt
   ağaç da gezilir; büyükse o alt ağacın tamamı elenir.

Üçüncü adım, verimliliğin tamamını sağlar: bölme doğrusuna uzaklık, o taraftaki herhangi
bir noktaya olan uzaklığın alt sınırıdır.

```python
def uzaklik2(a: tuple[float, ...], b: tuple[float, ...]) -> float:
    """Karesel uzaklık; karekök almak sıralamayı değiştirmez."""
    return sum((x - y) ** 2 for x, y in zip(a, b))


def en_yakin(dugum: KdDugum | None, hedef: tuple[float, ...],
             en_iyi=None, sayac=None):
    """(en yakın nokta, ziyaret edilen düğüm sayısı) döndürür."""
    sayac = {"n": 0} if sayac is None else sayac
    if dugum is None:
        return en_iyi, sayac["n"]

    sayac["n"] += 1
    if en_iyi is None or uzaklik2(dugum.nokta, hedef) < uzaklik2(en_iyi, hedef):
        en_iyi = dugum.nokta

    eksen = dugum.eksen
    fark = hedef[eksen] - dugum.nokta[eksen]
    yakin, uzak = (dugum.sol, dugum.sag) if fark < 0 else (dugum.sag, dugum.sol)

    en_iyi, _ = en_yakin(yakin, hedef, en_iyi, sayac)          # önce yakın taraf
    if fark ** 2 < uzaklik2(en_iyi, hedef):                    # budama sınaması
        en_iyi, _ = en_yakin(uzak, hedef, en_iyi, sayac)
    return en_iyi, sayac["n"]


print(en_yakin(kok, (9, 2)))      # ((8, 1), 3)
print(en_yakin(kok, (4, 6)))      # ((4, 7), 3)
```

İlk sorguda altı noktalı ağacın yalnızca üç düğümü ziyaret edilmiştir; üç düğüm budanarak
elenmiştir. Karesel uzaklık kullanılması, karekök hesabından kaçınmak içindir — sıralama
değişmediği sürece gereksiz bir işlemdir.

#### Aralık Sorgusu

Dikdörtgen (veya çok boyutlu kutu) sorgusu aynı budama mantığını kullanır: düğümün bölme
doğrusu sorgu kutusunun tümüyle bir tarafında kalıyorsa, öbür alt ağaç hiç gezilmez.

Bu, aralık ağaçlarındaki fikrin uzamsal karşılığıdır: sorgu, ağaçtaki düğümlerin bir alt
kümesiyle kaplanır.

#### Boyut Laneti

k-d ağacının vaadi düşük boyutlarda geçerlidir. Boyut sayısı arttıkça budama işe
yaramaz hâle gelir.

Nedeni sezgiseldir: yüksek boyutlu bir uzayda, iki nokta arasındaki uzaklıklar birbirine
yaklaşır ve bölme doğrusuna olan uzaklık neredeyse her zaman en iyi adaydan küçük çıkar.
Budama koşulu sağlanmaz, her iki alt ağaç da gezilir ve arama doğrusal taramaya döner.

Pratik ölçüt şudur: $n \gg 2^{k}$ olmalıdır ($k$ boyut sayısı). Yirmi boyut ve bin nokta
ile k-d ağacı, doğrusal taramadan hızlı değildir — üstelik ek bellek kullanır.

Bu, yalnızca bir veri yapısı ayrıntısı değildir; yüksek boyutlu verinin genel bir
özelliğidir ve makine öğrenmesinde uzaklık temelli yöntemlerin sınırını da belirler.

Ekleme ve silme de mümkündür, ancak k-d ağacı bu işlemlerde dengesini koruyamaz: dönme
gibi bir onarım işlemi tanımlı değildir. Veri sık değişiyorsa ağaç belirli aralıklarla
yeniden kurulur.

#### Diğer Uzamsal Yapılar

| Yapı | Bölme biçimi | Uygun kullanım |
|---|---|---|
| Izgara | Sabit boyutlu hücreler | Düzgün dağılmış veri, sabit yarıçaplı sorgular |
| Dörtlü ağaç | Her düğüm alanı dörde böler | İki boyutlu, dengesiz yoğunluk |
| k-d ağacı | Dönüşümlü tek eksen | Orta boyut, nokta verisi |
| R-ağacı | Kapsayan dikdörtgenler | Nokta değil alan verisi; disk tabanlı dizinler |

Yüksek boyutlu verilerde — belge ve görüntü gömmeleri gibi — kesin en yakın komşu
aramasından vazgeçilir ve **yaklaşık** yöntemler kullanılır. Bu yöntemler, doğrusal
yapılar konusundaki atlama listesi gibi olasılıksal güvenceler verir ve vektör
veritabanlarının temelini oluşturur; yapay zekâ mühendisliği müfredatında ele alınırlar.

#### Özet

- Uzamsal sorgular tek boyutlu sıralamayla yanıtlanamaz; yakınlık tüm boyutlara birlikte
  bağlıdır.
- k-d ağacı, bölme boyutunu derinliğe göre dönüşümlü seçer; her düğüm uzayı ikiye ayırır.
- Ortanca nokta seçimi yüksekliği logaritmik tutar.
- En yakın komşu araması, bölme doğrusuna olan uzaklığı alt sınır olarak kullanıp alt
  ağaçları budar.
- Karesel uzaklık, karekök hesabından kaçınmak için kullanılır; sıralamayı değiştirmez.
- Boyut sayısı arttıkça budama etkisizleşir ve arama doğrusal taramaya döner; pratik
  ölçüt $n \gg 2^k$'dir.

#### Sonraki Adım

Ağaçlar, döngüsüz ve tek ebeveynli yapılardı. Bu kısıt kaldırıldığında — bir düğümün
birden çok "üstü" olabildiğinde ve döngülere izin verildiğinde — elde edilen yapı çok
daha geneldir ve ağ, harita, bağımlılık ilişkisi gibi problemlerin doğal modelidir.
Kursun son konusu çizgeleri ele alacak.

## Çizgeler

Çizge kavramı, gösterim seçenekleri, enine ve derine arama ile topolojik sıralama.

### Çizge Kavramı

Source: https://academia.sh/tr/kurslar/veri-yapilari/cizge-kavrami

Düğüm ve kenar tanımı, yönlü ve yönsüz çizgeler, ağırlık, derece, yol ve döngü kavramları.

Ağaçlar iki kısıt taşıyordu: döngü yoktu ve her düğümün tek bir üstü vardı. Bu kısıtlar
kaldırıldığında elde edilen yapı, ilişkileri modellemenin en genel biçimidir.

**Çizge (graph)**, düğümler ve onları birleştiren kenarlardan oluşur. Bu kadar basit bir
tanımın bu kadar geniş bir uygulama alanı olması, ilişkinin kendisinin temel bir kavram
olmasındandır: yollar arasındaki bağlantılar, kişiler arasındaki tanışıklık, görevler
arasındaki bağımlılık, sayfalar arasındaki bağlantılar — hepsi aynı yapıdır.

#### Temel Terimler

Bir çizge $G = (V, E)$ olarak yazılır: $V$ düğüm kümesi, $E$ kenar kümesidir.

| Terim | Anlamı |
|---|---|
| Düğüm (vertex) | Yapının birimi; modellenen varlık |
| Kenar (edge) | İki düğüm arasındaki ilişki |
| Komşu | Aralarında kenar bulunan düğümler |
| Derece | Bir düğüme bağlı kenar sayısı |
| Yol | Kenarlar üzerinden ilerleyen düğüm dizisi |
| Döngü | Başladığı düğüme dönen yol |
| Bağlı bileşen | Kendi içinde birbirine ulaşabilen düğüm kümesi |

Bir düğümden diğerine **ulaşılabiliyorsa** aralarında bir yol vardır. Tüm düğüm
çiftlerinin birbirine ulaşabildiği çizgeye **bağlı** denir; ulaşamayanlar varsa çizge
birden çok **bileşene** ayrılmıştır.

#### Yönlü ve Yönsüz

**Yönsüz çizgede** kenar iki yönlüdür: `a` ile `b` arasında kenar varsa, `a`'dan `b`'ye
ve `b`'den `a`'ya gidilebilir. Karşılıklı ilişkileri modeller — iki şehir arasındaki yol,
iki kişi arasındaki arkadaşlık.

**Yönlü çizgede** kenarın bir yönü vardır. Tek yönlü ilişkileri modeller — bir sayfadan
diğerine verilen bağlantı, bir görevin diğerine bağımlılığı, tek yönlü bir sokak.

Yönlü çizgede derece ikiye ayrılır: **giriş derecesi** (düğüme gelen kenar sayısı) ve
**çıkış derecesi** (düğümden çıkan). Bu ayrım, topolojik sıralama dersinde belirleyici
olacaktır.

Yönlü çizgelerde döngü kavramı da özelleşir. **Yönlü çevrimsiz çizge**, hiçbir yönlü
döngü içermeyen çizgedir ve bağımlılık ilişkilerinin doğal modelidir: bir görev kendisine
dolaylı olarak da bağımlı olamaz.

#### Ağırlık

Kenarlara sayısal bir değer — **ağırlık** — atanabilir. Ağırlık, ilişkinin maliyetini
veya gücünü taşır: iki şehir arasındaki uzaklık, bir bağlantının gecikmesi, bir işlemin
süresi.

Ağırlıksız çizgede "en kısa yol", en az kenar kullanan yoldur. Ağırlıklı çizgede ise
ağırlık toplamı en küçük olan yoldur ve bu iki yol farklı olabilir: az sayıda uzun kenar
mı, çok sayıda kısa kenar mı sorusu, ancak ağırlıklara bakılarak yanıtlanır.

#### Ağaçlar Çizgelerin Özel Hâlidir

Önceki konunun tanımı burada yerine oturur: **ağaç, döngüsüz ve bağlı bir yönsüz
çizgedir.** $n$ düğümlü ağacın $n-1$ kenarı olması, bu tanımın doğrudan sonucuydu.

İlişki üç adımda kurulur:

- Çizgeden döngüler çıkarılırsa **orman** elde edilir.
- Orman bağlıysa **ağaç** olur.
- Ağaçta bir düğüm kök seçilirse **köklü ağaç** olur.

Bu, önceki konudaki tüm yapıların çizgelerin özel hâli olduğu anlamına gelir. Tersi
doğru değildir: çizgeler ağaçların yapamadığı şeyleri modeller — döngüler, çoklu yollar,
birden çok ebeveyn.

Ayrık kümeler dersindeki "bağlı bileşen" sorusu da buraya bağlanır: kenarlar eklendikçe
hangi düğümlerin aynı bileşende olduğu, orada birleştir–bul ile izleniyordu.

#### Özel Çizge Aileleri

| Aile | Tanım | Örnek kullanım |
|---|---|---|
| Yönlü çevrimsiz çizge | Yönlü, döngüsüz | Görev bağımlılıkları, derleme sırası |
| İki parçalı çizge | Düğümler iki gruba ayrılır, kenarlar yalnız gruplar arası | Eşleştirme problemleri |
| Tam çizge | Her düğüm çifti arasında kenar var | En kötü durum çözümlemeleri |
| Seyrek / yoğun çizge | Kenar sayısı düğüm sayısına yakın / karesine yakın | Gösterim seçimini belirler |

Son satır, sonraki dersin konusudur: kenar sayısının düğüm sayısına oranı, hangi
gösterimin uygun olduğunu doğrudan belirler.

Kenar sayısı için sınırlar da bu ayrımdan çıkar. Yönsüz ve basit bir çizgede en fazla
kenar sayısı:

$$
\lvert E \rvert \leq \frac{\lvert V \rvert (\lvert V \rvert - 1)}{2}
$$

Yani kenar sayısı, düğüm sayısının karesiyle sınırlıdır. Gerçek çizgelerin çoğu bu
sınırın çok altındadır — bir yol ağında her şehir yalnızca birkaç komşuya bağlıdır. Bu
gözlem, gösterim seçiminin pratikte neden seyrek çizgelere göre yapıldığını açıklar.

#### Modelleme Örneği

Ölçüm istasyonları arasındaki bağlantılar bir çizgeyle modellensin: istasyonlar düğüm,
aralarındaki iletişim hatları kenar, hattın gecikmesi ağırlık olsun.

```python
# Yönsüz, ağırlıklı çizge: her kenar bir kez yazılır.
kenarlar = [
    ("kuzey", "merkez", 4),
    ("guney", "merkez", 2),
    ("dogu",  "merkez", 7),
    ("bati",  "kuzey",  3),
    ("bati",  "guney",  5),
]

dugumler = {d for kenar in kenarlar for d in kenar[:2]}
print(sorted(dugumler))        # ['bati', 'dogu', 'guney', 'kuzey', 'merkez']
print(len(dugumler), len(kenarlar))     # 5 5

derece: dict[str, int] = {d: 0 for d in dugumler}
for a, b, _ in kenarlar:
    derece[a] += 1
    derece[b] += 1

print(sorted(derece.items()))
# [('bati', 2), ('dogu', 1), ('guney', 2), ('kuzey', 2), ('merkez', 3)]
print(sum(derece.values()), 2 * len(kenarlar))    # 10 10
```

Son satır, çizge kuramının en temel özdeşliğini gösterir: **derecelerin toplamı, kenar
sayısının iki katıdır.** Her kenar iki düğümün derecesine birer katkı yaptığı için bu
her yönsüz çizgede geçerlidir. Doğrudan bir sonucu, tek dereceli düğüm sayısının her
zaman çift olmasıdır.

Çoklu kenar ve ilmek — aynı düğüm çifti arasında birden çok kenar, ya da bir düğümden
kendisine giden kenar — bazı modellerde anlamlıdır. Bunlara izin veren çizgelere çoklu
çizge denir; bu kurstaki tanım, izin vermeyen **basit çizgedir**.

#### Çizgelerle Sorulan Sorular

Yapının kendisi kadar, üzerinde sorulan sorular da standarttır:

- **Ulaşılabilirlik:** İki düğüm arasında yol var mı?
- **En kısa yol:** Varsa en ucuzu hangisi?
- **Bağlı bileşenler:** Çizge kaç parçaya ayrılmış?
- **Döngü tespiti:** Yapıda döngü var mı?
- **Sıralama:** Bağımlılıklara uygun bir yürütme sırası var mı?
- **Kapsama:** Tüm düğümlere en az maliyetle ulaşan kenar kümesi hangisi?

Soruların çoğu, çizgenin yönlü olup olmadığına ve ağırlık taşıyıp taşımadığına göre
farklı algoritmalar gerektirir. Bu kursun kalan üç dersi ilk dördünü yanıtlayan gezinme
yöntemlerini kurar; en kısa yol
ve kapsama problemleri, ağırlıkların devreye girdiği algoritmalarla birlikte
**Algoritmalar** kursunda ele alınır.

#### Özet

- Çizge, düğümler ve kenarlardan oluşan en genel ilişki modelidir.
- Yönsüz kenar karşılıklı, yönlü kenar tek yönlü ilişkiyi gösterir; yönlü çizgede giriş
  ve çıkış dereceleri ayrılır.
- Ağırlık, ilişkinin maliyetini taşır ve "en kısa yol" tanımını değiştirir.
- Ağaç, döngüsüz ve bağlı bir çizgedir; ormanlar ve köklü ağaçlar bu tanımın
  özelleşmiş hâlleridir.
- Yönlü çevrimsiz çizgeler bağımlılık ilişkilerinin doğal modelidir.
- Derecelerin toplamı kenar sayısının iki katıdır; kenar sayısı düğüm sayısının karesiyle
  sınırlıdır.

#### Sonraki Adım

Çizge kavramı tanımlandı, ancak bellekte nasıl tutulacağı belirtilmedi. Seçim önemsiz
değildir: aynı algoritma, gösterime göre farklı maliyetlerle çalışır. Sonraki ders iki
temel gösterimi ve seçimi belirleyen ölçütü ele alacak.

### Çizge Gösterimleri

Source: https://academia.sh/tr/kurslar/veri-yapilari/cizge-gosterimleri

Komşuluk matrisi ile komşuluk listesi, bellek ve işlem maliyetleri, seyreklik ölçütü ve kenar listesi.

Çizge kavramı soyuttur; kodda bir gösterime dönüşmesi gerekir. İki temel seçenek vardır ve
aralarındaki fark, bu kursun tekrarlayan temasının bir örneğidir: **aynı veri, farklı
yerleşim, farklı maliyet.**

Seçim, çizgenin kenar yoğunluğuna ve hangi işlemlerin sık yapılacağına bağlıdır. Bu iki
ölçüt bilinmeden yapılan seçim, algoritmanın maliyetini gereksiz yere bir mertebe
yukarı taşıyabilir.

#### Komşuluk Matrisi

**Komşuluk matrisi**, $\lvert V \rvert \times \lvert V \rvert$ boyutunda bir tablodur.
Satır $i$, sütun $j$ hücresi, $i$ ile $j$ arasında kenar olup olmadığını söyler; ağırlıklı
çizgede ağırlığı taşır.

```python
INF = float("inf")
dugumler = ["bati", "dogu", "guney", "kuzey", "merkez"]
dizin = {ad: i for i, ad in enumerate(dugumler)}
n = len(dugumler)

matris = [[INF] * n for _ in range(n)]
for i in range(n):
    matris[i][i] = 0

for a, b, agirlik in [("kuzey", "merkez", 4), ("guney", "merkez", 2),
                      ("dogu", "merkez", 7), ("bati", "kuzey", 3),
                      ("bati", "guney", 5)]:
    matris[dizin[a]][dizin[b]] = agirlik
    matris[dizin[b]][dizin[a]] = agirlik          # yönsüz: iki hücre birden

print(matris[dizin["bati"]][dizin["kuzey"]])      # 3    — kenar var
print(matris[dizin["bati"]][dizin["dogu"]])       # inf  — kenar yok
print(sum(1 for x in matris[dizin["merkez"]] if x not in (0, INF)))   # 3 — derece
```

**Üstünlüğü:** İki düğüm arasında kenar olup olmadığı tek bir okumayla, $O(1)$'de
yanıtlanır.

**Bedeli:** Bellek her zaman $O(\lvert V \rvert^2)$'dir — kenar sayısından bağımsız.
Ayrıca bir düğümün komşularını listelemek, o satırın tamamını taramayı gerektirir:
$O(\lvert V \rvert)$.

Yönsüz çizgede matris köşegene göre bakışımlıdır; yalnızca yarısını saklamak belleği
yarıya indirir ama mertebeyi değiştirmez.

#### Komşuluk Listesi

**Komşuluk listesi**, her düğüm için yalnızca komşularının listesini tutar.

```python
from collections import defaultdict

komsuluk: dict[str, list[tuple[str, int]]] = defaultdict(list)
for a, b, agirlik in [("kuzey", "merkez", 4), ("guney", "merkez", 2),
                      ("dogu", "merkez", 7), ("bati", "kuzey", 3),
                      ("bati", "guney", 5)]:
    komsuluk[a].append((b, agirlik))
    komsuluk[b].append((a, agirlik))              # yönsüz: iki yöne de eklenir

print(sorted(komsuluk["merkez"]))
# [('dogu', 7), ('guney', 2), ('kuzey', 4)]
print(len(komsuluk["bati"]))                      # 2   — derece doğrudan okunur
print(any(komsu == "dogu" for komsu, _ in komsuluk["bati"]))   # False
```

**Üstünlüğü:** Bellek $O(\lvert V \rvert + \lvert E \rvert)$'dir; yalnızca var olan
kenarlar saklanır. Bir düğümün komşularını gezmek, derecesi kadar sürer.

**Bedeli:** İki düğüm arasında kenar olup olmadığı, listenin taranmasıyla bulunur —
$O(\text{derece})$.

#### Seyreklik Belirleyicidir

Karar ölçütü, kenar sayısının düğüm sayısına oranıdır.

Bir çizge **yoğunsa** ($\lvert E \rvert \approx \lvert V \rvert^2$) matris hem bellek
açısından makuldür hem sabit zamanlı kenar sorgusu verir.

Bir çizge **seyrekse** ($\lvert E \rvert \approx \lvert V \rvert$) matris neredeyse
tümüyle boş kalır. On bin düğümlü ve otuz bin kenarlı bir yol ağında matris yüz milyon
hücre ister; komşuluk listesi kırk bin girdiyle yetinir.

Gerçek çizgelerin büyük çoğunluğu seyrektir: her şehir birkaç şehre, her kişi birkaç yüz
kişiye, her sayfa birkaç düzine sayfaya bağlanır. Bu nedenle **varsayılan seçim komşuluk
listesidir**; matris, düğüm sayısı küçük veya çizge yoğun olduğunda tercih edilir.

#### Üçüncü Seçenek: Kenar Listesi

En yalın gösterim, kenarların düz bir listesidir — önceki dersteki `kenarlar` değişkeni
buydu.

Gezinme için elverişsizdir: bir düğümün komşularını bulmak tüm listeyi taramayı gerektirir.
Buna karşılık iki durumda doğru seçimdir: kenarların **tümü üzerinde** sırayla çalışan
algoritmalarda (kenarları ağırlığa göre sıralayıp işleyen minimum kapsayan ağaç
algoritması gibi) ve çizgenin **saklanması veya aktarılması** gerektiğinde.

#### Karşılaştırma

| İşlem | Komşuluk matrisi | Komşuluk listesi | Kenar listesi |
|---|---|---|---|
| Bellek | $O(V^2)$ | $O(V + E)$ | $O(E)$ |
| Kenar var mı | $O(1)$ | $O(\text{derece})$ | $O(E)$ |
| Komşuları gezme | $O(V)$ | $O(\text{derece})$ | $O(E)$ |
| Kenar ekleme | $O(1)$ | $O(1)$ | $O(1)$ |
| Kenar silme | $O(1)$ | $O(\text{derece})$ | $O(E)$ |
| Tüm kenarları gezme | $O(V^2)$ | $O(V + E)$ | $O(E)$ |

Tabloda $V$ ve $E$, düğüm ve kenar sayılarını gösterir; "derece" ilgili düğümün komşu
sayısıdır ve seyrek çizgelerde küçük bir sabit gibi davranır.

Dördüncü satırdaki eşitlik yanıltıcı olmasın: matriste kenar eklemek sabit zamanlıdır ama
matrisin kendisi baştan ayrılmıştır; düğüm eklemek matrisin yeniden oluşturulmasını
gerektirir. Komşuluk listesinde düğüm eklemek yalnızca yeni bir girdi açar.

#### Düğüm Kimlikleri

Yukarıdaki örneklerde düğümler dizgi adlarla anıldı. Büyük çizgelerde bu, iki maliyet
üretir: her erişimde dizgi karma hesabı yapılır ve her düğüm adı ayrı bir nesne olarak
bellekte durur.

Yaygın çözüm, düğümlere **tam sayı kimlikler** vermektir. Adlar bir kez taranır, her ada
sıralı bir numara atanır ve bundan sonra tüm yapılar dizin olarak bu numarayı kullanır.

```python
adlar = ["bati", "dogu", "guney", "kuzey", "merkez"]
kimlik = {ad: i for i, ad in enumerate(adlar)}

komsu_listesi: list[list[int]] = [[] for _ in adlar]
for a, b in [("kuzey", "merkez"), ("guney", "merkez"), ("dogu", "merkez"),
             ("bati", "kuzey"), ("bati", "guney")]:
    komsu_listesi[kimlik[a]].append(kimlik[b])
    komsu_listesi[kimlik[b]].append(kimlik[a])

print(komsu_listesi[kimlik["merkez"]])       # [3, 2, 1]
print([adlar[i] for i in komsu_listesi[kimlik["merkez"]]])
# ['kuzey', 'guney', 'dogu']
```

Kazanç yalnızca hız değildir: ziyaret işaretleri, uzaklıklar ve ebeveyn kayıtları da
eşleme yerine düz dizilerde tutulabilir. Bu, hem bellek hem önbellek davranışı açısından
belirgin bir iyileşmedir ve büyük çizgelerle çalışan kütüphanelerin standart yaklaşımıdır.

#### Gezinme Maliyetine Etkisi

Sonraki iki derste ele alınacak gezinme algoritmalarının maliyeti, doğrudan gösterime
bağlıdır. Her düğüm bir kez ziyaret edilir ve komşuları gezilir:

- Komşuluk listesiyle toplam maliyet $O(V + E)$'dir — her kenar iki kez incelenir.
- Komşuluk matrisiyle $O(V^2)$'dir — her düğüm için tüm satır taranır, kenar olmasa bile.

Seyrek bir çizgede bu, doğrusal ile karesel arasındaki farktır. Gösterim seçimi bu
nedenle bir ayrıntı değil, algoritmanın maliyet sınıfını belirleyen bir karardır.

Üçüncü bir seçenek olarak, iki gösterim birlikte de tutulabilir: gezinme için komşuluk
listesi, sık sorulan kenar sınamaları için ek bir küme. Bellek karşılığında iki işlemi de
ucuzlatan bu yaklaşım, aynı verinin birden çok yapıda tutulmasının meşru olduğu
durumlardan biridir — kursun ilk dersinden beri tekrarlanan ödünleşimin bilinçli
kullanımıdır.

#### Özet

- Komşuluk matrisi kenar sorgusunu sabit zamanlı yapar; belleği kenar sayısından bağımsız
  olarak $O(V^2)$'dir.
- Komşuluk listesi yalnızca var olan kenarları saklar; bellek $O(V + E)$, komşu gezinmesi
  derece kadardır.
- Seyrek çizgelerde liste, yoğun çizgelerde matris uygundur; gerçek çizgelerin çoğu
  seyrektir.
- Kenar listesi gezinme için elverişsizdir ama tüm kenarlar üzerinde çalışan
  algoritmalar ve veri aktarımı için uygundur.
- Gezinme algoritmalarının maliyeti gösterime bağlıdır: listeyle $O(V+E)$, matrisle
  $O(V^2)$.

#### Sonraki Adım

Gösterim hazır olduğuna göre gezinmeye geçilebilir. Sonraki ders, bir başlangıç
düğümünden başlayarak çizgeyi katman katman tarayan enine aramayı ve onun ağırlıksız en
kısa yol problemini nasıl çözdüğünü ele alacak.

### Enine Arama

Source: https://academia.sh/tr/kurslar/veri-yapilari/enine-arama

Kuyrukla katman katman gezinme, ziyaret işaretleme, ağırlıksız en kısa yol ve yol geri kurma.

Ağaçlarda seviye sıralı gezinme, düğümleri katman katman ziyaret ediyordu ve bunu bir
kuyrukla yapıyordu. Aynı fikir çizgelerde de çalışır — bir farkla: çizgede döngüler
vardır ve aynı düğüme birden çok yoldan ulaşılabilir.

**Enine arama (breadth-first search)**, başlangıç düğümünden uzaklığa göre katman katman
ilerleyen gezinmedir.

#### Ziyaret İşaretlemesi

Ağaçta her düğüme tek bir yoldan ulaşılırdı; çizgede bu güvence yoktur. İşaretleme
yapılmazsa aynı düğüm defalarca kuyruğa girer ve döngü varsa gezinme hiç bitmez.

Bu nedenle çizge gezinmelerinin tamamı bir **ziyaret kümesi** tutar. Bir düğüm kuyruğa
konurken işaretlenir; işaretli düğüm bir daha eklenmez.

Ziyaret kümesi, çizge gezinmelerini ağaç gezinmelerinden ayıran tek yapısal eklentidir;
gerisi aynıdır. İşaretlemenin kuyruğa **eklerken** yapılması önemlidir. Kuyruktan çıkarırken yapılırsa,
aynı düğüm çıkarılmadan önce birden çok kez eklenebilir ve kuyruk gereksiz yere büyür.

#### Algoritma

```python
from collections import deque

def enine_ara(komsuluk: dict[str, list[str]], baslangic: str):
    """Katman katman gezer; (ziyaret sırası, uzaklıklar, ebeveynler) döndürür."""
    ziyaret = {baslangic}
    uzaklik = {baslangic: 0}
    ebeveyn: dict[str, str | None] = {baslangic: None}
    sira: list[str] = []
    kuyruk = deque([baslangic])

    while kuyruk:
        dugum = kuyruk.popleft()               # ilk giren ilk çıkar
        sira.append(dugum)
        for komsu in komsuluk.get(dugum, []):
            if komsu not in ziyaret:
                ziyaret.add(komsu)             # eklerken işaretle
                uzaklik[komsu] = uzaklik[dugum] + 1
                ebeveyn[komsu] = dugum
                kuyruk.append(komsu)
    return sira, uzaklik, ebeveyn


komsuluk = {
    "bati":   ["kuzey", "guney"],
    "kuzey":  ["bati", "merkez"],
    "guney":  ["bati", "merkez"],
    "merkez": ["kuzey", "guney", "dogu"],
    "dogu":   ["merkez"],
}

sira, uzaklik, ebeveyn = enine_ara(komsuluk, "bati")
print(sira)          # ['bati', 'kuzey', 'guney', 'merkez', 'dogu']
print(uzaklik)       # {'bati': 0, 'kuzey': 1, 'guney': 1, 'merkez': 2, 'dogu': 3}
```

Ziyaret sırası katmanları izler: önce başlangıç, sonra bir kenar uzaktakiler, sonra iki
kenar uzaktakiler. `merkez` düğümüne hem `kuzey` hem `guney` üzerinden ulaşılabilir;
işaretleme sayesinde yalnızca ilki dikkate alınır.

#### Ağırlıksız En Kısa Yol

Enine aramanın en önemli özelliği burada ortaya çıkar: **bulduğu uzaklıklar, ağırlıksız
çizgede en kısa yol uzunluklarıdır.**

Gerekçe katmanlı ilerlemededir. Bir düğüme ilk kez ulaşıldığında, o ana kadar işlenen
tüm düğümler daha yakın veya eşit uzaklıktadır; dolayısıyla daha kısa bir yol
bulunması olanaksızdır. Bu, kuyruğun ilk giren ilk çıkar davranışının doğrudan sonucudur
— yığıt kullanılsaydı güvence ortadan kalkardı.

Ebeveyn kaydı tutulduğunda, yolun kendisi de geri kurulabilir:

```python
def yolu_kur(ebeveyn: dict[str, str | None], hedef: str) -> list[str]:
    """Ebeveyn kayıtlarından hedefe giden yolu geri kurar."""
    if hedef not in ebeveyn:
        return []                              # ulaşılamıyor
    yol = []
    dugum: str | None = hedef
    while dugum is not None:
        yol.append(dugum)
        dugum = ebeveyn[dugum]
    return list(reversed(yol))


print(yolu_kur(ebeveyn, "dogu"))     # ['bati', 'kuzey', 'merkez', 'dogu']
print(yolu_kur(ebeveyn, "yok"))      # []
```

Yol, hedeften başlayarak geriye izlenir ve ters çevrilir. Aynı teknik, sonraki kursta
ele alınacak ağırlıklı en kısa yol algoritmalarında da kullanılır.

Ağırlıklar devreye girdiğinde enine arama yetmez: az sayıda ağır kenar, çok sayıda hafif
kenardan pahalı olabilir. O durumda kuyruk yerine öncelik kuyruğu kullanan algoritmalar
gerekir; ağaçlar konusundaki yığın bu nedenle çizge algoritmalarının temel yapı
taşlarındandır.

Aynı teknik, hedefin de bilindiği aramalarda **çift yönlü** olarak uygulanabilir: iki
arama başlatılır — biri başlangıçtan, biri hedeften — ve ikisi karşılaştığında yol
bulunmuş olur. Her arama yarı derinliğe kadar ilerlediği için ziyaret edilen düğüm sayısı
belirgin biçimde azalır; dallanma çarpanının yüksek olduğu çizgelerde kazanç büyüktür.

#### Maliyet

Her düğüm en fazla bir kez kuyruğa girer ve her kenar en fazla iki kez incelenir (yönsüz
çizgede her iki uçtan bir kez). Komşuluk listesiyle toplam maliyet:

$$
O(\lvert V \rvert + \lvert E \rvert)
$$

Bellek maliyeti, kuyrukta aynı anda bulunabilecek en fazla düğüm sayısıdır — yani en
geniş katmanın genişliği. Geniş ve sığ çizgelerde bu sayı büyük olabilir; ağaçlardaki
seviye sıralı gezinme için yapılan gözlemin aynısıdır.

#### Çok Kaynaklı Arama

Enine arama tek bir başlangıç düğümüyle sınırlı değildir. Kuyruğa baştan birden çok düğüm
konursa, gezinme **tüm kaynaklardan aynı anda** yayılır ve bulunan uzaklık, en yakın
kaynağa olan uzaklıktır.

```python
def cok_kaynakli(komsuluk: dict[str, list[str]], kaynaklar: list[str]) -> dict[str, int]:
    """Her düğüm için en yakın kaynağa uzaklığı döndürür."""
    uzaklik = {k: 0 for k in kaynaklar}
    kuyruk = deque(kaynaklar)
    while kuyruk:
        dugum = kuyruk.popleft()
        for komsu in komsuluk.get(dugum, []):
            if komsu not in uzaklik:
                uzaklik[komsu] = uzaklik[dugum] + 1
                kuyruk.append(komsu)
    return uzaklik


print(cok_kaynakli(komsuluk, ["bati", "dogu"]))
# {'bati': 0, 'dogu': 0, 'kuzey': 1, 'guney': 1, 'merkez': 1}
```

Tek kaynaklı aramada `merkez` düğümünün uzaklığı iki idi; iki kaynakla bir olur, çünkü
`dogu` düğümüne komşudur.

Bu kalıp, "her hücrenin en yakın su kaynağına uzaklığı" veya "her düğümün en yakın
sunucuya gecikmesi" gibi problemleri, her kaynak için ayrı arama yapmadan tek geçişte
çözer. Aynı işi kaynak sayısı kadar arama ile yapmak, maliyeti kaynak sayısıyla
çarpardı.

#### Kullanım Alanları

**En az adımlı çözüm.** Bir bulmacanın durumları düğüm, hamleler kenar sayıldığında,
enine arama en az hamleli çözümü bulur.

**Bağlı bileşenler.** Her ziyaret edilmemiş düğümden bir arama başlatmak, çizgeyi
bileşenlerine ayırır. Ayrık kümeler dersindeki soru burada gezinmeyle yanıtlanır; fark,
oradaki yapının kenarlar akış hâlinde gelirken çalışmasıdır.

**İki parçalılık sınaması.** Katmanlar dönüşümlü olarak iki renge boyanır; aynı katmandaki
iki düğüm arasında kenar bulunursa çizge iki parçalı değildir.

**Yayılma modelleri.** Bir ağda bilginin, bir toplulukta bir etkinin veya bir sistemde bir
arızanın kaç adımda nereye ulaştığı.

**Ağ tarama.** Bağlantılar üzerinden ilerleyen tarayıcılar, başlangıç adresinden
uzaklığa göre gezinmek için enine arama kullanır.

Son bir uyarı: enine aramanın en kısa yol güvencesi, tüm kenarların eşit maliyetli
sayılmasına dayanır. Kenarlara ağırlık eklendiği anda güvence ortadan kalkar ve kuyruk
yerine öncelik kuyruğu gerekir; bu, ağaçlar konusundaki yığının çizge algoritmalarındaki
rolünü açıklar. Ağırlıkların yalnızca bir bölümü farklıysa — örneğin bazı kenarlar sıfır,
bazıları bir maliyetliyse — çift uçlu kuyrukla çalışan bir ara çözüm de kullanılabilir.

#### Özet

- Enine arama, kuyruk kullanarak başlangıçtan uzaklığa göre katman katman ilerler.
- Çizgede aynı düğüme birden çok yoldan ulaşılabildiği için ziyaret işaretlemesi
  zorunludur; işaretleme kuyruğa eklerken yapılır.
- Bulunan uzaklıklar, ağırlıksız çizgede en kısa yol uzunluklarıdır; güvence, kuyruğun
  ilk giren ilk çıkar davranışından gelir.
- Ebeveyn kayıtları tutulduğunda yolun kendisi geriye izlenerek kurulur.
- Maliyet, komşuluk listesiyle $O(V + E)$'dir; bellek en geniş katmana bağlıdır.
- Ağırlıklı çizgelerde enine arama yetmez; öncelik kuyruğu kullanan algoritmalar gerekir.

#### Sonraki Adım

Enine arama genişliği önceler: yakın olan her şey uzağa gitmeden gezilir. Karşıt strateji,
bir yolu sonuna kadar izleyip ancak tıkandığında geri dönmektir. Sonraki ders bu stratejiyi
ve onun çözdüğü farklı problem ailesini ele alacak.

### Derine Arama

Source: https://academia.sh/tr/kurslar/veri-yapilari/derine-arama

Yığıtla derinlemesine gezinme, özyinelemeli ve açık yığıtlı biçimler, keşif–bitiş zamanları ve döngü tespiti.

Enine arama, uzaklığa göre ilerliyordu: yakın olan her şey gezilmeden uzağa gidilmiyordu.
**Derine arama (depth-first search)** karşıt stratejiyi izler — bir yolu tıkanana kadar
izler, sonra en son ayrım noktasına döner ve başka bir dal dener.

Yapısal fark tek bir yerdedir: kuyruk yerine **yığıt** kullanılır. Ağaçlarda seviye
sıralı ve derinlik gezinmeleri arasındaki fark neyse, burada da odur.

#### Özyinelemeli Biçim

Yığıt açıkça tutulmayabilir; özyineleme, çağrı yığıtını aynı iş için kullanır.

```python
def derine_ara(komsuluk: dict[str, list[str]], baslangic: str) -> list[str]:
    """Derinlemesine gezer; ziyaret sırasını döndürür."""
    ziyaret: set[str] = set()
    sira: list[str] = []

    def gez(dugum: str) -> None:
        ziyaret.add(dugum)
        sira.append(dugum)
        for komsu in komsuluk.get(dugum, []):
            if komsu not in ziyaret:
                gez(komsu)                       # tıkanana kadar derine in

    gez(baslangic)
    return sira


komsuluk = {
    "bati":   ["kuzey", "guney"],
    "kuzey":  ["bati", "merkez"],
    "guney":  ["bati", "merkez"],
    "merkez": ["kuzey", "guney", "dogu"],
    "dogu":   ["merkez"],
}

print(derine_ara(komsuluk, "bati"))
# ['bati', 'kuzey', 'merkez', 'guney', 'dogu']
```

Enine arama aynı çizgede `['bati', 'kuzey', 'guney', 'merkez', 'dogu']` sırasını
veriyordu. Derine aramada `kuzey` düğümünden hemen `merkez`'e inilir; `guney` ancak
o dal tükendiğinde ziyaret edilir.

#### Açık Yığıtlı Biçim

Programlama Temelleri kursunda kurulan dönüşüm burada da geçerlidir: çağrı yığıtı yerine
açık bir yığıt tutulabilir. Derin çizgelerde bu, özyineleme sınırına çarpmayı önler.

```python
def derine_ara_yigitla(komsuluk: dict[str, list[str]], baslangic: str) -> list[str]:
    ziyaret: set[str] = set()
    sira: list[str] = []
    yigit = [baslangic]
    while yigit:
        dugum = yigit.pop()                      # son giren ilk çıkar
        if dugum in ziyaret:
            continue
        ziyaret.add(dugum)
        sira.append(dugum)
        for komsu in reversed(komsuluk.get(dugum, [])):
            if komsu not in ziyaret:
                yigit.append(komsu)              # ters sırada it: sıra korunsun
    return sira


print(derine_ara_yigitla(komsuluk, "bati"))
# ['bati', 'kuzey', 'merkez', 'guney', 'dogu']
```

Komşuların ters sırada itilmesi, ağaç gezinmelerinde sağ çocuğun önce itilmesiyle aynı
gerekçeye dayanır: yığıt, itilenlerin tersini verir.

İki biçim arasında ince bir fark vardır: açık yığıtlı sürümde bir düğüm, ziyaret
edilmeden önce birden çok kez yığıta girebilir. Bu nedenle çıkarma sırasında yeniden
denetlenir. Bellek kullanımı bir miktar artar, davranış aynı kalır.

#### Keşif ve Bitiş Zamanları

Derine aramanın taşıdığı ek bilgi, her düğüm için iki zaman damgasıdır:

- **Keşif zamanı:** Düğüme ilk ulaşıldığı an.
- **Bitiş zamanı:** Düğümün tüm soyu gezildikten sonra geri dönüldüğü an.

Bu iki değer, düğümler arasındaki ilişkiyi sınıflandırmayı sağlar. Bir düğümün keşif–bitiş
aralığı, diğerinin aralığını tümüyle kapsıyorsa ikincisi birincinin soyudur; aralıklar
kesişmiyorsa iki düğüm ayrı dallardadır. Aralıklar kısmen örtüşemez — bu, gezinmenin
yığıt yapısının doğrudan sonucudur.

Bitiş zamanları, sonraki dersteki topolojik sıralamanın temelini oluşturur.

#### Döngü Tespiti

Derine aramanın en yaygın kullanımlarından biri, yönlü çizgede döngü aramaktır. Ayrım,
"ziyaret edildi" ile "hâlâ yığıtta" arasındadır: gezinme sırasında **hâlâ açık olan** bir
düğüme geri dönülüyorsa döngü vardır.

```python
def dongu_var_mi(komsuluk: dict[str, list[str]]) -> bool:
    """Yönlü çizgede döngü olup olmadığını sınar."""
    ziyaret: set[str] = set()
    acik: set[str] = set()                       # o an yığıtta olanlar

    def gez(dugum: str) -> bool:
        ziyaret.add(dugum)
        acik.add(dugum)
        for komsu in komsuluk.get(dugum, []):
            if komsu in acik:
                return True                      # geri kenar: döngü
            if komsu not in ziyaret and gez(komsu):
                return True
        acik.discard(dugum)                      # dal tamamlandı
        return False

    return any(gez(d) for d in komsuluk if d not in ziyaret)


cevrimsiz = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
cevrimli = {"a": ["b"], "b": ["c"], "c": ["a"]}

print(dongu_var_mi(cevrimsiz))     # False
print(dongu_var_mi(cevrimli))      # True
```

`acik` kümesi olmadan, yalnızca `ziyaret` ile sınama yapılırsa yanlış sonuç alınır:
`cevrimsiz` çizgesinde `d` düğümüne iki farklı yoldan ulaşılır, ama bu bir döngü değildir.
İki kavramın ayrılması bu nedenle zorunludur.

#### İki Gezinmenin Karşılaştırması

| Ölçüt | Enine arama | Derine arama |
|---|---|---|
| Yardımcı yapı | Kuyruk | Yığıt (veya özyineleme) |
| İlerleme | Katman katman | Dal boyunca derine |
| Ağırlıksız en kısa yol | Bulur | Bulmaz |
| Bellek | En geniş katman | En derin yol |
| Doğal kullanım | Uzaklık, yayılma, en az adım | Döngü, sıralama, geri izleme |
| Maliyet | $O(V + E)$ | $O(V + E)$ |

Dördüncü satır pratik seçimde belirleyici olabilir: geniş ve sığ bir çizgede enine
aramanın kuyruğu çok büyür; derin ve dar bir çizgede derine aramanın yığıtı.

Üçüncü satır ise en sık yapılan hatanın kaynağıdır: derine arama bir yol bulur, ama
bulduğu yolun en kısa olduğuna dair hiçbir güvence yoktur.

#### Yinelemeli Derinleştirme

Karşılaştırma tablosu bir ikilem gösterir: enine arama en kısa yolu bulur ama belleği çok
kullanabilir; derine arama az bellek kullanır ama en kısa yolu bulmaz.

**Yinelemeli derinleştirme**, ikisini birleştirir. Derine arama, önce derinlik sınırı bir
olarak çalıştırılır; çözüm bulunamazsa sınır ikiye çıkarılır ve arama baştan yapılır.
Sınır arttıkça derinleşilir.

İlk bakışta savurgan görünür — aynı üst katmanlar tekrar tekrar gezilir. Ancak dallanma
çarpanı birden büyük olduğunda düğümlerin çoğu **son katmandadır**; tekrar edilen iş,
toplamın küçük bir bölümü kalır. Maliyet, enine aramanınkiyle aynı mertebede olur.

Kazanç bellektedir: her an yalnızca tek bir yol yığıtta tutulur. Bulunan ilk çözüm de en
sığ olanıdır, çünkü daha küçük sınırlarda çözüm bulunamamıştır.

Yöntem, arama uzayının önceden bilinmediği ve belleğe sığmadığı problemlerde — oyun ağacı
araması, bulmaca çözme — tercih edilir.

#### Kullanım Alanları

- **Döngü tespiti.** Yukarıdaki gibi; bağımlılık çizgelerinin geçerliliği bu sınamayla
  denetlenir.
- **Bağlı bileşenler.** Enine aramada olduğu gibi, her ziyaret edilmemiş düğümden bir
  gezinme başlatılır.
- **Topolojik sıralama.** Bitiş zamanlarının tersi, geçerli bir sıralama verir; sonraki
  dersin konusu.
- **Geri izleme.** Labirent çözme, bulmaca doldurma ve kısıt sağlama problemleri, derine
  aramanın seçim ağacı üzerindeki uygulamasıdır.
- **Yol bulma.** İki düğüm arasında herhangi bir yol aranıyorsa — en kısası değil —
  derine arama daha az bellekle sonuç verir.

#### Özet

- Derine arama bir yolu tıkanana kadar izler, sonra son ayrım noktasına döner; kuyruk
  yerine yığıt kullanır.
- Özyinelemeli biçim çağrı yığıtını kullanır; açık yığıtlı biçim derin çizgelerde
  güvenlidir.
- Keşif ve bitiş zamanları düğümler arası soy ilişkisini kodlar; aralıklar ya kapsar ya
  ayrıktır.
- Döngü tespitinde "ziyaret edildi" ile "hâlâ açık" ayrımı zorunludur.
- Enine arama en kısa yolu bulur, derine arama bulmaz; bellek davranışları çizgenin
  biçimine göre ayrışır.
- İki gezinmenin de maliyeti $O(V + E)$'dir.

#### Sonraki Adım

Bağımlılık ilişkilerini modelleyen çizgelerde asıl soru şudur: işler hangi sırayla
yapılmalıdır? Kursun son dersi, yönlü çevrimsiz çizgelerde geçerli bir yürütme sırası
üreten topolojik sıralamayı ele alacak ve bu kursun kurduğu yapıları bir arada
kullanacak.

### Topolojik Sıralama

Source: https://academia.sh/tr/kurslar/veri-yapilari/topolojik-siralama

Bağımlılık çizgesinden geçerli yürütme sırası üretme, giriş dereceli algoritma, döngü tespiti ve kullanım alanları.

Yönlü çevrimsiz çizgeler, çizge kavramı dersinde bağımlılık ilişkilerinin doğal modeli
olarak tanıtılmıştı: bir kenar, "şu iş şundan önce yapılmalı" demektir.

Bu dersin sorusu doğrudan pratiktir: verilen bağımlılıklara uygun bir **yürütme sırası**
nasıl bulunur?

#### Tanım ve Varlık Koşulu

**Topolojik sıralama**, çizgedeki tüm düğümlerin öyle bir dizilişidir ki, her kenar
listede soldan sağa doğru gider: `a → b` kenarı varsa, `a` listede `b`'den önce gelir.

Böyle bir sıralamanın var olması için tek bir koşul gerekir: **çizge döngüsüz olmalıdır.**
Döngü varsa, döngüdeki her düğüm kendisinden önce gelmek zorunda kalır; bu olanaksızdır.

Koşul, sıralama algoritmasının aynı zamanda bir döngü sınayıcısı olduğu anlamına gelir:
tüm düğümler sıralanamıyorsa çizgede döngü vardır.

#### Giriş Derecesi Temelli Algoritma

En sezgisel yöntem, bağımlılığı kalmamış işlerden başlamaktır.

1. Her düğümün **giriş derecesini** — kaç kenarın ona geldiğini — hesapla.
2. Giriş derecesi sıfır olan düğümleri bir kuyruğa koy; bunlar hiçbir şeyi beklemiyor.
3. Kuyruktan bir düğüm al, sıralamaya ekle. Ondan çıkan her kenarı kaldır: hedef düğümün
   giriş derecesini bir azalt; sıfıra düşerse kuyruğa ekle.
4. Kuyruk boşalana kadar sürdür.

Sona gelindiğinde sıralamadaki düğüm sayısı toplam düğüm sayısından azsa, kalan düğümler
bir döngünün parçasıdır.

```python
from collections import deque

def topolojik_sirala(komsuluk: dict[str, list[str]]) -> list[str] | None:
    """Geçerli bir sıralama döndürür; döngü varsa None."""
    giris = {dugum: 0 for dugum in komsuluk}
    for dugum in komsuluk:
        for hedef in komsuluk[dugum]:
            giris[hedef] += 1

    kuyruk = deque(sorted(d for d in giris if giris[d] == 0))   # belirlilik için sıralı
    sonuc: list[str] = []

    while kuyruk:
        dugum = kuyruk.popleft()
        sonuc.append(dugum)
        for hedef in komsuluk[dugum]:
            giris[hedef] -= 1                     # bağımlılık karşılandı
            if giris[hedef] == 0:
                kuyruk.append(hedef)

    return sonuc if len(sonuc) == len(komsuluk) else None


# Bu müfredatın kendi önkoşul ilişkisi bir bağımlılık çizgesidir.
kurslar = {
    "bilgisayarlar-nasil-calisir": ["programlama-temelleri"],
    "programlama-temelleri":       ["veri-yapilari"],
    "veri-yapilari":               ["algoritmalar"],
    "modelleme-ve-gosterim":       ["algoritmalar"],
    "algoritmalar":                [],
}

print(topolojik_sirala(kurslar))
# ['bilgisayarlar-nasil-calisir', 'modelleme-ve-gosterim',
#  'programlama-temelleri', 'veri-yapilari', 'algoritmalar']
```

Sonuç, her kursun önkoşullarından sonra geldiği bir okuma sırasıdır. `modelleme-ve-gosterim` kursunun
erken çıkması, hiçbir önkoşulu olmamasındandır; `algoritmalar` en sonda çıkar çünkü iki
ayrı kursu bekler.

#### Sıralama Tek Değildir

Aynı çizge için genellikle birden çok geçerli sıralama vardır. Yukarıdaki örnekte
`modelleme-ve-gosterim` kursu, `algoritmalar` kursundan önce gelmek koşuluyla listenin herhangi bir
yerinde olabilir.

Bu, algoritmanın seçim yaptığı anlamına gelir: kuyrukta birden çok düğüm varken hangisinin
alınacağı serbesttir. Yukarıdaki gerçekleştirim, çıktının tekrarlanabilir olması için
alfabetik sıra kullanır; başka bir ölçüt de seçilebilir — örneğin önce en kısa işi almak.

Sıralamanın **tek** olduğu durum, çizgenin bir zincir oluşturmasıdır: her adımda kuyrukta
tam olarak bir düğüm bulunur.

#### Döngü Durumu

```python
dongulu = {
    "a": ["b"],
    "b": ["c"],
    "c": ["a"],       # döngü: a → b → c → a
}

print(topolojik_sirala(dongulu))     # None
```

Hiçbir düğümün giriş derecesi sıfır olmadığı için kuyruk baştan boştur ve sonuç boş
kalır. Uzunluk denetimi bunu yakalar.

Bu, önceki dersteki derine arama temelli döngü tespitinin alternatifidir. İkisi aynı
soruyu yanıtlar; giriş dereceli yöntem, döngü bulunduğunda hangi düğümlerin
**sıralanamadığını** da doğrudan verir — sıralamaya girmeyenler. Bu küme döngüdeki
düğümleri kapsar ama onlarla sınırlı değildir: yalnızca bir döngü üzerinden ulaşılabilen
düğümler de sıralamaya giremez.

Derine arama temelli ikinci bir yöntem de vardır: düğümler bitiş zamanına göre
sıralanır ve liste ters çevrilir. Sonuç aynı biçimde geçerlidir; hangi yöntemin
seçileceği, çizgenin gösterimine ve döngü bilgisine ihtiyaç olup olmamasına bağlıdır.

#### Katmanlar ve Paralel Yürütme

Algoritmanın ürettiği düz liste, sıralı yürütme içindir. Bağımsız işler paralel
çalıştırılabiliyorsa, daha yararlı bir çıktı **katmanlardır**: aynı anda başlatılabilecek
işler kümesi.

Katmanlar, kuyruğun her turdaki içeriğidir — enine aramadaki seviye ayrımının aynısı:

```python
def katmanlar(komsuluk: dict[str, list[str]]) -> list[list[str]] | None:
    giris = {d: 0 for d in komsuluk}
    for d in komsuluk:
        for h in komsuluk[d]:
            giris[h] += 1

    hazir = sorted(d for d in giris if giris[d] == 0)
    sonuc: list[list[str]] = []
    islenen = 0
    while hazir:
        sonuc.append(hazir)
        islenen += len(hazir)
        sonraki: list[str] = []
        for dugum in hazir:
            for hedef in komsuluk[dugum]:
                giris[hedef] -= 1
                if giris[hedef] == 0:
                    sonraki.append(hedef)
        hazir = sorted(sonraki)
    return sonuc if islenen == len(komsuluk) else None


print(katmanlar(kurslar))
# [['bilgisayarlar-nasil-calisir', 'modelleme-ve-gosterim'],
#  ['programlama-temelleri'], ['veri-yapilari'], ['algoritmalar']]
```

Birinci katmandaki iki kurs eşzamanlı okunabilir; ikinci katman ancak birinci
tamamlandıktan sonra başlar. Katman sayısı, tüm işlerin sonsuz paralellikle
tamamlanabileceği en kısa süredir — bu değere çizgenin **kritik yol uzunluğu** denir.

#### Maliyet

Her düğüm kuyruğa en fazla bir kez girer ve her kenar tam olarak bir kez incelenir:

$$
O(\lvert V \rvert + \lvert E \rvert)
$$

Giriş derecelerinin hesaplanması da tüm kenarları bir kez gezer; toplam maliyet
değişmez.

#### Kullanım Alanları

**Derleme sistemleri.** Kaynak dosyalar arasındaki bağımlılıklar bir çizgedir; hangi
dosyanın önce derleneceği topolojik sıralamayla belirlenir. Bilgisayarlar Nasıl Çalışır
kursundaki bağlama aşaması bu sıraya dayanır.

**Paket yöneticileri.** Bağımlılıkların kurulum sırası; döngüsel bağımlılık, kurulumun
reddedilme nedenidir.

**Görev zamanlama.** Birbirine bağımlı işlerin yürütülme sırası; veri hatlarında
adımların çalıştırılma düzeni bu yolla belirlenir.

**Hesap tablosu yeniden hesaplama.** Bir hücre değiştiğinde, ona bağımlı hücrelerin
hangi sırayla güncelleneceği.

**Öğrenme yolları.** Bu müfredatın kendi önkoşul yapısı; yukarıdaki örnek gerçek bir
uygulamadır.

#### Kursun Toparlanması

Bu ders, kursun kurduğu yapıların birlikte çalıştığı bir örnektir: çizge bir **eşleme**
ile gösterilir, giriş dereceleri bir **sayaç** tutar, hazır düğümler bir **kuyrukta**
bekler, sonuç bir **dizide** birikir.

Kurs boyunca tekrarlanan ilke de burada görünür hâle gelir: her yapı bir işlemi ucuzlatır
ve bunu başka bir işlemi pahalılaştırarak yapar. Dizi erişimi ucuzlatır, ekleme
pahalıdır; bağlı liste tersini yapar. Karma tablosu aramayı sabite indirir, sırayı
kaybeder. Ağaç sırayı korur, sabit zamanı kaybeder. Yığın uç elemanı verir, arama
yapamaz.

Doğru yapıyı seçmek, bu nedenle "en iyi yapıyı bulmak" değildir: **hangi işlemin sık,
hangisinin seyrek olduğunu bilmektir.** Bir sonraki kursun konusu olan algoritmalar, aynı
soruyu işlem düzeyinde sorar.

#### Özet

- Topolojik sıralama, her kenarın listede soldan sağa gittiği bir düğüm dizilişidir.
- Sıralamanın var olması için çizgenin döngüsüz olması gerekir; algoritma aynı zamanda
  döngü sınayıcısıdır.
- Giriş dereceli yöntem, bağımlılığı kalmamış düğümlerden başlar ve kenarları kaldırdıkça
  yeni hazır düğümler ortaya çıkar.
- Aynı çizge için genellikle birden çok geçerli sıralama vardır; algoritma kuyruktan
  seçim yaparken bir ölçüt uygular.
- Maliyet $O(V + E)$'dir.
- Derleme sistemleri, paket yöneticileri, görev zamanlama ve önkoşul yapıları bu
  sıralamayı kullanır.

#### Sonraki Adım

Bu kurs, verinin nasıl düzenlendiğini ve bu düzenin işlem maliyetini nasıl belirlediğini
kurdu. Bir sonraki kurs — **Algoritmalar** — bu yapıların üzerinde çalışan çözümleri ele
alacak: bir problemin farklı çözümleri nasıl karşılaştırılır, maliyet nasıl biçimsel
olarak ifade edilir ve sıralama, arama ile çizge problemleri hangi yöntemlerle çözülür.