İkili Arama Ağaçları

Ö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.

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.

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:

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.