--- title: 'İkili Arama Ağaçları' source: 'https://academia.sh/tr/kurslar/veri-yapilari/ikili-arama-agaclari' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:08:01+00:00' license: 'CC BY-SA 4.0' --- # İkili Arama Ağaçları Sıralama değişmezi, arama–ekleme–silme işlemleri, üç silme durumu ve dejenere ağaç sorunu. Önceki ders, ağacın tüm düğümlerini gezmenin $O(n)$ olduğunu gösterdi. Arama için bu yeterli değildir; bir dizide doğrusal arama da aynı maliyettedir ve ağaç hiçbir kazanç sağlamaz. Kazanç, ağaca bir **düzen** eklendiğinde ortaya çıkar. Her düğümde hangi dala gidileceği karşılaştırmayla belirlenebiliyorsa, arama tüm ağacı değil yalnızca bir yolu gezer. ## Sıralama Değişmezi **İkili arama ağacı (binary search tree)**, şu koşulu her düğümde sağlayan ikili ağaçtır: > Sol alt ağaçtaki tüm değerler düğümün değerinden küçük, sağ alt ağaçtaki tüm değerler > büyüktür. Koşulun **tüm alt ağaç** için geçerli olması gerekir; yalnızca doğrudan çocuklara bakmak yetmez. Bu, Programlama Temelleri kursunda tanımlanan anlamıyla bir **değişmezdir**: her işlemden önce ve sonra doğru kalmalıdır. ``` (12) / \ (7) (25) / \ \ (3) (10) (30) ``` Bu ağaçta `25` köklü alt ağacın tüm değerleri $12$'den büyüktür; `7` köklü alt ağacınkiler küçüktür. Aynı koşul her düğümde ayrı ayrı sağlanır. Değişmezin doğrudan bir sonucu vardır ve önceki dersle bağlantılıdır: **iç sıralı gezinme, değerleri artan sırada verir.** Sol alt ağaç önce gezildiği, sonra düğüm ziyaret edildiği, en son sağ alt ağaç gezildiği için sıra kendiliğinden oluşur. ## Arama Arama, kökten başlar ve her düğümde tek bir karşılaştırma yapar: - Aranan değer düğüme eşitse bulunmuştur. - Küçükse sol alt ağaca, büyükse sağ alt ağaca inilir. - Boş bir bağa ulaşılırsa değer ağaçta yoktur. Her adımda alt ağaçlardan biri tümüyle elenir. Bu, sıralı dizideki ikili aramanın ağaç üzerindeki karşılığıdır ve maliyeti **yükseklikle** orantılıdır. ```python class DugumBST: def __init__(self, deger: int) -> None: self.deger = deger self.sol: "DugumBST | None" = None self.sag: "DugumBST | None" = None def ara(kok: DugumBST | None, hedef: int) -> tuple[bool, int]: """Hedefi arar; (bulundu, karşılaştırma sayısı) döndürür.""" adim = 0 dugum = kok while dugum is not None: adim += 1 if hedef == dugum.deger: return True, adim dugum = dugum.sol if hedef < dugum.deger else dugum.sag return False, adim def ekle(kok: DugumBST | None, deger: int) -> DugumBST: """Değeri yerine yerleştirir; kökü döndürür. Yinelenen değer eklenmez.""" if kok is None: return DugumBST(deger) if deger < kok.deger: kok.sol = ekle(kok.sol, deger) elif deger > kok.deger: kok.sag = ekle(kok.sag, deger) return kok def ic_sirali(dugum, sonuc=None): sonuc = [] if sonuc is None else sonuc if dugum is not None: ic_sirali(dugum.sol, sonuc) sonuc.append(dugum.deger) ic_sirali(dugum.sag, sonuc) return sonuc kok = None for deger in (12, 7, 25, 3, 10, 30): kok = ekle(kok, deger) print(ic_sirali(kok)) # [3, 7, 10, 12, 25, 30] — sıralı print(ara(kok, 10)) # (True, 3) print(ara(kok, 11)) # (False, 3) ``` `10` değeri üç karşılaştırmada bulunur: `12 → 7 → 10`. Altı elemanlık ağaçta doğrusal arama en kötü durumda altı karşılaştırma yapardı. ## Ekleme Ekleme, başarısız bir aramadır: değerin bulunması gereken yer aranır ve boş bağa ulaşıldığında yeni düğüm oraya bağlanır. Yeni düğüm her zaman **yaprak** olur; var olan hiçbir bağ değişmez. Bu sadelik, sıralama değişmezinin korunmasını da kendiliğinden sağlar: düğüm, arama yolunun sonuna konduğu için tüm ata düğümlerin koşullarını zaten sağlar. Yinelenen değerlerin ne olacağı bir tasarım kararıdır: yok sayılabilir, sağ alt ağaca konabilir veya düğümde bir sayaç tutulabilir. Yukarıdaki gerçekleştirim ilkini seçmiştir; çok küme davranışı isteniyorsa sayaç yaklaşımı uygundur. ## Silme: Üç Durum Silme, ağacın en dikkat isteyen işlemidir; silinen düğümün çocuk sayısına göre üç durum vardır. **Yaprak düğüm.** Doğrudan kaldırılır; ebeveynin ilgili bağı boşaltılır. **Tek çocuklu düğüm.** Düğüm kaldırılır ve tek çocuğu, silinen düğümün yerine bağlanır. Alt ağacın tamamı yukarı taşınmış olur; sıralama değişmezi korunur. **İki çocuklu düğüm.** Doğrudan kaldırılamaz — iki alt ağaç tek bağa sığmaz. Çözüm, düğümün değerini **ardılıyla** değiştirmektir: sağ alt ağacın en küçük değeri. Bu değer, silinen düğümden büyük ama sağ alt ağaçtaki tüm değerlerden küçük olduğu için yerine geçebilir. Ardıl düğümün sol çocuğu olamayacağından, onun silinmesi ilk iki duruma iner. ```python def en_kucuk(dugum: DugumBST) -> DugumBST: while dugum.sol is not None: dugum = dugum.sol return dugum def sil(kok: DugumBST | None, deger: int) -> DugumBST | None: if kok is None: return None if deger < kok.deger: kok.sol = sil(kok.sol, deger) elif deger > kok.deger: kok.sag = sil(kok.sag, deger) else: if kok.sol is None: # yaprak veya tek çocuk (sağ) return kok.sag if kok.sag is None: # tek çocuk (sol) return kok.sol ardil = en_kucuk(kok.sag) # iki çocuk: ardılla değiştir kok.deger = ardil.deger kok.sag = sil(kok.sag, ardil.deger) return kok kok = None for deger in (12, 7, 25, 3, 10, 30): kok = ekle(kok, deger) kok = sil(kok, 3) # yaprak print(ic_sirali(kok)) # [7, 10, 12, 25, 30] kok = sil(kok, 25) # tek çocuklu print(ic_sirali(kok)) # [7, 10, 12, 30] kok = sil(kok, 12) # iki çocuklu: kök print(ic_sirali(kok)) # [7, 10, 30] ``` Her silmeden sonra iç sıralı gezinmenin sıralı kalması, değişmezin korunduğunun göstergesidir. Bu, bir veri yapısının doğruluğunu sınamanın standart yoludur: değişmezi her işlemden sonra denetlemek. ## Dejenere Ağaç Sorunu İkili arama ağacının vaadi, tüm işlemlerin yükseklikle orantılı olmasıdır. Vaadin değeri, yüksekliğin küçük olmasına bağlıdır — ve bunun hiçbir güvencesi yoktur. Değerler artan sırada eklenirse her yeni düğüm sağa bağlanır; ağaç bir bağlı listeye dönüşür: ```python artan = None for deger in (3, 7, 10, 12, 25, 30): # sıralı ekleme artan = ekle(artan, deger) karisik = None for deger in (12, 7, 25, 3, 10, 30): # dengeli sıra karisik = ekle(karisik, deger) print(ara(artan, 30)) # (True, 6) — tüm düğümler gezildi print(ara(karisik, 30)) # (True, 3) ``` Aynı altı değer, aynı yapı, iki kat fark. Girdi sıralı geldiğinde — ki gerçek verilerde sık karşılaşılan bir durumdur — ağaç en kötü hâline geçer. Bu, sonraki üç dersin çıkış noktasıdır: ağacın yüksekliğini, ekleme sırasından bağımsız olarak logaritmik tutmak. ## Maliyet Tablosu | Yapı | Arama | Ekleme | Silme | Sıralı gezinme | |---|---|---|---|---| | Karma tablosu | $O(1)$ ortalama | $O(1)$ ortalama | $O(1)$ ortalama | Desteklemez | | İkili arama ağacı (dengeli) | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ | | İkili arama ağacı (dejenere) | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ | ## Özet - İkili arama ağacı, her düğümde sol alt ağacın küçük, sağ alt ağacın büyük değerler taşıması değişmezine dayanır. - Değişmezin sonucu olarak iç sıralı gezinme değerleri artan sırada verir. - Arama her adımda bir alt ağacı eler; maliyet yükseklikle orantılıdır. - Ekleme, başarısız aramanın sonuna yaprak bağlamaktır; var olan bağlar değişmez. - Silmede üç durum vardır; iki çocuklu düğüm, sağ alt ağacın en küçüğüyle değiştirilerek ilk iki duruma indirgenir. - Yükseklik güvencesi yoktur: sıralı gelen girdi ağacı bağlı listeye çevirir ve tüm işlemler doğrusala düşer. ## Sonraki Adım Sorun tanımlandı: yükseklik, ekleme sırasına bağlı. Çözüm, ağacı her değişiklikten sonra denetlemek ve gerekiyorsa yeniden düzenlemektir. Sonraki ders, bu düzenlemeyi yapan dönme işlemini ve dengeyi güvenceye alan iki klasik ağaç ailesini ele alacak.