İkili arama ağaçları: arama, ekleme, silme

Sıralı bir dizide ikili arama (binary search) $O(\log n)$ sürer, ama ekleme ve silme elemanları kaydırdığı için $O(n)$. Bağlı listede ekleme kolay, ama arama $O(n)$. İkili arama ağacı (binary search tree, BST) ikisinin iyi tarafını birleştirmeye çalışır: ağaç alçak kaldıkça arama, ekleme ve silme $O(\log n)$.

Sınavda bu konudan neredeyse kesin gelen sorular: verilen sırayla ekle, ağacı çiz, şu düğümü sil, yeni ağacı çiz, arama yolunu yaz, bu ağaç BST mi, en kötü durum ne. Hepsi aşağıdaki birkaç kurala dayanıyor.

BST özelliği

Her düğüm x için:

• x’in sol alt ağacındaki her anahtar x’ten küçük,
• x’in sağ alt ağacındaki her anahtar x’ten büyük.

Bu derste anahtarlar tekrar etmez. Bu özellikten çıkan en önemli sonuç: inorder gezinme anahtarları artan sırada verir.

Bütün sayfa boyunca bu ağacı kullanacağız. Boş ağaca 50, 30, 70, 20, 40, 60, 80, 35, 45, 65 sırasıyla eklendi:

            50
          /    \
        30      70
       /  \    /  \
     20   40  60   80
         / \    \
       35  45    65

Inorder: 20 30 35 40 45 50 60 65 70 80. Sıralı, demek ki BST.

Arama (find / contains)

Kökten başla. Aranan anahtar düğümden küçükse sola, büyükse sağa git, eşitse bulundu. null’a düşersen yok.

find 45: 50 30 40 45      bulundu, 4 karş.
find 63: 50 70 60 65 null yok, 4 karş.

Her adımda bir seviye iniyorsun, yani maliyet en fazla yükseklik + 1 karşılaştırma: $O(h)$.

findMin hep sola gider (20), findMax hep sağa gider (80). Karşılaştırma bile gerekmez.

Ekleme (insert)

Yeni anahtarı arar gibi in. Arama null’a düştüğü yerde yeni bir yaprak oluştur. Ekleme hiçbir zaman mevcut düğümleri yerinden oynatmaz.

Yukarıdaki ağaca 63 eklenirse: 50 → 70 → 60 → 65 → 65’in solu boş, 63 oraya girer.

Ekleme sırası şekli belirler

Aynı anahtar kümesi, farklı sıralarla çok farklı ağaçlar verir:

1 2 3 4 5 6 7 sırası:      4 2 6 1 3 5 7 sırası:

1                                4
 \                             /   \
  2                           2     6
   \                         / \   / \
    3                       1   3 5   7
     \
      ...7   (yükseklik 6)          (yükseklik 2)

Soldaki ağaç aslında bir bağlı liste (degenerate tree). Arama $O(n)$. Sağdaki mükemmel dengeli, arama $O(\log n)$. Sıralı veri eklemek gerçek hayatta çok yaygın (zaman damgaları, artan ID’ler), bu yüzden düz BST’ye güvenmek risklidir.

TUZAK · “zigzag” girdiler de kötüdür. 10, 90, 20, 80, 30, 70 sıralı değil ama her eleman bir öncekinin tek çocuğu olur. Sonuç yine zincir, yükseklik 5. Kötü ağaç için sıralı girdi şart değil.

Silme (remove): üç durum

Silinecek düğümü önce arayarak bul. Sonra çocuk sayısına bak. Aşağıdaki üç örneğin her biri orijinal ağaçtan başlıyor.

Durum 1: yaprak

Ebeveynin ilgili referansını null yap. 20’yi silmek: 30’un solu null olur. Başka hiçbir şey değişmez.

Durum 2: tek çocuk

Düğümü atla: ebeveyni doğrudan torunu göstersin. 60’ın tek çocuğu 65. 60 silinince 70’in solu 65 olur.

önce:  70            sonra:  70
      /  \                  /  \
    60    80              65    80
      \
       65

BST özelliği bozulmaz: 65 zaten 70’in sol alt ağacındaydı, orada kalıyor.

Durum 3: iki çocuk

Düğümü doğrudan kaldıramazsın, iki alt ağacı tek bir ebeveyn referansına bağlayamazsın. Çözüm: düğümün değerini, sıralamada ona en yakın değerle değiştir. Bu derste kullanılan kural: inorder successor, yani sağ alt ağacın en küçüğü.

1. Sağ alt ağaçta hep sola in, en küçüğü bul.
2. O değeri silinecek düğüme kopyala.
3. O değeri sağ alt ağaçtan sil. Sağ alt ağacın minimumunun sol çocuğu olamaz, bu yüzden bu ikinci silme hep durum 1 ya da 2’dir.

30’u silelim. 30’un iki çocuğu var (20 ve 40). Sağ alt ağacı (40, 35, 45), en küçüğü 35. 35 yukarı kopyalanır, 35 yaprağı silinir:

            50
          /    \
        35      70
       /  \    /  \
     20   40  60   80
            \   \
            45   65

Program çıktısı: 50(35(20,40(-,45)),70(60(-,65),80)).

Şimdi orijinal ağaçta kökü (50) silelim. Sağ alt ağacın en küçüğü: 70 → 60, 60’ın solu yok, successor 60. 60 köke kopyalanır. Eski 60’ın tek çocuğu 65 olduğu için ikinci silme durum 2: 65, 70’in sol çocuğu olur.

            60
          /    \
        30      70
       /  \    /  \
     20   40  65   80
         /  \
       35    45

İPUCU · predecessor de olur. Sol alt ağacın en büyüğü (inorder predecessor) ile de silme doğru çalışır. Sınavda hangi kural istendiği yazmıyorsa successor kullan ve bunu cevabına not düş.

Inorder successor

x’ten büyük en küçük anahtar. İki durum:

1. x’in sağ alt ağacı varsa: o alt ağacın minimumu. Ana ağaçta successor(30) = 35.
2. Yoksa: yukarı çık; x’e sol tarafından indiğin ilk ata successor. successor(45): 45, 40’ın sağı; 40, 30’un sağı; 30, 50’nin solu. Cevap 50.

Ebeveyn referansı yoksa kökten arayarak bulunur: x’i ararken sola döndüğün her düğümü “aday” olarak kaydet, son aday successor.

static Integer successor(Node root, int x) {
    Node t = root, succ = null;
    while (t != null) {
        if (x < t.element) { succ = t; t = t.left; }
        else t = t.right;
    }
    return succ == null ? null : succ.element;
}

En büyük anahtarın (80) successor’ı yoktur. Predecessor simetriktir: sol alt ağacın maksimumu ya da sağ tarafından geldiğin ilk ata.

Yükseklik ve karmaşıklık

n düğümlü ağacın yüksekliği $\lfloor \log_2 n \rfloor$ ile $n - 1$ arasında. Anahtarlar rastgele sırayla eklenirse ortalama derinlik yaklaşık $1.39 \log_2 n$, yani beklenen maliyet $O(\log n)$. Ama “rastgele” garanti değil. Garanti isteyen 5. ve 6. haftadaki dengeli ağaçlara (AVL, red-black) geçer.

Sık yapılan hatalar

          45
        /    \
      22      67
     /  \    /  \
   10   30  55   80
        /     \
      27       60

          45
        /    \
      22      67
     /  \    /  \
   10   27  55   80
              \
               60

          55
        /    \
      22      67
     /  \    /  \
   10   30  60   80
        /
      27

        55
      /    \
    27      67
   /  \    /  \
 10   30  60   80

        50
       /  \
     30    70
    /  \   /
  20   55 60