Dengeli Arama Ağaçları

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

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.

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.