AVL ağaçları: denge faktörü ve rotasyonlar

Geçen hafta gördüğün ikili arama ağacı (BST) güzel ama kırılgan. Anahtarları sıralı eklersen (1, 2, 3, …) ağaç sağa doğru bir zincire döner ve arama O(n) olur. AVL ağacı (Adelson-Velsky ve Landis) bu sorunu çözen ilk kendini dengeleyen (self-balancing) BST’dir. Sınavda neredeyse her zaman aynı soru gelir: “Şu anahtarları boş bir AVL ağacına sırayla ekle, son ağacı çiz.” Bu sayfadaki dört rotasyonu ezberden değil, mantığıyla bilen biri bu soruyu kaçırmaz.

Altın kurallar:

1. AVL kuralı: her düğümde sol ve sağ alt ağacın yükseklik farkı en fazla 1.
2. Yükseklik: boş ağaç -1, yaprak 0. Denge faktörü (balance factor) bf = height(sol) - height(sağ).
3. Ekledikten sonra yukarı çık. bf değeri +2 ya da -2 olan ilk (en derindeki) düğümde dur ve düzelt. Eklemede tek düzeltme yeter.
4. Yön sorusu: yeni anahtar o düğümden itibaren hangi iki adımı attı? Sol-sol, sağ-sağ, sol-sağ, sağ-sol. Dört durumun adı buradan gelir.

Yükseklik ve denge faktörü

Bir düğümün yüksekliği (height), ondan en uzak yaprağa giden yoldaki kenar sayısıdır. Hesabı her zaman alttan yukarı yap:

$height(t) = 1 + \max(height(t.left),\ height(t.right)), \qquad height(null) = -1$

        30  h=2, bf=1-0=1
       /  \
     20    40   h(20)=1 bf=1, h(40)=0
    /
  10            h=0, bf=0

Bu ağaç AVL: bütün bf değerleri -1, 0 ya da 1. 10’un altına 5 eklersen 20’nin bf’si 2 olur ve kural bozulur.

TUZAK · Yükseklik ile derinlik karışmasın. Derinlik (depth) kökten aşağı sayılır, yükseklik yapraktan yukarı. bf hesabında hep yükseklik kullanılır. Bazı kaynaklar yaprağa 1 der; o zaman tüm değerler 1 kayar ama bf aynı çıkar. Sınavda hocanın tanımına bak.

Neden O(log n)?

En az düğümle h yüksekliğinde AVL ağacı kurmak istersen, bir alt ağacı h-1, diğerini h-2 yüksekliğinde yaparsın (fark 1’e izin var). Buradan:

$N(h) = N(h-1) + N(h-2) + 1, \qquad N(0)=1,\ N(1)=2$

Bu dizi Fibonacci gibi üstel büyür. Düğüm sayısı yükseklikle üstel artıyorsa, yükseklik düğüm sayısıyla logaritmik artar: $h < 1.44 \log_2 n$. Arama, ekleme ve silme yükseklik kadar adım attığı için hepsi O(log n). Rotasyon sadece birkaç işaretçi değiştirir, O(1).

Dört durum ve rotasyonlar

Ekleme normal BST eklemesi gibi yapılır. Sonra eklenen yaprağın atalarına yukarı doğru bakılır. İlk dengesiz düğüme k diyelim. Yeni anahtarın k’dan sonra attığı iki adım durumu belirler.

LL ve RR: tek rotasyon

LL durumunda yeni anahtar k’nın sol çocuğunun sol alt ağacına gitmiştir. Sol çocuk (k1) yukarı çıkar, k2 sağa iner. X, Y, Z alt ağaçlardır:

LL: k2'de saga rotasyon
        k2                k1
       /  \              /  \
     k1    Z    ==>     X    k2
    /  \                    /  \
   X    Y                  Y    Z

Dikkat: k1’in sağındaki Y alt ağacı k2’nin soluna geçer. Y’deki her anahtar k1’den büyük, k2’den küçüktür. Yani yeni yerinde de BST sırası korunur. Inorder sıra X, k1, Y, k2, Z her iki çizimde aynıdır.

RR bunun ayna görüntüsüdür: k1 üzerinde sola rotasyon, sağ çocuk k2 köke çıkar, k2’nin sol alt ağacı k1’in sağına geçer.

RR: 10'da sola rotasyon (10, 20, 30 eklendi)
  10                  20
    \                /  \
     20     ==>    10    30
       \
        30

LR ve RL: çift rotasyon

LR durumunda yeni anahtar k’nın solunun sağına gitmiştir. Tek sağa rotasyon burada işe yaramaz, sadece eğriliği diğer tarafa taşır. Çözüm iki adım: önce sol çocukta sola rotasyon (durumu LL’ye çevirir), sonra k’da sağa rotasyon. Sonuçta ortadaki düğüm (k1 ile k3 arasındaki) en üste çıkar.

LR: 30, 10, 20 eklendi
    30          30           20
   /           /            /  \
  10    ==>   20    ==>   10    30
    \        /
     20     10
  10'da sola   30'da saga

RL ayna görüntüsü: önce sağ çocukta sağa, sonra k’da sola rotasyon.

İPUCU · Çift rotasyonun kısa yolu. k, çocuğu ve torunu (yeni anahtarın yolundaki üç düğüm) sıraya diz. Ortanca değer yeni kök olur, küçüğü sola, büyüğü sağa gider. Torunun eski iki alt ağacı sırayla sol ve sağ tarafa dağıtılır.

Java’da AVL ekleme

Düğüm kendi yüksekliğini tutar. Ekleme özyinelemelidir: geri dönerken her düğüm yüksekliğini günceller ve gerekirse dengelenir. balance metodu yükseklikleri karşılaştırdığı için hem ekleme hem silme için çalışır.

static class AvlNode {
    int key, height;          // yaprak: height = 0
    AvlNode left, right;
    AvlNode(int key) { this.key = key; }
}

static int height(AvlNode t) { return t == null ? -1 : t.height; }

static void update(AvlNode t) {
    t.height = 1 + Math.max(height(t.left), height(t.right));
}

static AvlNode rotateRight(AvlNode k2) {   // LL
    AvlNode k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;
    update(k2);
    update(k1);
    return k1;
}

static AvlNode rotateLeft(AvlNode k1) {    // RR
    AvlNode k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;
    update(k1);
    update(k2);
    return k2;
}

static AvlNode insert(AvlNode t, int x) {
    if (t == null) return new AvlNode(x);
    if (x < t.key) t.left = insert(t.left, x);
    else if (x > t.key) t.right = insert(t.right, x);
    else return t;                         // kopya eklenmez
    return balance(t);
}

static AvlNode balance(AvlNode t) {
    update(t);
    int bf = height(t.left) - height(t.right);
    if (bf > 1) {
        if (height(t.left.left) < height(t.left.right))
            t.left = rotateLeft(t.left);   // LR: once LL'ye cevir
        return rotateRight(t);
    }
    if (bf < -1) {
        if (height(t.right.right) < height(t.right.left))
            t.right = rotateRight(t.right); // RL
        return rotateLeft(t);
    }
    return t;
}

Kullanım hep root = insert(root, x); biçimindedir. Rotasyon alt ağacın kökünü değiştirdiği için dönen değeri atamak şart.

Çözümlü örnek: 15, 20, 24, 10, 13, 7, 30, 36, 25

Boş bir AVL ağacına bu dokuz anahtarı ekleyelim. Her adımda yolu takip et, yukarı doğru bf kontrol et.

+15, +20: sorun yok. +24: 15’in bf’si -2, yol sağ-sağ: RR, 15’te sola rotasyon.

  15                 20
    \               /  \
     20    ==>    15    24
       \
        24

+10: 15’in soluna, dengeli. +13: 13 → 20 → 15 → 10 → sağ. 15’in bf’si 2 (sol yükseklik 1, sağ -1). Yol sol-sağ: LR. 10’da sola, 15’te sağa. 13 ortaya çıkar.

       20                   20
      /  \                 /  \
    15    24    ==>      13    24
   /                    /  \
  10                  10    15
    \
     13

+7: 7 → 20 → 13 → 10 → sol. Yukarı bak: 10’un bf’si 1, 13’ün bf’si 1, 20’nin bf’si height(13) - height(24) = 2 - 0 = 2. Yol (20’den) sol-sol: LL, 20’de sağa rotasyon. 13 köke çıkar, 13’ün sağ çocuğu 15, 20’nin soluna geçer.

         13
        /  \
      10    20
     /     /  \
    7    15    24

+30: 24’ün sağına, dengeli. +36: 24’ün bf’si -2, sağ-sağ: RR, 24’te sola rotasyon, 30 yukarı çıkar.

         13
        /  \
      10    20
     /     /  \
    7    15    30
              /  \
            24    36

+25: 25 → 13 → 20 → 30 → 24 → sağ. 24’ün bf’si -1, 30’un bf’si 1, 20’nin bf’si 0 - 2 = -2. Yol (20’den) sağ-sol: RL. Önce 30’da sağa rotasyon (24 yukarı), sonra 20’de sola rotasyon (24, 20’nin yerine geçer).

          13
        /    \
      10      24
     /       /  \
    7      20    30
          /     /  \
        15    25    36

Program çıktısı (her eklemeden sonra seviye sırası ve yapılan düzeltme):

+15 -> 15
+20 -> 15 20
+24 -> 20 15 24   [RR at 15]
+10 -> 20 15 24 10
+13 -> 20 13 24 10 15   [LR at 15]
+7 -> 13 10 20 7 15 24   [LL at 20]
+30 -> 13 10 20 7 15 24 30
+36 -> 13 10 20 7 15 30 24 36   [RR at 24]
+25 -> 13 10 24 7 20 30 15 25 36   [RL at 20]

Son ağacın yüksekliği 3. Kökün bf’si 1 - 2 = -1, kural tutuyor.

Silme kısaca

AVL’den silme önce normal BST silmesidir (iki çocuklu düğümde sağ alt ağacın en küçüğü, inorder successor, yerine geçer). Sonra silinen yerden köke kadar her düğümde balance çağrılır. Eklemeden farkı: silmede bir rotasyon alt ağacın yüksekliğini azaltabilir ve dengesizlik yukarıya taşınabilir. Yani köke kadar birden fazla rotasyon gerekebilir. Durum seçimi yine çocukların yüksekliğine bakılarak yapılır; yukarıdaki balance metodu bunu zaten yapıyor. Süre yine O(log n).

Sık yapılan hatalar

        20
       /  \
     10    30
    /  \
   5    15
  /
 3

static AvlNode rotateRight(AvlNode k2) {
    AvlNode k1 = k2.left;
    k2.left = k1.right;   // ortadaki alt agac (Y) k2'ye gecer
    k1.right = k2;
    k2.height = 1 + Math.max(height(k2.left), height(k2.right));
    k1.height = 1 + Math.max(height(k1.left), height(k1.right));
    return k1;            // yeni kok; cagiran t = rotateRight(t) yazar
}