İkili Ağaçlar

Genel ağaçta bir düğümün kaç çocuğu olacağı belirsizdir; bu, gösterimi ve maliyet çözümlemesini zorlaştırır. İkili ağaç (binary tree), dallanmayı en fazla ikiye sınırlar: her düğümün bir sol ve bir sağ çocuğu olabilir, ikisi de olmayabilir.

Kısıt yalnızca sadeleştirme değildir. İki çocuk, “büyük mü küçük mü”, “sol mu sağ mı”, “evet mi hayır mı” biçimindeki ikili kararların doğal karşılığıdır; bu nedenle arama ağaçları, karar ağaçları ve ifade ağaçları hep ikilidir.

Sol ve Sağ Ayrı Bilgidir

Genel ağaçta çocukların sırası çoğu zaman anlamsızdır. İkili ağaçta ise sol ve sağ ayrı konumlardır: tek çocuğu olan bir düğümün o çocuğu sol mu sağ mı, yapının parçasıdır.

Bu ayrım, sonraki derslerde anlam kazanır: arama ağacında sol küçükleri, sağ büyükleri taşır; çıkarma işlemini gösteren bir ifade ağacında sol ile sağın yer değiştirmesi sonucu değiştirir.

Biçim Sınıfları

Üç tanım sık kullanılır ve karıştırılır.

Dolu (full) ikili ağaç: Her düğümün ya sıfır ya iki çocuğu vardır; tek çocuklu düğüm yoktur.

Tam (complete) ikili ağaç: Son seviye dışındaki tüm seviyeler tümüyle doludur ve son seviyedeki düğümler soldan sağa yerleşiktir. Boşluk yalnızca sağ uçta olabilir.

Kusursuz (perfect) ikili ağaç: Tüm seviyeler tümüyle doludur; yapraklar aynı derinliktedir.

   dolu ama tam değil      tam ama kusursuz değil      kusursuz
        (a)                        (a)                    (a)
       /   \                      /   \                  /   \
     (b)   (c)                  (b)   (c)              (b)   (c)
    /   \                      /   \   /              /  \   /  \
  (d)   (e)                  (d)  (e)(f)            (d) (e)(f) (g)

Kusursuz bir ağaç hem doludur hem tamdır. Tam ağaç kavramı, sonraki derslerde yığın yapısının temeli olacaktır: boşlukların yalnızca sağ uçta olması, ağacın diziye sığdırılmasını mümkün kılar.

Yükseklik ve Düğüm Sayısı

İkili ağaçta her seviyede en fazla $2^d$ düğüm bulunur ($d$ derinlik). Buradan iki sınır çıkar.

Yüksekliği $h$ olan bir ikili ağacın en fazla düğüm sayısı:

$$1 + 2 + 4 + \dots + 2^{h} = 2^{h+1} - 1$$

Tersinden okunduğunda, $n$ düğümlü bir ikili ağacın en az yüksekliği:

$$h \geq \log_2(n + 1) - 1$$

En kötü durumda ise her düğümün tek çocuğu vardır ve yükseklik $n - 1$ olur.

Bu iki sınır, bir önceki dersin kapanış sorusunu sayısallaştırır. Bin düğümlü bir ikili ağacın yüksekliği, dengeliyse dokuz dolayında, dejenere ise dokuz yüz doksan dokuzdur. Arama maliyeti yükseklikle orantılı olduğuna göre, aradaki fark yüz kattan fazladır.

Bağlantılı Gösterim

Genel gösterim, her düğümün iki bağ tutmasıdır:

class IkiliDugum:
    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.sol: "IkiliDugum | None" = None
        self.sag: "IkiliDugum | None" = None


def dugum_sayisi(dugum: IkiliDugum | None) -> int:
    if dugum is None:
        return 0
    return 1 + dugum_sayisi(dugum.sol) + dugum_sayisi(dugum.sag)


def yukseklik(dugum: IkiliDugum | None) -> int:
    if dugum is None:
        return -1                       # boş ağacın yüksekliği -1 kabul edilir
    return 1 + max(yukseklik(dugum.sol), yukseklik(dugum.sag))


def dolu_mu(dugum: IkiliDugum | None) -> bool:
    if dugum is None:
        return True
    if (dugum.sol is None) != (dugum.sag is None):
        return False                    # tek çocuklu düğüm bulundu
    return dolu_mu(dugum.sol) and dolu_mu(dugum.sag)


kok = IkiliDugum(12)
kok.sol = IkiliDugum(18)
kok.sag = IkiliDugum(7)
kok.sol.sol = IkiliDugum(25)
kok.sol.sag = IkiliDugum(14)

print(dugum_sayisi(kok), yukseklik(kok))    # 5 2
print(dolu_mu(kok))                          # True
kok.sag.sol = IkiliDugum(30)                 # 7 düğümüne tek çocuk eklendi
print(dolu_mu(kok))                          # False

Boş ağacın yüksekliğinin $-1$ kabul edilmesi bir sözleşmedir; tek düğümlü ağacın yüksekliği böylece $0$ çıkar ve önceki dersteki tanımla tutarlı kalır.

Dizi Gösterimi

Ağaç tam ise, bağlara hiç gerek kalmaz. Düğümler seviye seviye, soldan sağa bir diziye yerleştirilir; ilişki dizin aritmetiğiyle hesaplanır:

$$\text{sol}(i) = 2i + 1, \qquad \text{sağ}(i) = 2i + 2, \qquad \text{ebeveyn}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor$$

agac = [12, 18, 7, 25, 14, 30]      # tam ikili ağaç, seviye sırasıyla

def sol(i: int) -> int: return 2 * i + 1
def sag(i: int) -> int: return 2 * i + 2
def ebeveyn(i: int) -> int: return (i - 1) // 2

print(agac[0], agac[sol(0)], agac[sag(0)])       # 12 18 7
print(agac[sol(1)], agac[sag(1)])                # 25 14
print(agac[ebeveyn(5)], agac[ebeveyn(4)])        # 7 18

Gösterimin üstünlükleri, birinci konudaki dizi tartışmasının aynısıdır: işaretçi ek yükü yoktur ve düğümler bitişik durduğu için önbellek davranışı iyidir.

Kısıtı ise ağacın tam olmasıdır. Ağaç seyrekse — örneğin dejenere bir zincirse — dizi gösterimi $2^{h+1}$ göz ister ve büyük bölümü boş kalır. Bu nedenle dizi gösterimi, biçimi güvence altında olan yapılarda kullanılır; yığın bunun başlıca örneğidir.

Dengeli Ne Demektir

“Dengeli” sözcüğü tek bir tanıma sahip değildir. Üç ölçüt yaygındır: her düğümde alt ağaç yüksekliklerinin farkının sınırlı olması, her düğümde alt ağaç boyutlarının oranının sınırlı olması, ve yaprakların aynı derinlikte olması.

Üçü de aynı amaca hizmet eder — yüksekliği logaritmik tutmak — ama farklı yapılar farklı ölçütü seçer. Sonraki derslerde bunların üçü de karşınıza çıkacak: yükseklik farkı AVL ağaçlarında, siyah düğüm sayısı kırmızı–siyah ağaçlarda, aynı derinlik ise 2-3 ağaçlarında kullanılır.

İkili Ağaçların Sayısı

Bir yan not, ağaç biçimlerinin ne kadar çeşitli olduğunu gösterir: $n$ düğümlü farklı ikili ağaç biçimi sayısı hızla büyür — üç düğümle beş, dört düğümle on dört farklı biçim vardır. Bu sayılar Katalan sayıları olarak bilinir ve bir sayma probleminin çözümüdür: $n$ düğüm için kök seçildiğinde sol ve sağ alt ağaçlara kalan düğümlerin her bölüşümü ayrı bir biçim üretir, bu yüzden sayı düğüm başına yaklaşık dört katına çıkar.

Pratik sonucu şudur: aynı veri kümesi, ekleme sırasına göre çok farklı biçimlerde saklanabilir ve biçim, maliyeti belirler. Bu biçimlerin yalnızca küçük bir bölümü dengelidir; rastgele bir biçime güvenmek, en kötü duruma açık kalmak demektir. Dengeleme kavramının gerekçesi budur.

Özet

• İkili ağaçta her düğümün en fazla iki çocuğu vardır ve sol ile sağ ayrı konumlardır.
• Dolu ağaçta tek çocuklu düğüm yoktur; tam ağaçta boşluk yalnızca son seviyenin sağ ucundadır; kusursuz ağaçta tüm seviyeler doludur.
• Yüksekliği $h$ olan ağaç en fazla $2^{h+1}-1$ düğüm taşır; $n$ düğümlü ağacın en az yüksekliği logaritmiktir, en kötü durumda ise doğrusaldır.
• Bağlantılı gösterimde her düğüm iki bağ tutar; boş ağacın yüksekliği $-1$ sayılır.
• Tam ağaçlar diziyle gösterilebilir: sol $2i+1$, sağ $2i+2$, ebeveyn $\lfloor (i-1)/2 \rfloor$.
• Aynı veri kümesi birçok farklı ağaç biçimiyle saklanabilir; biçim maliyeti belirler.

Sonraki Adım

Ağaç kuruldu ama üzerinde henüz gezinilmedi. Bir ağacın tüm düğümlerini ziyaret etmenin birden çok yolu vardır ve hangi yolun seçildiği, elde edilen sıralamayı belirler. Sonraki ders dört temel gezinme düzenini ve her birinin hangi problemde kullanıldığını ele alacak.