Bölüm 10: Arama Ağaçları

Bölüm 10: Arama Ağaçları · Çalışma Soruları
BST özelliği ve gezinmeArama, ekleme, ardılSilme ve analizAralık sorgusu ve doğrulamaAVL ağaçlarıKırmızı-siyah ağaçlarSplay ağaçlarıB-ağacı ve B+ ağacı
Sercan KÜLCÜ · Giresun Üniversitesi · Bilgisayar Mühendisliği

Çoktan Seçmeli · Arama Ağaçları

Soru 1: BST Özelliği

Ağaçlar kök(sol, sağ) biçiminde yazılmıştır (— : boş). Aşağıdakilerden hangisi bir ikili arama ağacı değildir?

C: 12, 5'in sağında olduğu için 5'ten büyük olması yetmez; 10'un sol alt ağacında olduğu için 10'dan küçük de olmalıdır. BST özelliği yalnızca çocuklar için değil, bütün alt ağaç için geçerlidir. B'deki 7 ise hem 5'ten büyük hem 10'dan küçüktür, geçerlidir.

Çoktan Seçmeli · Arama Ağaçları

Soru 2: Hatalı minDeger

minDeger şöyle yazılmıştır. Boş olmayan bir ağaçta minDeger(kok) ne döndürür?

IkiliAgacDugum<E> minDeger(
        IkiliAgacDugum<E> dugum) {
    while (dugum != null)
        dugum = dugum.solCocuk;
    return dugum;
}

Döngü dugum null olana kadar sürer: en soldaki düğümü de geçip null döndürür. null'un alanına erişilmediği için istisna oluşmaz (C yanlış). Doğrusu while (dugum.solCocuk != null): en küçük, sol çocuğu olmayan en soldaki düğümdür; O(h).

Çoktan Seçmeli · BST İşlemleri

Soru 3: == ile Karşılaştırma

Ağaca ekle ile sırasıyla 1000, 100, 2000 eklenmiştir. Aşağıdaki arama ne yazdırır?

boolean ara(IkiliAgacDugum<Integer> kok,
            Integer veri) {
    if (kok == null) return false;
    if (veri == kok.veri) return true;
    if (veri.compareTo(kok.veri) < 0)
        return ara(kok.solCocuk, veri);
    return ara(kok.sagCocuk, veri);
}
System.out.println(ara(kok, 1000));

== Integer nesnelerinin referanslarını karşılaştırır: ayrı ayrı kutulanan iki 1000 farklı nesnedir. compareTo 0 döndüğü için kod sağa (2000) iner, 2000'in solundaki null'a varır → false. Doğrusu: k = veri.compareTo(kok.veri), k == 0 ise bulundu.

Klasik Soru · BST İşlemleri

Soru 4: Ekleme Sırası ve Ağaç

Boş bir BST'ye sırasıyla 45, 20, 70, 10, 30, 60, 90, 25, 65, 27 ekleniyor. Son ağacı çizin ve yüksekliğini bulun.

Cevabı göster
10202527304560657090

Her anahtar kökten iner (küçükse sol, büyükse sağ) ve düştüğü null konuma yaprak olarak eklenir. Örn. 27: 45 → 20 → 30 → 25 → 25'in sağı.

Yükseklik 4 (45–20–30–25–27 yolu).

Kontrol, kök ortada: 10 20 25 27 30 45 60 65 70 90

Klasik Soru · BST İşlemleri

Soru 5: Dönüş Değerini Atamamak

Sunumdaki ekle metodu (yeni alt ağaç kökünü döndürür) aşağıdaki gibi kullanılıyor. Çıktı ne olur? Gerekçelendirin.

IkiliAgacDugum<Integer> kok = null;
ekle(kok, 8);
ekle(kok, 3);
ekle(kok, 12);
inorder(kok);
Cevabı göster

Hiçbir şey yazdırılmaz; ağaç boş kalır. Java'da parametre değerle geçer: ekle(null, 8) yeni düğümü döndürür ama sonuç atanmadığı için kaybolur, kok hep null kalır.

Doğrusu: kok = ekle(kok, 8); (sil için de aynı).

Boş olmayan ağaçta atamasız çağrı çoğu zaman çalışıyor gibi görünür, çünkü yeni yaprak iç çağrıda kok.solCocuk = … ile bağlanır. Ancak kökün değiştiği durumlarda (boş ağaç, kökün silinmesi, dengeli ağaçta kökte döndürme) ağaç bozulur.

Klasik Soru · BST İşlemleri

Soru 6: Ardıl, Öncül, Tavan, Taban

Şekildeki BST için ardil(45), oncul(50), tavan(38) ve taban(38) değerlerini bulun; her birinde hangi kuralı izlediğinizi belirtin.

20303540455060657080
Cevabı göster
  • ardil(45) = 50: 45'in sağ alt ağacı yok → solundan geçtiğimiz en yakın ata (45, 50'nin sol alt ağacında).
  • oncul(50) = 45: sol alt ağacın en büyüğü: bir sola (30), sonra hep sağa → 40 → 45.
  • tavan(38) = 40: ≥ 38 olan en küçük anahtar (38 ağaçta yok).
  • taban(38) = 35: ≤ 38 olan en büyük anahtar.

Hepsi kökten tek bir yol izler: O(h). TreeMap karşılıkları: higherKey, lowerKey, ceilingKey, floorKey.

Adım Adım Çalıştırma · BST İşlemleri

Soru 7: ardil() İzleme

Şekildeki ağaçta ardil(kok, 62) (62 ağaçta yok) hangi düğümü döndürür?

20303540455060657080
20303540455060657080

Henüz aday yok; kökten (50) başlanır.

20303540455060657080

62 ≥ 50 → 50 ve solundakiler ardıl olamaz; sağa in.

20303540455060657080

62 < 70 → 70 bir aday; daha küçük aday ancak solda olabilir → sola in.

20303540455060657080

62 ≥ 60 → sağa in.

20303540455060657080

62 < 65 → aday = 65 (70'ten daha iyi); sola in: kok = null.

20303540455060657080

Döngü biter → return 65. 4 düğüm ziyaret edildi: O(h).

AgacDugumu ardil(AgacDugumu kok, int x) {
    AgacDugumu aday = null;
    while (kok != null) {
        if (x < kok.veri) {
            aday = kok;     // aday
            kok = kok.sol;  // sola
        } else
            kok = kok.sag;  // sağa
    }
    return aday;
}
System.out.println(ardil(kok, 62).veri);

Klasik Soru · BST İşlemleri

Soru 8: Silme: Üç Durum

Şekildeki BST'den sırasıyla 20, 30 ve 50 siliniyor (iki çocuklu düğümde kök ortada ardıl kullanılıyor). Her silmenin hangi durum olduğunu yazın ve son ağacı çizin.

20303540455060657080
Cevabı göster
  • sil 20: yaprak → 30'un sol bağı null olur.
  • sil 30: artık yalnız sağ çocuğu (40) var → tek çocuk: 50, doğrudan 40'a bağlanır.
  • sil 50: iki çocuk → ardıl = sağ alt ağacın en küçüğü 60; 60 köke kopyalanır, eski 60 (tek çocuğu 65) silinir → 65, 70'in solu olur.
35404560657080

Kök ortada: 35 40 45 60 65 70 80

Çoktan Seçmeli · BST İşlemleri

Soru 9: Ardılın Çocukları

İki çocuklu bir düğüm silinirken yerine kopyalanan kök ortada ardılın kendisinin silinmesi neden her zaman yaprak ya da tek çocuk durumuna iner?

minDeger hep sola iner ve sol çocuğu olmayan düğümde durur. Ardılın sağ çocuğu olabilir, bu yüzden B ve D yanlıştır; ardıl daha derinde de olabilir (C yanlış). Öncül kullanılırsa simetrik olarak sağ çocuğu yoktur.

Adım Adım Çalıştırma · BST İşlemleri

Soru 10: aralik() İzleme

Şekildeki ağaçta aralik(kok, 38, 62) ne yazdırır ve hangi düğümler hiç ziyaret edilmez?

20303540455060657080
20303540455060657080

38 < 50 → solda aralığa giren anahtar olabilir: sola in.

20303540455060657080

38 < 30 yanlış → sol alt ağaç (20) budanır. 30 aralık dışında. 30 < 62 → sağa.

20303540455060657080

38 < 40 → sola in.

20303540455060657080

35: solu budanır, aralık dışında; 35 < 62 → sağa (null), hemen döner.

20303540455060657080

40'a dönüldü: 40 ∈ [38, 62] → yazdır.

20303540455060657080

40 < 62 → sağa: 45. Solu boş; 45 ∈ aralık → yazdır. Sağı da boş.

20303540455060657080

45, 40 ve 30 çerçeveleri kapanır; 50'ye dönüldü: 50 ∈ aralık → yazdır.

20303540455060657080

50 < 62 → sağa: 70. 38 < 70 → sola in.

20303540455060657080

60: solu boş; 60 ∈ aralık → yazdır. 60 < 62 → sağa.

20303540455060657080

65 aralık dışında; 65 < 62 yanlış → sağı budanır.

20303540455060657080

70'e dönüldü: aralık dışında; 70 < 62 yanlış → 80 budanır.

20303540455060657080

Çıktı sıralı: 40 45 50 60. 20 ve 80 hiç ziyaret edilmedi → O(h + s).

void aralik(AgacDugumu k, int lo, int hi) {
    if (k == null) return;
    if (lo < k.veri)           // solda aday
        aralik(k.sol, lo, hi);
    if (lo <= k.veri && k.veri <= hi)
        System.out.print(k.veri + " ");
    if (k.veri < hi)           // sağda aday
        aralik(k.sag, lo, hi);
}

Çoktan Seçmeli · Denge ve AVL

Soru 11: Mükemmel Ağaç İçin Sıra

1, 2, …, 7 anahtarları boş bir BST'ye hangi sırayla eklenirse yüksekliği 2 olan (mükemmel) ağaç oluşur?

Önce orta (4), sonra her yarının ortası (2, 6), en son yapraklar. B'de 1–2–3 ve 5–6–7 birer zincir olur (h = 3); C'de kök 2 olduğu için sağ taraf ağırdır (h = 3); A, h = 6 olan zincirdir. BST'nin şekli ekleme sırasına bağlıdır.

Klasik Soru · Denge ve AVL

Soru 12: Denge Faktörü ve Döndürme

Şekil, bir AVL ağacına 27 eklendikten hemen sonraki (henüz dengelenmemiş) hâli gösteriyor. Denge faktörlerini hesaplayarak hangi düğümde hangi döndürmenin yapılacağını belirleyin ve sonucu çizin.

101517202527304050
Cevabı göster

bf = h(sol) − h(sağ), boş alt ağaç −1. 27'den köke: bf(25) = −1, bf(20) = 0 − 1 = −1, bf(15) = 0 − 2 = −2 ✗, bf(30) = 3 − 1 = 2 ✗.

Düzeltilen, en alttaki dengesiz düğüm 15: sağ ağır ve sağ çocuğu 20'de bf = −1 (aynı yön) → RR: 15'te sola döndürme.

101517202527304050

Alt ağacın yüksekliği eski değerine (2) döndüğü için 30 da dengelenir (bf = 1).

Çoktan Seçmeli · Denge ve AVL

Soru 13: Hangi Döndürme?

Boş bir AVL ağacına sırasıyla 50, 20, 30 ekleniyor. Hangi durum oluşur ve ağaç nasıl dengelenir?

bf(50) = 2 (sol ağır) ama sol çocuk 20'de bf = −1 (sağa eğik): zikzak (üçgen) → LR. Tek sağa döndürme (A) 20(—, 50(30, —)) verir, bf(20) = −2 olur; yine dengesizdir. Doğru sonuç 30(20, 50).

Klasik Soru · Denge ve AVL

Soru 14: AVL'ye Ekleme Dizisi

Boş bir AVL ağacına sırasıyla 40, 20, 10, 25, 30, 22, 50 ekleniyor. Her dengesizlikte durumu (LL, RR, LR, RL) ve yapılan döndürmeleri yazın, son ağacı çizin.

Cevabı göster
  • +10: bf(40) = 2, bf(20) = 1 → LL: 40'ta sağa → 20(10, 40).
  • +25: 40'ın solu; dengesizlik yok.
  • +30: 25'in sağı; bf(40) = 2, bf(25) = −1 → LR: 25'te sola, 40'ta sağa → 20(10, 30(25, 40)).
  • +22: 25'in solu; bf(20) = −2, bf(30) = 1 → RL: 30'da sağa, 20'de sola → 25(20(10, 22), 30(—, 40)).
  • +50: bf(30) = −2, bf(40) = −1 → RR: 30'da sola.
10202225304050

Son ağaç: dört durumun hepsi görüldü; h = 2.

Çoktan Seçmeli · Kırmızı-Siyah Ağaçlar

Soru 15: Kural İhlali

Şekildeki ağaçta koyu düğümler siyah, 40 kırmızıdır; boş çocuklar (NIL) siyah sayılır. Ağaç hangi kırmızı-siyah ağaç kuralını ihlal eder?

1020253040

20 → 10 → NIL yolunda 2 siyah (20, 10), 20 → 30 → 25 → NIL yolunda 3 siyah (20, 30, 25) var. Tek kırmızı düğüm 40'ın çocukları NIL (siyah), kök siyah. 25 kırmızı yapılırsa her yolda 2 siyah olur ve ağaç geçerli hâle gelir.

Klasik Soru · Kırmızı-Siyah Ağaçlar

Soru 16: Kırmızı-Siyah Ağaca Ekleme

Boş bir kırmızı-siyah ağaca sırasıyla 50, 40, 30, 35, 45, 32 ekleniyor. Düzeltme gerektiren her eklemede uygulanan durumu yazın ve son ağacı renkleriyle çizin.

Cevabı göster
  • 50: kök → siyah. 40: ebeveyn siyah, işlem yok.
  • 30: ebeveyn 40 kırmızı, amca NIL (siyah), 30–40–50 çizgi → 50'de sağa döndür; 40 siyah, 50 kırmızı.
  • 35: ebeveyn 30 kırmızı, amca 50 kırmızı → renk değiştir: 30, 50 siyah, 40 kırmızı; 40 kök olduğu için yeniden siyah.
  • 45: ebeveyn 50 siyah, işlem yok.
  • 32: ebeveyn 35 kırmızı, amca NIL; 32–35–30 üçgen → 35'te sağa (çizgi olur), sonra 30'da sola döndür; 32 siyah, 30 kırmızı.
303235404550

Her yolda 2 siyah düğüm; ardışık kırmızı yok.

Çoktan Seçmeli · Kırmızı-Siyah Ağaçlar

Soru 17: AVL mi Kırmızı-Siyah mı?

İşlemlerinin %95'i arama olan, nadiren güncellenen büyük bir sözlük için hangi seçim en uygundur?

İkisi de O(log n) verir; AVL daha kısa ağaç kurar, güncellemelerin pahalı olması (silmede O(log n) döndürme) nadir güncellemede önemsizdir. A tersini söylüyor: kırmızı-siyah daha gevşek dengelidir; ucuz güncellemesi (≤ 2–3 döndürme, 1 bit renk) yüzünden sık güncellenen yapılarda ve kütüphanelerde (TreeMap, std::map) tercih edilir.

Adım Adım Çalıştırma · Splay Ağaçları

Soru 18: splay() İzleme

Şekildeki splay ağacında 10'a erişiliyor. splay(10) hangi adımlarla çalışır ve son ağaç ne olur?

102030405060
102030405060

x kök değil. p = 20, g = 30.

102030405060

g var; x ve p ikisi de sol çocuk → aynı yön: zig-zig.

102030405060

Önce dede: 30'da sağa döndür → 20 yukarı çıkar.

102030405060

Sonra ebeveyn: 20'de sağa döndür → x iki düzey yükseldi.

102030405060

x hâlâ kök değil. p = 50 kök, g = null.

102030405060

g == null → zig: 50'de sağa döndür; 10 kök olur, eski sağı (20…) 50'nin soluna geçer.

102030405060

x == kok → döngü biter. Zig yalnızca son adımda olur; zig-zig'de önce dede döndürülür.

void splay(Dugum x) {
    while (x != kok) {
        Dugum p = x.ebeveyn, g = p.ebeveyn;
        if (g == null)  // zig
            dondur(p, x);
        else if (ayniYon(x, p, g)) {
            dondur(g, p); // önce dede
            dondur(p, x);
        } else { // zig-zag
            dondur(p, x);
            dondur(g, x);
        }
    }
}

Klasik Soru · Çok Yollu Arama Ağaçları

Soru 19: B-Ağacına Ekleme

Boş, derecesi m = 3 olan bir B-ağacına (düğüm başına en çok 2 anahtar) sırayla 40, 10, 30, 20, 50, 60, 70, 80 ekleniyor. Son ağacı çizin; kök kaç kez bölünür?

Cevabı göster
  • 30: [10 30 40] taşar → ortanca 30 yeni kök, [10] ve [40] (1. kök bölünmesi).
  • 20 → [10 20]; 50 → [40 50]; 60: [40 50 60] taşar → 50 köke çıkar: kök [30 50].
  • 70 → [60 70]; 80: [60 70 80] taşar → 70 yukarı, kök [30 50 70] taşar → 50 yeni kök (2. kök bölünmesi).
50307010 20406080

Kök 2 kez bölündü; yükseklik yalnızca kök bölününce arttı ve tüm yapraklar aynı derinlikte kaldı. B-ağacı aşağıdan yukarı büyür.

Çoktan Seçmeli · Çok Yollu Arama Ağaçları

Soru 20: B+ Ağacında Aralık Sorgusu

Bir veritabanı indisinde “20 ile 50 arası” gibi aralık sorguları sık yapılıyor. Bu iş için B+ ağacını B-ağacından üstün kılan özellik hangisidir?

D. Alt sınır 20 içeren yaprak O(log n) ile bulunur, sonra yukarı çıkmadan yaprak zinciri izlenir: toplam O(log n + k), k = sonuç sayısı. A, B-ağacının özelliğidir; B+ ağacında iç düğümler yalnızca yönlendirme anahtarı tutar, bu yüzden bir bloğa daha çok anahtar sığar ve ağaç daha alçaktır.

Ucu Açık Soru · Özet

Soru 21: Sözlük Uygulaması

Bir sözlük uygulamasında kelime ekleme, kelime arama ve "ab" ile başlayan tüm kelimeleri alfabetik listeleme işlemleri yapılacak; kelimeler ilk kurulumda alfabetik sırayla toplu yükleniyor. HashMap, düz BST ve TreeMap (kırmızı-siyah ağaç) arasından hangisini seçersiniz? Gerekçelendirin.

Örnek cevap

HashMap ekleme/aramada ortalama O(1) verir ama sıra tutmaz; önek sorgusu tüm tabloyu tarayıp sonucu sıralamayı gerektirir (O(n + k log k)).

Düz BST sıralıdır ama alfabetik toplu yükleme her kelimeyi öncekinin sağına koyar: zincir, h = n − 1, yükleme O(n²), işlemler O(n).

TreeMap anahtarları sıralı tutar ve döndürmelerle h = O(log n) garanti eder; sıralı yükleme sorun olmaz. Önek sorgusu bir aralık sorgusudur: subMap("ab", "ac") O(log n + k) sürede ve zaten alfabetik sırayla gelir. Önek ağırlıklı işler için özel bir yapı da (trie) düşünülebilir.

Klasik Soru · Denge ve AVL

Soru 22: AVL Silme Zinciri

Şekildeki AVL ağacından 60 siliniyor. Dersteki sil önce BST silmesi yapar, özyineleme geri dönerken her atada dengele çağırır. Köke doğru hangi düğümlerde hangi döndürmeler yapılır? Son ağacı çizin.

51015202530354045505560
Cevabı göster

bf = h(sol) − h(sağ), boş alt ağaç −1.

  • 60 yaprak → kopar. 55: bf = 1 − (−1) = 2 ✗, bf(50) = 1 → LL: 55'te sağa → 50(45, 55). Bu alt ağacın yüksekliği 2'den 1'e iner.
  • 40: bf = 3 − 1 = 2 ✗, bf(15) = 1 − 2 = −1 → LR: 15'te sola (30 yukarı), sonra 40'ta sağa.
510152025303540455055

İki atada toplam 3 döndürme; yükseklik 4'ten 3'e iner. Eklemede tek düzeltme yeterlidir; silmede döndürme alt ağacı alçaltabilir ve dengesizlik yukarı taşınır: en fazla O(log n) atada döndürme.

Çoktan Seçmeli · Denge ve AVL

Soru 23: Silmede bf = 0 Olan Çocuk

AVL ağacı 50(30(20, 40), 60)'tan 60 siliniyor. 50'de çağrılan dengele ne yapar?

if (bf(d) > 1) {        // sol ağır
    if (bf(d.sol) < 0)   // LR
        d.sol = solaDondur(d.sol);
    return sagaDondur(d);  // LL
}

B: 60 gidince bf(50) = 1 − (−1) = 2; sol çocuk 30'da bf = 0. Bu durum eklemede oluşmaz, silmede çıkar; bf(d.sol) < 0 sağlanmadığı için tek sağa döndürme yapılır ve 40, 30'un sağından 50'nin soluna geçer. A da dengeli bir ağaç (40(30(20, —), 50)) verirdi ama kod bu durumda çift döndürme yapmaz. C: bf = 2 ihlaldir. D: yükseklik silmeden önceki gibi 2 kalır.

Son

Bölüm 10: Arama Ağaçları: Çalışma Soruları
Konu anlatımı: Arama Ağaçları sunumu
1 / 1 Sercan KÜLCÜ, Tüm hakları saklıdır.