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

Ö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.

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 \leq h \leq \log_2 n$$

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$ ile $\log_2 n$ 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.