Binary Search Tree Sınav Soruları: Ekleme, Silme, Dolaşma

Binary search tree (BST, ikili arama ağacı), sıralı veriyi ekleme ve silme yaparken de sıralı tutan, dengeli kaldığı sürece arama, ekleme ve silmeyi O(log n) adımda yapan bir veri yapısıdır. Veri yapıları dersinin vize ve finalinde en çok çizim sorusu çıkan konudur: "şu anahtarları ekleyin, şunu silin, ağacı çizin, preorder'ını yazın". Bu yazıda kuralları kısa tutup ağırlığı elle çözülmüş sorulara veriyorum. Her ağaç ve her dolaşma sonucu hem elle hem de aşağıdaki kod çalıştırılarak doğrulandı.

BST Özelliği

Her düğüm için şu kural geçerlidir: sol alt ağaçtaki bütün anahtarlar düğümün anahtarından küçük, sağ alt ağaçtaki bütün anahtarlar büyüktür. Kural yalnızca doğrudan çocuklar için değil, tüm alt ağaç için geçerlidir; bu ayrım Soru 6'da karşına çıkacak. Yazı boyunca kullanacağım ağaç, 50, 30, 70, 20, 40, 60, 80 anahtarlarının bu sırayla eklenmesiyle oluşuyor:

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80

Eşit anahtarların ne olacağı derse göre değişir (eklenmez, sağa gider ya da sayaç tutulur). Bu yazıda eşit anahtar eklenmiyor; sınavda hocanın kuralını kullan.

Düğüm, Ekleme ve Arama

Düğüm sıradan bir sınıftır; sınıf ve referans mantığını tazelemek istersen C# sınıf ve nesne kavramı yazısına bakabilirsin.

public class Node
{
    public int Key;
    public Node? Left, Right;
    public Node(int key) => Key = key;
}

public static class Bst
{
    public static Node Insert(Node? node, int key)
    {
        if (node == null) return new Node(key);
        if (key < node.Key) node.Left = Insert(node.Left, key);
        else if (key > node.Key) node.Right = Insert(node.Right, key);
        return node; // eşit anahtar: eklenmez
    }

    public static bool Search(Node? node, int key)
    {
        while (node != null)
        {
            if (key == node.Key) return true;
            node = key < node.Key ? node.Left : node.Right;
        }
        return false;
    }
}

Ekleme de arama da kökten başlar, her düğümde küçükse sola, büyükse sağa gider. Yeni anahtar her zaman bir yaprak olarak eklenir; var olan düğümlerin yeri değişmez. Kullanım: Node? root = null; root = Bst.Insert(root, 50);.

Silme: Üç Durum

1. Yaprak düğüm: doğrudan kaldırılır.
2. Tek çocuklu düğüm: çocuğu, silinen düğümün yerine geçer.
3. İki çocuklu düğüm: düğümün anahtarı, inorder ardılıyla (sağ alt ağacın en küçüğü) değiştirilir, sonra ardıl sağ alt ağaçtan silinir. Ardılın sol çocuğu olamayacağı için bu ikinci silme her zaman 1. ya da 2. duruma düşer.

// Bst sınıfının içine
public static Node? Delete(Node? node, int key)
{
    if (node == null) return null;
    if (key < node.Key) node.Left = Delete(node.Left, key);
    else if (key > node.Key) node.Right = Delete(node.Right, key);
    else
    {
        if (node.Left == null) return node.Right;  // yaprak ya da yalnız sağ çocuk
        if (node.Right == null) return node.Left;  // yalnız sol çocuk
        Node successor = node.Right;
        while (successor.Left != null) successor = successor.Left;
        node.Key = successor.Key;
        node.Right = Delete(node.Right, successor.Key);
    }
    return node;
}

Bazı dersler ardıl yerine inorder öncülü (sol alt ağacın en büyüğü) kullanır. İkisi de geçerli bir BST üretir ama ağaçlar farklı çıkar; soruda hangisi isteniyorsa onu kullan, belirtilmemişse seçimini cevabına yaz.

Dolaşma Yöntemleri

// Bst sınıfının içine
public static void Inorder(Node? node, List<int> output)
{
    if (node == null) return;
    Inorder(node.Left, output);
    output.Add(node.Key);        // preorder için bu satır en başa, postorder için en sona gelir
    Inorder(node.Right, output);
}

public static List<int> LevelOrder(Node? root)
{
    var result = new List<int>();
    if (root == null) return result;
    var queue = new Queue<Node>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        Node current = queue.Dequeue();
        result.Add(current.Key);
        if (current.Left != null) queue.Enqueue(current.Left);
        if (current.Right != null) queue.Enqueue(current.Right);
    }
    return result;
}

Yukarıdaki ağaç için sonuçlar:

Dolaşma	Sıra	Sonuç
Inorder	sol, kök, sağ	20 30 40 50 60 70 80
Preorder	kök, sol, sağ	50 30 20 40 70 60 80
Postorder	sol, sağ, kök	20 40 30 60 80 70 50
Level-order	seviye seviye, soldan sağa	50 30 70 20 40 60 80

Bir BST'nin inorder dolaşması her zaman sıralı çıkar; sınavda çizdiğin ağacı kontrol etmenin en hızlı yolu budur. Preorder'da kök hep ilk, postorder'da hep son elemandır.

Yükseklik, Denge ve Dejenere Durum

Yükseklik, kökten en derin yaprağa giden yoldaki kenar sayısıdır; tek düğümlü ağacın yüksekliği 0, boş ağacınki −1 kabul edilir. Bazı dersler düğüm sayar ve her değer 1 fazla çıkar; tanımı kontrol et.

// Bst sınıfının içine
public static int Height(Node? node) =>
    node == null ? -1 : 1 + Math.Max(Height(node.Left), Height(node.Right));

Bütün işlemler kökten aşağı tek bir yol izlediği için maliyet O(h)'dir. n düğümlü bir ağaçta h en az ⌊log₂ n⌋, en çok n − 1 olabilir. Anahtarlar sıralı gelirse (Soru 5) ağaç bağlı listeye döner ve O(log n) beklentisi O(n)'e çıkar.

İşlem	Ortalama	En kötü (dejenere)
Arama	O(log n)	O(n)
Ekleme	O(log n)	O(n)
Silme	O(log n)	O(n)
En küçük / en büyük	O(log n)	O(n)
Dolaşma (hepsi)	O(n)	O(n)
Bellek	O(n) düğüm; özyinelemede O(h) yığın	O(n)

Notasyon yabancı geliyorsa Big O ve zaman karmaşıklığı rehberi bu tablonun nasıl okunacağını anlatıyor.

Soru 1: Ekle, Sonra 30'u Sil

Soru: Boş bir BST'ye sırasıyla 50, 30, 70, 20, 40, 60, 80 ekleyin. Ardından 30'u silin ve ağacı çizin (inorder ardıl kullanın).

Çözüm: 50 kök olur. 30 < 50 sola, 70 > 50 sağa gider. 20: 50'den küçük, 30'dan küçük, 30'un soluna. 40: 50'den küçük, 30'dan büyük, 30'un sağına. 60 ve 80 aynı mantıkla 70'in soluna ve sağına yerleşir; sonuç yazının başındaki ağaçtır.

30'un iki çocuğu var. Ardıl, sağ alt ağacın en küçüğüdür; sağ alt ağaç yalnızca 40'tan oluştuğu için ardıl 40'tır. 30'un yerine 40 yazılır, eski 40 yaprağı silinir:

        50
      /    \
    40      70
   /       /  \
  20      60  80

Kontrol: inorder 20 40 50 60 70 80, sıralı. Öncül kullanılsaydı 30'un yerine 20 gelir, 40 onun sağ çocuğu olarak kalırdı.

Soru 2: Dört Dolaşmayı Yazın

Soru: Soru 1'de silme yapılmadan önceki ağacın inorder, preorder, postorder ve level-order dolaşmalarını yazın.

Çözüm: Preorder'ı adım adım yapalım: kök 50 yazılır; sol alt ağaca geçilir: 30, onun solu 20, sağı 40; sonra sağ alt ağaç: 70, 60, 80. Sonuç 50 30 20 40 70 60 80. Postorder'da her düğüm iki alt ağacından sonra yazılır: 20 40 30, sonra 60 80 70, en son 50. Dört sonucun tamamı yukarıdaki tabloda.

Silmeden sonraki ağaç için aynı soru gelirse: preorder 50 40 20 70 60 80, postorder 20 40 60 80 70 50, level-order 50 40 70 20 60 80.

Soru 3: Kökü Silmek ve Çocuklu Ardıl

Soru: İlk ağaca 65 ekleyin, sonra kök 50'yi silin.

Çözüm: 65 > 50 sağa, 65 < 70 sola, 65 > 60 sağa: 60'ın sağ çocuğu olur.

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

50'nin ardılı için sağ alt ağaçta hep sola gidilir: 70, sonra 60; 60'ın sol çocuğu yok, ardıl 60. Köke 60 yazılır. Şimdi eski 60 düğümü silinmeli; tek (sağ) çocuğu var, yani 2. durum: 65 onun yerine, 70'in sol çocuğu olarak geçer.

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

Kontrol: inorder 20 30 40 60 65 70 80. Bu soruda en sık yapılan hata 65'i unutup ağaçtan düşürmektir.

Aynı ağaçta diğer iki durum da görülebilir: 20 yapraktır, doğrudan kaldırılır. 60 silinirse (50 silinmeden önceki ağaçta) tek çocuğu 65, 70'in sol çocuğu olur.

Soru 4: Preorder'dan BST Kurmak

Soru: Preorder dolaşması 40, 20, 10, 30, 25, 60, 50, 70 olan BST'yi çizin ve postorder'ını yazın.

Çözüm: Preorder'da ilk eleman köktür: 40. Geri kalanlarda 40'tan küçükler (20, 10, 30, 25) sol alt ağacı, büyükler (60, 50, 70) sağ alt ağacı oluşturur. Aynı kural özyinelemeli uygulanır: solda kök 20, küçük olan 10 solda, büyükler 30 ve 25 sağda; orada kök 30, 25 onun solunda. Sağda kök 60, 50 solda, 70 sağda.

          40
        /    \
      20      60
     /  \    /  \
   10   30  50  70
        /
      25

Postorder: 10 25 30 20 50 70 60 40. Yükseklik 3'tür. Pratik kısayol: anahtarları preorder sırasıyla boş bir BST'ye eklemek aynı ağacı verir. Genel bir ikili ağaçta tek bir dolaşma ağacı belirlemeye yetmez; BST'de yeter, çünkü inorder zaten bellidir (sıralı hali).

Soru 5: Sıralı Ekleme ve Dejenere Ağaç

Soru: Boş BST'ye 10, 20, 30, 40, 50 sırasıyla eklenirse ağacın yüksekliği ne olur? 50'yi aramak kaç karşılaştırma gerektirir? Aynı anahtarlar 30, 20, 40, 10, 50 sırasıyla eklenseydi?

Çözüm: Her yeni anahtar öncekilerin hepsinden büyük olduğu için hep sağa gider:

10
  \
   20
     \
      30
        \
         40
           \
            50

Yükseklik 4 (n − 1), 50'yi bulmak için 5 düğümle karşılaştırma yapılır; yapı fiilen bağlı listedir. İkinci sırada 30 kök olur, 20 ve 40 çocukları, 10 ve 50 onların altına yerleşir: yükseklik 2, 50 için 3 karşılaştırma (30, 40, 50). Aynı anahtar kümesi, farklı ekleme sırası, farklı ağaç. AVL ve kırmızı-siyah ağaçlar bu sorunu her eklemeden sonra döndürmelerle dengeleyerek çözer.

Soru 6: Bu Ağaç Bir BST mi?

Soru: Aşağıdaki ağaç BST midir?

        50
      /    \
    30      70
   /  \
  20  55

Çözüm: Hayır. Her düğüm kendi çocuklarıyla karşılaştırıldığında sorun görünmez: 20 < 30 < 55 ve 30 < 50 < 70. Ama 55, 50'nin sol alt ağacında ve 50'den büyük; kural tüm alt ağaç için geçerlidir. Hızlı kontrol: inorder 20 30 55 50 70 sıralı değil. Kodda doğru kontrol, her düğüme izin verilen aralığı taşımaktır:

// Bst sınıfının içine; çağrı: IsBst(root, long.MinValue, long.MaxValue)
public static bool IsBst(Node? node, long min, long max)
{
    if (node == null) return true;
    if (node.Key <= min || node.Key >= max) return false;
    return IsBst(node.Left, min, node.Key) && IsBst(node.Right, node.Key, max);
}

Soru 7: Arama Yolu ve Yükseklik Sınırları

Soru: (a) Soru 3'teki 8 düğümlü ağaçta (50 silinmeden önce) 65 ve 45 aranırken hangi düğümler ziyaret edilir? (b) 7 düğümlü bir BST'nin yüksekliği en az ve en çok kaç olabilir?

Çözüm (a): 65 için 50, 70, 60, 65: dört karşılaştırma, bulundu. 45 için 50, 30, 40; 40'ın sağ çocuğu yok, arama üç karşılaştırmayla başarısız biter. Başarısız aramanın bittiği boş konum, 45 eklenseydi yerleşeceği konumdur.

Çözüm (b): En az 2: yüksekliği h olan bir ağaç en fazla 2^(h+1) − 1 düğüm alır, h = 2 için bu tam 7'dir (yazının başındaki ağaç). En çok 6: sıralı eklemede her düğüm tek çocukludur, yükseklik n − 1 olur.

Ne Zaman Kullanılır, Ne Zaman Kullanılmaz?

BST'yi veri hem değişiyor hem de sıralı erişim gerekiyorsa seç: en küçük/en büyük eleman, belirli bir aralıktaki anahtarlar, bir anahtarın ardılı, sıralı listeleme. Yalnızca "bu anahtar var mı?" sorusu soruluyorsa hash tablosu (Dictionary, HashSet) ortalamada O(1) ile daha iyi bir seçimdir ama sıra bilgisini tutmaz. Veri hiç değişmiyorsa sıralı bir dizi üzerinde binary search daha az bellekle aynı O(log n) aramayı verir; diziyi bir kez sıralamanın maliyeti için sıralama algoritmaları yazısına bakabilirsin.

Üretim kodunda dengesiz bir BST'yi elle yazmak nadiren doğrudur; girdi sıralı gelirse performans çöker. .NET'te SortedSet<T> ve SortedDictionary<TKey, TValue> dengeli ikili arama ağacı üzerine kuruludur ve O(log n) garantisi verir. Elle yazılmış BST'nin değeri, bu yapıların nasıl çalıştığını anlamaktır; sınavın ölçtüğü de budur.

Sık Yapılan Hatalar

1. Özyinelemenin sonucunu atamamak. Insert(node.Left, key); yazıp dönüş değerini node.Left'e atamazsan yeni düğüm oluşturulur ama ağaca bağlanmaz. Belirti: hata yok, ama ağaç hiç büyümüyor ve inorder yalnızca kökü yazdırıyor.

if (key < node.Key) Insert(node.Left, key);             // YANLIŞ: yeni düğüm kaybolur
if (key < node.Key) node.Left = Insert(node.Left, key); // DOĞRU

2. BST kontrolünde yalnızca çocuklara bakmak. Soru 6'daki ağaç bu kontrolden geçer ama BST değildir. Aralık taşıyan IsBst ya da inorder'ın sıralı olup olmadığı kontrol edilmelidir.

3. İki çocuklu silmede ardılı silmeyi unutmak. Anahtar kopyalanır ama eski ardıl düğüm yerinde kalırsa aynı anahtar ağaçta iki kez görünür; inorder'da ... 40 40 ... gibi bir tekrar bunun işaretidir. Ardılın sağ çocuğu varsa (Soru 3) onun yukarı bağlanması da bu adımın parçasıdır.

4. Ardıl ile öncülü karıştırmak. Ardıl sağ alt ağacın en solundaki, öncül sol alt ağacın en sağındaki düğümdür. "Sağa bir adım, sonra hep sola" diye ezberlemek işe yarar.

Çizim sorularını kendi dersinin çıkmış sınavlarıyla çalışmak istersen sınav destek sayfasında nasıl ilerlediğimi anlattım.

Sık Sorulan Sorular

BST ile binary tree arasındaki fark nedir?

Binary tree yalnızca her düğümün en fazla iki çocuğu olduğunu söyler, anahtarların sırası hakkında bir kural koymaz. BST buna sıralama kuralını ekler: sol alt ağaç küçük, sağ alt ağaç büyük anahtarları içerir.

İki çocuklu düğüm silinirken ardıl mı öncül mü kullanılmalı?

İkisi de doğrudur ve geçerli bir BST bırakır, ama ortaya çıkan ağaçlar farklıdır. Sınavda dersin kullandığı yöntemi uygula; belirtilmemişse hangisini seçtiğini cevabına yaz.

BST'de aynı anahtar iki kez eklenebilir mi?

Tanıma bağlıdır. Yaygın seçenekler eklemeyi reddetmek, eşit anahtarı tutarlı biçimde sağ alt ağaca göndermek ya da düğümde sayaç tutmaktır. Hangisi seçilirse arama ve silme de aynı kurala uymalıdır.

AVL ağacı ile BST arasındaki fark nedir?

AVL ağacı, her düğümde sol ve sağ alt ağaç yükseklikleri arasındaki farkı en fazla 1'de tutan bir BST'dir. Ekleme ve silmeden sonra döndürmelerle kendini dengeler, böylece en kötü durumda da O(log n) garantisi verir.