Ağaç Terminolojisi

Buraya kadarki yapılar doğrusaldı: her elemanın en fazla bir öncesi ve bir sonrası vardı. Ayrık kümeler dersinde bu kırıldı — gruplar, her düğümün bir üstü olduğu ama bir üstün birden çok altı olabildiği yapılarla tutuldu.

Bu konu, o yapıyı başlı başına ele alır. Ağaç (tree), dallanan ilişkileri modelleyen temel yapıdır ve bilgisayar biliminin her katmanında karşımıza çıkar.

Tanım

Ağaç, iki koşulu sağlayan bir düğüm–bağ yapısıdır:

1. Tüm düğümler birbirine bağlıdır; hiçbiri kopuk değildir.
2. Hiçbir döngü yoktur; iki düğüm arasında tam olarak bir yol vardır.

Bu iki koşulun sayısal sonucu şudur: $n$ düğümlü bir ağacın tam olarak $n - 1$ bağı vardır. Bir bağ daha eklenirse döngü oluşur, bir bağ çıkarılırsa yapı ikiye ayrılır.

Ağaçların çoğu köklüdür: bir düğüm kök seçilir ve tüm bağlar ondan uzağa doğru yönlenmiş sayılır. Bu kurs boyunca “ağaç” denildiğinde köklü ağaç kastedilir.

Terimler

                 (12)          ← kök, derinlik 0
                /    \
            (18)      (7)      ← derinlik 1
           /   \        \
       (25)   (14)      (30)   ← derinlik 2, hepsi yaprak

Terim	Anlamı	Örnekte
Kök	Üstü olmayan tek düğüm	12
Ebeveyn	Bir düğümün bir üstü	18’in ebeveyni 12
Çocuk	Bir düğümün bir altı	12’nin çocukları 18 ve 7
Kardeş	Aynı ebeveynin çocukları	25 ve 14
Yaprak	Çocuğu olmayan düğüm	25, 14, 30
İç düğüm	En az bir çocuğu olan düğüm	12, 18, 7
Ata	Kökten düğüme giden yoldaki düğümler	25’in ataları: 18, 12
Soy	Bir düğümün altındaki tüm düğümler	18’in soyu: 25, 14
Alt ağaç	Bir düğüm ve tüm soyu	18 köklü alt ağaç
Derinlik	Kökten düğüme giden bağ sayısı	25’in derinliği 2
Yükseklik	Düğümden en uzak yaprağa bağ sayısı	12’nin yüksekliği 2
Dallanma çarpanı	Bir düğümün çocuk sayısı	12 için 2

Derinlik ve yükseklik sık karıştırılır. Derinlik yukarıdan, yükseklik aşağıdan ölçülür. Kökün derinliği sıfır, yapraklarınki en büyüktür; yaprakların yüksekliği sıfır, kökünki en büyüktür. Ağacın yüksekliği, kökün yüksekliğidir.

Birden çok kopuk ağacın oluşturduğu yapıya orman denir. Ayrık kümeler dersindeki gösterim bir ormandı: her grup ayrı bir ağaçtı.

Ağaçlar Nerede Görünür

Ağaç, “her şeyin bir üstü var ama bir üstün birden çok altı olabilir” biçiminde tanımlanan her ilişkinin yapısıdır:

• Dosya sistemi. Dizinler ve dosyalar; kök dizinden yapraklara. Linux müfredatındaki dizin hiyerarşisi bu yapıdadır.
• Belge yapısı. İşaretleme dillerinde iç içe etiketler; her etiketin bir kapsayıcısı, birden çok içeriği vardır.
• Ayrıştırma ağacı. Bilgisayarlar Nasıl Çalışır kursunda kurulan soyut sözdizim ağacı; ifade önceliği ağacın biçiminde kodlanıyordu.
• Karar yapıları. Her düğümde bir soru, her dalda bir yanıt; makine öğrenmesindeki karar ağaçları bu düzendedir.
• Kuruluş şemaları ve kategori hiyerarşileri. Doğrudan modelleme.

Bu kadar geniş bir kullanım alanı, ağaçlar üzerinde tanımlı işlemlerin — gezinme, arama, derinlik hesabı — her yerde tekrar tekrar karşımıza çıkması demektir.

Gösterim Seçenekleri

Ağaç üç ana biçimde saklanır.

Çocuk listeleri. Her düğüm, çocuklarının listesini tutar. Genel ağaçlar için en doğal gösterimdir; dallanma çarpanı değişken olabilir. Bedeli, düğüm başına bir liste yapısıdır.

İlk çocuk – sonraki kardeş. Her düğüm iki bağ tutar: ilk çocuğu ve bir sonraki kardeşi. Değişken sayıda çocuk, sabit sayıda bağla temsil edilir; genel ağaç, ikili bir yapıya indirgenmiş olur.

Dizi gösterimi. Düğümler bir dizide tutulur ve ilişki, dizin aritmetiğiyle hesaplanır. Yalnızca ağacın biçimi düzenliyse uygulanabilir; sonraki derste ikili ağaçlar için tanımlanacaktır.

class AgacDugumu:
    """Genel ağaç düğümü: değer ve çocuk listesi."""

    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.cocuklar: list["AgacDugumu"] = []

    def cocuk_ekle(self, cocuk: "AgacDugumu") -> "AgacDugumu":
        self.cocuklar.append(cocuk)
        return cocuk


def yukseklik(dugum: AgacDugumu) -> int:
    """Düğümden en uzak yaprağa olan bağ sayısı."""
    if not dugum.cocuklar:
        return 0                                  # yaprağın yüksekliği sıfır
    return 1 + max(yukseklik(c) for c in dugum.cocuklar)


def dugum_sayisi(dugum: AgacDugumu) -> int:
    return 1 + sum(dugum_sayisi(c) for c in dugum.cocuklar)


def yaprak_sayisi(dugum: AgacDugumu) -> int:
    if not dugum.cocuklar:
        return 1
    return sum(yaprak_sayisi(c) for c in dugum.cocuklar)


kok = AgacDugumu(12)
sol = kok.cocuk_ekle(AgacDugumu(18))
sag = kok.cocuk_ekle(AgacDugumu(7))
sol.cocuk_ekle(AgacDugumu(25))
sol.cocuk_ekle(AgacDugumu(14))
sag.cocuk_ekle(AgacDugumu(30))

print(yukseklik(kok), dugum_sayisi(kok), yaprak_sayisi(kok))   # 2 6 3
print(yukseklik(sol), yukseklik(sag))                          # 1 1

Üç işlevin de özyinelemeli yazılması tesadüf değildir: ağacın tanımı özyinelemelidir — bir ağaç, bir kök ve onun alt ağaçlarıdır. Programlama Temelleri kursunda “problem tanımı dallanıyorsa özyineleme doğaldır” denmişti; ağaçlar bu ifadenin kanonik örneğidir.

Yapıyı Doğrulamak

Bir yapının gerçekten ağaç olup olmadığı iki koşulla sınanır: bağ sayısı düğüm sayısının bir eksiği olmalı ve yapı bağlı olmalıdır. İkisi birlikte döngüsüzlüğü de güvenceye alır.

Pratikte üçüncü bir sınama da yapılır: her düğüme yalnızca bir üstten gelinmelidir. Bir düğüme iki ayrı ebeveynden bağ varsa yapı ağaç değil, genel bir çizgedir; gezinme algoritmaları o düğümü iki kez ziyaret eder ve sonuç bozulur.

Yükseklik Neden Önemli

Ağaç üzerindeki hemen tüm işlemlerin maliyeti, düğüm sayısıyla değil yükseklikle orantılıdır: kökten yaprağa inen bir yol izlenir.

Bu, bir soruyu doğrudan önemli kılar: $n$ düğümlü bir ağacın yüksekliği ne olabilir?

• En iyi durum: Her düğüm çocuklarını dengeli dağıtırsa yükseklik $O(\log n)$’dir.
• En kötü durum: Her düğümün tek çocuğu varsa ağaç bir bağlı listeye dönüşür ve yükseklik $O(n)$ olur.

Bu nedenle ağaç yapılarının değerlendirilmesinde sorulacak ilk soru, yüksekliğin neyle sınırlandığıdır. İki uç arasındaki fark, bu konunun geri kalanının ana meselesidir: arama ağaçlarının dengeli tutulması, tam olarak yüksekliği logaritmik sınırda tutma çabasıdır.

Özet

• Ağaç, döngüsüz ve bağlı bir düğüm yapısıdır; $n$ düğümlü ağacın $n-1$ bağı vardır.
• Köklü ağaçta bağlar kökten uzağa yönlenir; kök dışındaki her düğümün tam bir ebeveyni vardır.
• Derinlik kökten aşağı, yükseklik düğümden yaprağa ölçülür; ağacın yüksekliği kökün yüksekliğidir.
• Ağaçlar dosya sistemlerinden ayrıştırma yapılarına kadar dallanan her ilişkinin modelidir.
• Gösterim, çocuk listeleri, ilk çocuk–sonraki kardeş veya dizin aritmetiği ile yapılır.
• İşlem maliyetleri düğüm sayısıyla değil yükseklikle orantılıdır; yükseklik dengeye bağlı olarak logaritmik ile doğrusal arasında değişir.

Sonraki Adım

Genel ağaçlarda dallanma çarpanı değişkendir ve bu, gösterimi ile analizi zorlaştırır. Sonraki ders, her düğümün en fazla iki çocuğu olduğu özel durumu — ikili ağaçları — ve bu kısıtın getirdiği düzenli gösterim olanaklarını ele alacak.