Bölüm 10: Arama Ağaçları
Ç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
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.
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?
Henüz aday yok; kökten (50) başlanır.
62 ≥ 50 → 50 ve solundakiler ardıl olamaz; sağa in.
62 < 70 → 70 bir aday; daha küçük aday ancak solda olabilir → sola in.
62 ≥ 60 → sağa in.
62 < 65 → aday = 65 (70'ten daha iyi); sola in: kok = null.
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.
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.
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?
38 < 50 → solda aralığa giren anahtar olabilir: sola in.
38 < 30 yanlış → sol alt ağaç (20) budanır. 30 aralık dışında. 30 < 62 → sağa.
38 < 40 → sola in.
35: solu budanır, aralık dışında; 35 < 62 → sağa (null), hemen döner.
40'a dönüldü: 40 ∈ [38, 62] → yazdır.
40 < 62 → sağa: 45. Solu boş; 45 ∈ aralık → yazdır. Sağı da boş.
45, 40 ve 30 çerçeveleri kapanır; 50'ye dönüldü: 50 ∈ aralık → yazdır.
50 < 62 → sağa: 70. 38 < 70 → sola in.
60: solu boş; 60 ∈ aralık → yazdır. 60 < 62 → sağa.
65 aralık dışında; 65 < 62 yanlış → sağı budanır.
70'e dönüldü: aralık dışında; 70 < 62 yanlış → 80 budanır.
Çı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.
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.
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.
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?
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ı.
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?
x kök değil. p = 20, g = 30.
g var; x ve p ikisi de sol çocuk → aynı yön: zig-zig.
Önce dede: 30'da sağa döndür → 20 yukarı çıkar.
Sonra ebeveyn: 20'de sağa döndür → x iki düzey yükseldi.
x hâlâ kök değil. p = 50 kök, g = null.
g == null → zig: 50'de sağa döndür; 10 kök olur, eski sağı (20…) 50'nin soluna geçer.
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).
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.
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.
İ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.