Bölüm 9: Ağaçlar

9.1Ağaç kavramı

Şimdiye kadarki veri yapılarının hepsi doğrusaldır: öğeler bir çizgi üzerinde dizilir, her öğeden sonra en çok bir öğe gelir. Bu düzen, sıra bilgisinin önemli olduğu işler için uygundur. Ancak bir şirketin örgüt şeması, bir bilgisayarın dosya sistemi ya da bir soy ağacı tek bir çizgiye sığmaz. Bu yapılarda bir öğenin altında birden çok öğe bulunabilir; her biri de kendi altındakilerin üstüdür. Bu kesim, böyle hiyerarşileri tutan ağaç yapısının dilini kurar.

9.1.1Ağaç nedir?

Ağaç (tree), öğeleri hiyerarşik biçimde tutan, doğrusal olmayan bir veri yapısıdır. Öğelerin her birine düğüm (node), iki düğümü birbirine bağlayan çizgiye kenar (edge) denir. En üstte tek bir düğüm bulunur; buna kök (root) adı verilir. Bilgisayar biliminde ağaç ters çizilir: kök yukarıda durur, dallar aşağı doğru iner. Şekil 9.1 küçük bir ağacı bu biçimde gösterir.

Kenarlar bir yön taşır: her kenar bir üst düğümü bir alt düğüme bağlar. Üstteki düğüm alttakinin ebeveyni (parent), alttaki de üsttekinin çocuğudur (child). Ağacı ağaç yapan kural şudur: kök dışındaki her düğümün tam olarak bir ebeveyni vardır. Kökün ise hiç ebeveyni yoktur. Bir düğümün çocuk sayısına bu tanımda bir sınır konmaz; sıfır, bir ya da daha çok çocuk olabilir.

Tanımdaki ikinci koşulun sonucu önemlidir: ağaçta döngü (cycle) bulunamaz. Bir düğümden başlayıp kenarlar üzerinden yürüyerek aynı düğüme, aynı kenarı iki kez kullanmadan dönmek mümkün değildir. Döngü olsaydı, döngüdeki düğümlerden birinin iki ayrı yoldan gelen iki ebeveyni olması ya da yukarı çıkışın köke hiç varmayıp dönüp durması gerekirdi. Her iki durum da tanıma aykırıdır.

Ağaçlarla ilgili en çok kullanılan sayısal gerçek, kenar sayısıdır. Kök dışındaki her düğüm ebeveynine bir kenarla bağlanır ve her kenar tam olarak bir düğümü ebeveynine bağlar. Kenarları, alttaki uçlarındaki düğümlerle eşlersek bire bir bir eşleme elde ederiz.

Şekil 9.1 bu kuralı doğrular: yedi düğüm, altı kenar. Kural iki yönde de iş görür. Bir ağacın düğüm sayısı biliniyorsa kenar sayısı hemen bulunur. Bağlantılı bir yapıda kenar sayısı düğüm sayısından küçük değilse, yapı ağaç olamaz; içinde mutlaka bir döngü vardır.

9.1.2Günlük hayatta hiyerarşiler

Ağaç, bilgisayar bilimine dışarıdan gelmiş bir fikirdir; insanlar hiyerarşileri çok önceden ağaç biçiminde çizer. Birkaç örnek kavramı somutlaştırır.

• Dosya sistemi. En üstte kök dizin bulunur (Unix benzeri sistemlerde /). Klasörler başka klasör ve dosyaları içerir, dosyalar ise hiçbir şey içermez. Klasörler ağacın iç düğümleri, dosyalar yapraklarıdır.
• Kitap. Bir kitap kısımlara, kısımlar bölümlere, bölümler alt başlıklara ayrılır. İçindekiler sayfası bu ağacın girintili bir yazımıdır.
• Coğrafya. Kıtalar ülkelerden, ülkeler eyalet ya da illerden, iller de şehirlerden oluşur.
• Web sayfası. Bir HTML belgesi iç içe öğelerden oluşur: <html> öğesinin içinde <head> ve <body>, onların içinde başka öğeler bulunur. Tarayıcı belgeyi okurken bu öğelerden bir ağaç kurar. Bu ağaca belge nesne modeli (Document Object Model, kısaca DOM) denir.

Şekil 9.2 bir dosyanın tam yolunun neden tek olduğunu da gösterir. notlar.txt dosyasına kökten başlayıp /home/ali/notlar.txt yolundan ulaşılır; başka bir yol yoktur. Her düğümün tek ebeveyni olduğundan kökten bir düğüme inen yol da tektir. Kısayol (bağ) dosyaları bu kuralı delen ek bağlantılardır; onlar eklenince yapı artık saf bir ağaç olmaz.

9.1.3Bir yapı ne zaman ağaçtır?

Kökü işaretlenmemiş, rastgele çizilmiş bir bağlantı yapısının ağaç olup olmadığını anlamak için tanımdaki koşulları yapının kendi özelliklerine çevirmek gerekir. Kök henüz seçilmemişse ebeveyn kavramı da yoktur. Bu durumda ağaç olmak iki koşula bağlıdır. Birincisi, yapı bağlantılıdır: her düğümden her düğüme bir yol vardır. İkincisi, yapıda döngü yoktur. Bu iki koşulun sonucu olarak kenar sayısı, düğüm sayısından bir eksik çıkar. Bu koşulları sağlayan bir yapıda herhangi bir düğüm kök seçilebilir. Seçilen kökten uzaklaştıkça her düğümün ebeveyni, köke doğru olan tek komşusu olur.

Örnekte döngünün yokluğunu ayrıca denetlemedik; sayım bunu kendiliğinden verdi. Bağlantılı bir yapıyı ağaç hâline getirmek için en az n − 1 kenar gerekir. Bağlantılı bir yapıya bir kenar daha eklemek, zaten arasında yol bulunan iki düğümü ikinci kez bağlamak demektir. Bu da bir döngü oluşturur. Dolayısıyla “bağlantılı ve n − 1 kenarlı” olmak, “bağlantılı ve döngüsüz” olmakla aynı şeydir.

Şekil 9.4 ağaç tanımını bozan üç tipik durumu gösterir. Soldaki üçgende üç düğüme üç kenar düşer; kenar sayısı bir fazladır ve döngü oluşmuştur. Ortadaki yapıda alttaki düğüm iki üst düğüme bağlıdır; hangisi kök seçilirse seçilsin, bu düğümün kökten iki ayrı yolla ulaşılması gerekir. Sağdaki yapıda ise üç düğüme bir kenar düşer. Kenar eksik olduğu için yapı iki parçaya ayrılmıştır. Birbirinden kopuk ağaçların oluşturduğu böyle bir topluluğa orman (forest) denir.

9.1.4Kök, iç düğüm ve yaprak

Ağaçtaki düğümler çocuk sahibi olup olmadıklarına göre iki gruba ayrılır. Bu ayrım, ağaç üzerindeki algoritmaların neredeyse hepsinde karşımıza çıkar; çünkü özyinelemeli bir metot çoğu zaman yapraklarda durur, iç düğümlerde çocuklarına iner.

• Kök düğüm (root): Ağacın en üstündeki, ebeveyni olmayan düğümdür. Dosya sisteminde kök dizine karşılık gelir.
• İç düğüm (internal node): En az bir çocuğu olan düğümdür. Dosya sisteminde klasörlere karşılık gelir.
• Yaprak (leaf): Hiç çocuğu olmayan düğümdür. Ağacın dış kenarında durduğu için dış düğüm (external node) adıyla da anılır. Dosya sisteminde dosyalara karşılık gelir.

Şekil 9.5 iki ince noktaya dikkat çeker. Birincisi, kök de çocuğu varsa bir iç düğümdür; “kök” ve “iç düğüm” birbirini dışlayan sınıflar değildir. Kök, konumuyla; iç düğüm ve yaprak ise çocuk sayısıyla tanımlanır. İkincisi, yaprakların hepsi aynı seviyede olmak zorunda değildir: 9, kökün doğrudan çocuğudur ama 4, 5, 6, 7 gibi o da bir yapraktır. Tek düğümlü bir ağaçta ise kökün çocuğu yoktur; bu durumda kök aynı zamanda yapraktır.

9.1.5Düğümler arası ilişkiler

Ağaç terimlerinin çoğu bir aile ağacından alınmıştır. Bir düğümün hemen üstündeki düğüm ebeveyn, hemen altındakiler çocuklardır. Aynı ebeveynin çocukları birbirinin kardeşidir (sibling). Bir düğümden köke giden yol üzerindeki düğümler o düğümün atalarıdır (ancestor). Bir düğümün altında kalan, yani o düğümden aşağı inerek ulaşılabilen bütün düğümler ise onun soyudur (descendant). Tablo 9.1 bu ilişkileri Şekil 9.6'daki ağaç üzerinde örnekler.

Ata ve soy birbirinin tersidir: M'nin ataları H, D ve A olduğuna göre M de H'nin, D'nin ve A'nın soyundandır. Kök, ağaçtaki bütün düğümlerin atasıdır; yapraklar ise kimsenin atası değildir. Bazı kaynaklar bir düğümü kendi atası ve kendi soyu da sayar. Bu notta, aksi söylenmedikçe, ata ve soy düğümün kendisini içermez. Bir düğümün soyu, o düğümün alt ağacındaki diğer düğümlerdir.

Kardeşlik çoğu zaman yanlış anlaşılır. İki düğümün aynı derinlikte, yani çizimde aynı satırda olması onları kardeş yapmaz. Şekil 9.6'daki F ve G aynı satırdadır, ama F'nin ebeveyni B, G'ninki C'dir; bu yüzden kardeş değillerdir. Akrabalık diliyle söylenirse F ile G kuzendir. Kardeşlik yalnız ortak ebeveyn ile tanımlanır.

Şekil 9.7 aynı ağacı, terimleri adım adım gösteren sunum çiziminin dört karesiyle verir. Ağaçta 13 düğüm vardır: A, B, C, D, E, F, G, H, I, J, K, L, M. Yapraklar çocuğu olmayan yedi düğümdür: K, L, F, G, M, I, J. İç düğümler en az bir çocuğu olan altı düğümdür: A, B, C, D, E, H. Sayılar tutar: 7 + 6 = 13. Kenar sayısı da Teorem 9.1'e göre 12'dir.

9.1.6Derece, derinlik, seviye ve yükseklik

Ağaçla ilgili hemen her maliyet hesabı birkaç sayısal ölçüye dayanır. Bunların en temeli, bir düğümün ne kadar dallandığını ve kökten ne kadar uzakta olduğunu söyleyen ölçülerdir.

Derinlik ile yükseklik ters yönlere bakar. Derinlik yukarıya, köke doğru ölçülür: “Bu düğüm kökten ne kadar aşağıda?” Yükseklik aşağıya, yapraklara doğru ölçülür: “Bu düğümün altında ne kadar uzun bir dal var?” Kökün derinliği her zaman 0'dır; yüksekliği ise ağacın yüksekliğidir. Yaprakların yüksekliği her zaman 0'dır; derinlikleri ise yaprağın nerede durduğuna göre değişir.

Bu notta derinlik ve yükseklik kenar sayısıyla ölçülür. Bazı kitaplar bunun yerine yol üzerindeki düğüm sayısını kullanır ve seviyeleri 1'den başlatır. O zaman kökün derinliği 1, yaprağın yüksekliği 1 olur; bütün değerler bir fazla çıkar. İki tanım da tutarlıdır, ama karıştırılırsa sonuçlar bir kayar. Kaynaklar karşılaştırılırken hangi tanımın kullanıldığına bakılmalıdır.

Tablodaki iki satır farklı bilgiler taşır. Derinliği bulmak için yalnız düğümün atalarına bakmak yeter; yükseklik ise düğümün bütün soyuna bakmayı gerektirir. Bu fark kodda da görülür: derinlik hesabı ebeveyn zinciri boyunca yukarı çıkar, yükseklik hesabı çocuklar üzerinden aşağı iner.

9.1.7Yol ve alt ağaç

Kenarlar boyunca bir düğümden diğerine yürümek bir yol (path) oluşturur. Biçimsel olarak bir yol, düğümler ve kenarlar arasında gidip gelen bir dizidir:

p = (v₀, e₁, v₁, e₂, …, e_k, v_k)

Burada her e_i kenarı v_i−1 ile v_i düğümlerini bağlar. Yolun başı start(p) = v₀, sonu end(p) = v_k, uzunluğu da kenar sayısı olan length(p) = k'dir. Hiçbir düğümün tekrar etmediği yola basit yol denir. Derinlik, kökten düğüme inen yolun uzunluğudur; yükseklik de düğümden en uzak yaprağa inen yolun uzunluğudur.

Şekil 9.9 ispattaki inşayı somut olarak gösterir. K'nin ataları E, B, A; M'nin ataları H, D, A'dır. İki zincirin ilk ortak düğümü A'dır. Yol K'den A'ya üç kenarla çıkar, A'dan M'ye üç kenarla iner; toplam uzunluk 6'dır. Bu iki düğüm arasında başka bir yol yoktur. Dosya sistemindeki “bir dosyanın tek bir tam yolu vardır” gözlemi de bu teoremin özel bir durumudur.

Alt ağaç (subtree), bir düğüm ile onun bütün soyundan oluşan yapıdır. Alt ağaç kendi başına bir ağaçtır: kökü seçilen düğümdür, içindeki her düğümün ebeveyni yine alt ağacın içindedir. Şekil 9.7'nin (d) karesindeki kesikli çerçeve, D'nin alt ağacını gösterir: D, H, I, J ve M. Dosya sisteminde bir klasör ile altındaki her şey bir alt ağaçtır. Bir klasörü kopyalamak ya da silmek, aslında bir alt ağacı kopyalamak ya da silmektir.

Alt ağaç kavramı, ağaç algoritmalarının özyinelemeli yazılmasının temelidir. Bir düğümün çocukları, kendi alt ağaçlarının kökleridir. Bir ağaç üzerinde yapılacak bir iş çoğu zaman şöyle tarif edilir: aynı işi her alt ağaçta yap, sonuçları birleştir, kökü de hesaba kat. Yüksekliğin tanımı bunun ilk örneğidir: bir düğümün yüksekliği, alt ağaçlarının yüksekliklerinin en büyüğünün bir fazlasıdır.

9.1.8Temel ağaç türleri

Ağaç tanımı bir düğümün çocuk sayısına sınır koymaz. Uygulamada ise çocuk sayısını sınırlamak ya da çocuklara bir düzen getirmek çoğu zaman işleri kolaylaştırır. Tablo 9.4 bu derste karşılaşılan dört türü özetler.

Türler birbirinin içine geçer. Her ikili arama ağacı bir ikili ağaçtır, her ikili ağaç k = 2 için bir k-lı ağaçtır, her k-lı ağaç da bir genel ağaçtır. Kısıt arttıkça yapı daha az esnek, ama üzerinde çalışmak daha kolay olur. Örneğin ikili arama ağacında bir anahtarı aramak için her düğümde yalnız bir çocuğa inmek yeter: aranan anahtar küçükse sola, büyükse sağa gidilir. Şekil 9.10'un sağındaki ağaçta 6 aranırken 8'den sola, 3'ten sağa inilir ve iki karşılaştırmada 6'ya ulaşılır.

Bu notun ağırlığı ikili ağaçlardadır. Genel ağaçlar da önemlidir, ama her genel ağaç bir ikili ağaç biçiminde saklanabilir; bu dönüşüm gösterimler kesiminde anlatılır. İkili arama ağaçlarının ekleme, silme ve dengeleme işlemleri ise kendi başına geniş bir konudur; burada yalnız tanım düzeyinde anılır.

9.1.9Ağaç ADT'si

Ağacı kodda kullanmadan önce ona hangi işlemlerle erişileceğini belirlemek gerekir. Yığın ve kuyrukta olduğu gibi burada da işlemleri gerçeklemeden ayırmak işe yarar. Yapının ne yaptığını söyleyen tarife soyut veri tipi (abstract data type, ADT) denir. Aşağıdaki Java arayüzü, Goodrich, Tamassia ve Goldwasser'in ağaç ADT'sinin Türkçe adlarla yazılmış hâlidir.

public interface Agac<E> extends Iterable<E> {
  Konum<E> kok();
  Konum<E> ebeveyn(Konum<E> p);
  Iterable<Konum<E>> cocuklar(Konum<E> p);
  int cocukSayisi(Konum<E> p);
  boolean icMi(Konum<E> p);      // isInternal
  boolean yaprakMi(Konum<E> p);  // isExternal
  boolean kokMu(Konum<E> p);     // isRoot
  int size();
  boolean isEmpty();
  Iterable<Konum<E>> konumlar(); // positions
}
// Konum<E> (Position): E getElement();

Arayüzün merkezinde konum (position) kavramı vardır. Konum<E>, ağaçtaki bir yeri temsil eden küçük bir nesnedir; tek bir işlemi vardır: getElement(), o yerdeki öğeyi döndürür. Kullanıcı ağacın içindeki düğüm nesnelerini doğrudan görmez, onlara referans tutamaz, alanlarını değiştiremez. Yalnız konumlar üzerinden ADT metotlarını çağırır. Böylece ağacın bellekte bağlantılarla mı yoksa bir diziyle mi tutulduğu kullanıcıdan gizlenir. Gerçekleme değişse bile ağacı kullanan kod değişmez.

Metotlar üç grupta toplanabilir.

• Gezinme metotları. kok() kökün konumunu döndürür (ağaç boşsa null). ebeveyn(p), p'nin ebeveyninin konumunu döndürür; p kökse null döner. cocuklar(p) çocukların konumlarını sırayla verir; dönüş tipi Iterable olduğu için sonuç doğrudan bir for-each döngüsünde kullanılabilir. cocukSayisi(p) çocukların sayısını, yani p'nin derecesini verir.
• Sorgu metotları. icMi(p), yaprakMi(p) ve kokMu(p) bir konumun iç düğüm, yaprak ya da kök olup olmadığını söyler. Yorumlardaki İngilizce adlar (isInternal, isExternal, isRoot) kaynak kitaptakilerdir.
• Genel metotlar. size() düğüm sayısını, isEmpty() ağacın boş olup olmadığını verir. konumlar() bütün konumları, iterator() ise (Iterable<E>'den gelir) bütün öğeleri bir sırayla dolaşır.

İkili ağaç ADT'si bu arayüzü genişletir ve üç metot ekler: sol(p), sag(p) ve kardes(p). İlk ikisi p'nin sol ve sağ çocuğunu (yoksa null), sonuncusu p'nin kardeşini döndürür. Kaynak kitapta bu metotlar left, right ve sibling adını taşır.

Şekil 9.11 üzerinde birkaç çağrının sonucunu yazalım. cocukSayisi(p) 2 döndürür. icMi(p) true, yaprakMi(p) false, kokMu(p) false döndürür. kok() A'nın konumunu verir; ebeveyn(kok()) ise null'dır. Ağaçta yedi düğüm olduğu için size() 7 döndürür.

9.1.10Kod izleme: derinlik ve yükseklik

ADT metotlarıyla, ağacın nasıl gerçeklendiğini bilmeden derinlik ve yükseklik hesaplanabilir. İki metot da tanımlarını neredeyse kelimesi kelimesine koda çevirir.

int derinlik(Konum<E> p) {
    if (kokMu(p)) return 0;
    return 1 + derinlik(ebeveyn(p));
}
int yukseklik(Konum<E> p) {
    int h = 0;
    for (Konum<E> c : cocuklar(p))
        h = Math.max(h, 1 + yukseklik(c));
    return h;
}

derinlik(p) tanımı izler: kökün derinliği 0'dır; kök olmayan bir düğümün derinliği, ebeveyninin derinliğinin bir fazlasıdır. Metot p'den başlayıp ebeveyn zinciri boyunca köke kadar çıkar. Her çağrı bir kenar yukarı çıktığı için p'nin derinliği d ise metot d + 1 kez çağrılır; zaman O(d + 1)'dir. Çağrı yığınında da en çok d + 1 çerçeve birikir.

yukseklik(p) de tanımı izler, ama aşağı bakar. h 0'dan başlar. Döngü p'nin her çocuğu c için 1 + yukseklik(c) değerini hesaplar ve h'yi bu değerle büyütür. Çocuğu olmayan bir düğümde döngü hiç dönmez ve 0 döner; bu, yaprağın yüksekliğidir. Metot p'nin alt ağacındaki her düğüm için bir kez çağrılır. Bir düğümün çocuklarını dolaşmanın maliyeti çocuk sayısıyla orantılıdır; bütün düğümlerin çocuk sayıları toplamı da kenar sayısı kadardır. Bu yüzden yukseklik(p), alt ağaçta n_p düğüm varsa O(n_p) sürer.

İzlemeyi Şekil 9.11'deki ağaç üzerinde yapalım: önce derinlik(G), sonra yukseklik(B). Tablo 9.5 her adımda çağrı yığınını (alttan üste) ve dönen değerleri verir.

İzleme iki metodun simetrisini açıkça gösterir. derinlik yukarı çıkarken çağrı yaparsa, değerler aşağı inerken hesaplanır: önce kök 0 der, sonra her çerçeve aldığı değere 1 ekler. yukseklik aşağı inerken çağrı yaparsa, değerler yukarı çıkarken hesaplanır: önce yapraklar 0 der, her iç düğüm çocuklarından gelenlerin en büyüğüne 1 ekler. yukseklik(B) dört kez çağrılmıştır: B, D, E ve G için. Bunlar B'nin alt ağacındaki düğümlerin tamamıdır; ağacın geri kalanına (A, C, F) hiç dokunulmamıştır.

Ağacın yüksekliği iki yolla hesaplanabilir. Birincisi yukseklik(kok()) çağrısıdır ve O(n) sürer. İkincisi, bütün düğümlerin derinliklerini derinlik ile hesaplayıp en büyüğünü almaktır. Bu ikinci yol her düğüm için ayrı bir yukarı tırmanış yapar. Derinliği d_p olan düğüm için maliyet O(d_p + 1) olduğundan toplam maliyet O(n + Σ d_p) olur. Zincir biçimli bir ağaçta derinlikler 0, 1, …, n − 1'dir ve toplamları n(n − 1)/2'ye ulaşır; maliyet O(n²)'ye çıkar. Doğru yöntem birincisidir.

9.2İkili ağaçlar

Genel ağaçta bir düğümün kaç çocuğu olacağı bilinmez. Bu esneklik, ağacı saklayan kodu da karmaşıklaştırır: her düğüm değişken uzunlukta bir çocuk listesi tutmak zorunda kalır. Çocuk sayısı en çok ikiyle sınırlanınca hem saklama hem de algoritmalar sadeleşir. İkili ağaçlar bu yüzden ağaçların en çok kullanılan biçimidir. İfade ağaçları, ikili arama ağaçları, heap yapıları ve Huffman kodlama ağaçları ikili ağaç üzerine kuruludur.

9.2.1İkili ağacın tanımı

İkili ağaçta her düğümün en çok iki çocuğu vardır. Ama asıl ayırt edici özellik bu sayı değil, çocukların adlandırılmasıdır. Her çocuk ya sol çocuk ya da sağ çocuktur. Tek çocuklu bir düğümde bile o çocuğun solda mı sağda mı olduğu bilinir ve önemlidir.

Tanım özyinelemelidir: ikili ağacı yine ikili ağaçlar cinsinden tarif eder. Bu bir döngü değildir, çünkü her adımda alt ağaçlar daha küçüktür ve sonunda boş ağaca varılır. Boş ağaç özyinelemenin taban durumudur (base case). Tanımın bu biçimi, ikili ağaç metotlarının yazılışını da belirler. Metot boş ağaçta bir değer döndürür. Boş olmayan ağaçta kendini sol ve sağ alt ağaca uygular, sonra sonuçları birleştirir.

Şekil 9.13 bu farkı gösterir. İki çizimde de A'nın tek bir çocuğu, B vardır. Genel ağaç gözüyle bakılırsa iki yapı aynıdır: bir kök ve onun tek çocuğu. İkili ağaç gözüyle bakılırsa farklıdır: birinde sol alt ağaç dolu, sağ alt ağaç boştur; ötekinde tersi. Ayrımın pratik bir anlamı vardır. Örneğin ikili arama ağacında sol, küçük anahtarlar demektir. Kök ortada gezinme de sol ve sağı ayırır; iki ağaç için farklı çıktılar verir: soldaki için B A, sağdaki için A B.

İkili ağacın düğümleri dengeli dağılmak zorunda değildir. Şekil 9.14'ün solundaki yapıda her düğümün yalnız sol çocuğu vardır ve ağaç bir zincire dönüşmüştür. Böyle ağaçlara çarpık (skewed) ağaç denir. Çarpık ağaç da geçerli bir ikili ağaçtır, ama ikili ağacın sağladığı avantajların çoğunu kaybeder. Dört düğümlü zincirin yüksekliği 3'tür; aynı dört düğüm dengeli dizilseydi yükseklik 2 olurdu. Fark küçük ağaçta önemsiz görünür, ama bir milyon düğümde yaklaşık 20 ile bir milyon arasındaki farka dönüşür.

9.2.2Dolu, tam ve mükemmel ikili ağaç

İkili ağaçların biçimini anlatmak için üç özel ad kullanılır. Bu adlar birbirine çok yakın olduğu için en çok karıştırılan kavramlar arasındadır. Türkçe kaynaklarda “dolu” ve “tam” sözcükleri yer yer ters anlamda da kullanılır. Karışıklığı önlemenin en güvenli yolu İngilizce karşılıkları esas almaktır: full, complete ve perfect.

Üç tanım farklı şeylere bakar. Dolu olmak, her düğümün kendi çocuk sayısıyla ilgili yerel bir koşuldur; ağacın genel şekline bakmaz. Bu yüzden dolu bir ağaç çok dengesiz olabilir: her adımda sağ çocuğu bir yaprak olan, sol çocuğu ise yeniden ikiye dallanan bir ağaç doludur ama bir zincire çok benzer. Tam olmak, ağacın seviyelerine bakan genel bir koşuldur; tek çocuklu bir düğüme izin verir, yeter ki bu düğüm son seviyenin hemen üstünde ve doğru konumda dursun. Mükemmel olmak ise en güçlü koşuldur: ağaç, yüksekliğinin izin verdiği bütün düğümleri içerir.

Tam ağacı anlamanın pratik bir yolu, düğümleri seviye seviye ve her seviyede soldan sağa numaralamaktır. Kök 1, onun çocukları 2 ve 3, bir alt seviye 4, 5, 6, 7 numarasını alır. Bir ikili ağacın n düğümü 1'den n'ye kadar bütün numaraları boşluksuz dolduruyorsa ağaç tamdır. Arada bir numara boş kalıyorsa, örneğin 10 boşken 11 doluysa, ağaç tam değildir. Bu numaralama, dizi gösteriminin de temelidir.

Tanımlar arasındaki ilişkiler şöyle özetlenebilir. Mükemmel bir ağaç hem dolu hem tamdır: iç düğümlerin hepsinde iki çocuk vardır ve bütün seviyeler, son seviye de dahil, doludur. Dolu ile tam ise birbirini gerektirmez. Dolu ama tam olmayan, tam ama dolu olmayan, ne dolu ne tam olan ağaçlar vardır.

9.2.3Dört ağaç üzerinde ayrım

Tanımları sınamanın en iyi yolu, onları somut ağaçlara uygulamaktır. Şekil 9.16 dört ağaç verir; her biri için üç özellik ayrı ayrı denetlenir.

Tablonun ilk iki satırı, dolu ile tamın bağımsız olduğunun somut kanıtıdır: (a) dolu ama tam değil, (b) tam ama dolu değil. (b) ile (c) arasındaki fark da öğreticidir. İki ağaçta da 5 tek çocukludur. (b)'de bu çocuk sol konumdadır (10) ve numaralar boşluksuz devam eder. (c)'de çocuk sağ konumdadır (11) ve 10 boş kalır. Tek bir düğümün sol yerine sağda durması, ağacı tam olmaktan çıkarmıştır.

9.2.4Düğüm sayısı ve yükseklik bağıntıları

İkili ağaçta her düğüm en çok iki çocuk taşıdığından, her seviyedeki düğüm sayısı bir öncekinin en çok iki katı olabilir. Bu basit gözlem, düğüm sayısı ile yükseklik arasındaki bütün bağıntıların kaynağıdır. Tablo 9.7 bu bağıntıları toplar; ardından her birinin gerekçesi verilir.

Üst sınırdaki toplam, ikinin ardışık kuvvetlerinin toplamıdır ve her zaman bir sonraki kuvvetten bir eksiktir: 1 + 2 + 4 + 8 = 15 = 16 − 1. Bu sınıra eşitlik yalnız mükemmel ağaçta ulaşılır. Yüksekliği 3 olan mükemmel ağaç 15 düğüm içerir; yüksekliği 4 olan 31 düğüm içerir. Alt sınıra ise her düğümün tek çocuklu olduğu zincirde ulaşılır: yüksekliği 3 olan zincir 4 düğümlüdür.

Bu bağıntıların neden önemli olduğu son satırda görülür. Ağaç üzerindeki birçok işlem, örneğin bir anahtarı aramak ya da yeni bir düğümü uygun yere eklemek, kökten bir yaprağa doğru tek bir yol boyunca ilerler. Böyle işlemlerin maliyeti O(h)'dir. Dengeli bir ağaçta h ≈ log₂ n olduğundan bir milyon düğümlü ağaçta yaklaşık 20 seviye vardır (2²⁰ ≈ 10⁶). Çarpık ağaçta ise h = n − 1'dir ve aynı işlem bir bağlı listede arama kadar yavaşlar. Arama ağaçlarının dengelenmesi bu farkı kapatmak için yapılır.

9.2.5Dolu ikili ağaçta yaprak ve iç düğüm sayısı

Dolu ikili ağaçların ilginç bir sayma özelliği vardır: yaprak sayısı her zaman iç düğüm sayısından tam bir fazladır. Tablo 9.7'deki son satır bunu 7 düğümlü mükemmel ağaçla örnekler: 3 iç düğüm (kök ve onun iki çocuğu), 4 yaprak.

İspatı en sezdiren yol, her dolu ikili ağacın tek bir düğümden başlayıp aynı işlemin tekrarıyla elde edilebildiğini görmektir. Dolu ağaçta bir yaprağa tek çocuk eklenemez; ağaç dolu kalsın diye her seferinde bir yaprağa iki çocuk birden eklenir. Şekil 9.17 bu büyümeyi adım adım gösterir.

Teoremin sonucu olan n = 2i + 1, dolu ikili ağaçta düğüm sayısının hiçbir zaman çift olamayacağını söyler. 6 düğümlü dolu ikili ağaç yoktur. Ayrıca düğüm sayısı biliniyorsa yaprak ve iç düğüm sayıları da bilinir: y = (n + 1)/2, i = (n − 1)/2. 15 düğümlü bir dolu ağaçta 8 yaprak ve 7 iç düğüm vardır.

Bu özellik birçok uygulamada doğrudan kullanılır. Bir aritmetik ifade ağacında her işleç iki işlenen alır; işleçler iç düğüm, sayılar yapraktır ve ağaç doludur. Dolayısıyla ikili işleçlerle yazılmış bir ifadede sayı adedi, işleç adedinden her zaman bir fazladır: (3 + 4) × (5 − 2) ifadesinde 3 işleç ve 4 sayı vardır. Huffman kodlamasında da her iç düğüm iki alt ağacı birleştirerek oluşur. k farklı karakter için kurulan ağacın k yaprağı ve k − 1 iç düğümü olur.

Kutudaki genel bağıntı da kenar sayılarak kolayca gösterilir. Tek çocuklu düğüm sayısı i₁, iki çocuklu düğüm sayısı i₂ olsun. Kenar sayısı bir yandan n − 1 = y + i₁ + i₂ − 1'dir. Her kenar bir çocuğa da iner; yani kenar sayısı i₁ + 2i₂'dir. İkisi eşitlenince y = i₂ + 1 kalır. Dolu ağaçta i₁ = 0 olduğu için i₂ = i olur ve teorem yeniden elde edilir.

9.3Gösterimler

Ağaç kâğıt üzerinde düğümler ve çizgilerden oluşur; bellekte ise ya ardışık hücrelerden oluşan bir dizi ya da birbirini gösteren nesneler vardır. Bir ağacı bu iki araçtan biriyle temsil etmenin yollarına gösterim denir. Hangi gösterimin seçildiği, ebeveyn ve çocuklara ne kadar hızlı ulaşılacağını, ne kadar bellek harcanacağını ve ağacın ne kadar kolay büyütüleceğini belirler.

9.3.1Dizi gösterimi

Tam ağaçların numaralanması, ikili ağacı bir diziye yerleştirmenin doğal yolunu verir. Düğümler seviye seviye, her seviyede soldan sağa okunur ve bu sırayla dizinin hücrelerine yazılır. Kök ilk hücreye, onun çocukları sonraki iki hücreye, bir alt seviye sonraki dört hücreye gider. Bu düzende bir düğümün çocuklarının ve ebeveyninin indisi, düğümün kendi indisinden basit bir aritmetikle bulunur.

1 tabanlı düzende formüller daha sadedir; bu yüzden birçok kitap dizinin 0. hücresini boş bırakır ve kökü 1. hücreye koyar. Formüllerin nedeni şöyle görülür. d derinliğindeki ilk düğüm 2^d indisini alır, çünkü üstündeki seviyelerde toplam 2^d − 1 düğüm vardır. Bir düğümden önce kendi seviyesinde j düğüm bulunuyorsa, bir alt seviyede onların 2j çocuğu bulunur. Bu sayımlar birleşince indis i'deki düğümün sol çocuğu 2i'ye düşer; sağ çocuk hemen yanındadır. Ebeveyn formülü bu ikisinin tersidir: hem 2i hem 2i + 1, 2'ye tam sayı bölmesiyle i'yi verir.

0 tabanlı formüller, 1 tabanlılardan indisleri bir kaydırarak elde edilir. 0 tabanlı indis i, 1 tabanlı i + 1'e karşılık gelir. Onun sol çocuğu 1 tabanlıda 2(i + 1) = 2i + 2'dir; 0 tabanlıya geri dönmek için bir çıkarılır ve 2i + 1 bulunur. Diğer formüller de aynı yolla çıkar.

Şekil 9.18'deki ağaçta E indis 5'tedir. Sol çocuğu 2 · 5 = 10, sağ çocuğu 11 indisinde olurdu. Dizide yalnız 9 düğüm bulunduğu için 10 ve 11 dizinin dışındadır; E'nin çocuğu yoktur, E bir yapraktır. E'nin ebeveyni ⌊5 / 2⌋ = 2, yani B'dir. Bu gösterimde düğümler referans taşımaz. Ebeveyn ve çocuk bilgisi, konumun kendisinde saklıdır; ulaşmak için birkaç aritmetik işlem yeterlidir ve her erişim O(1) sürer.

Dizi gösterimi en çok tam ikili ağaçlara yakışır. Tam ağaçta düğümler 1'den n'ye kadar bütün indisleri boşluksuz doldurur; dizi tam n hücre kullanır ve hiç boşluk kalmaz. İkili heap bu yüzden hemen her zaman bir dizide tutulur. Tam olmayan ağaçlarda ise boş konumlar dizide boş hücre olarak kalır; bunun bedeli aşağıda hesaplanır.

9.3.2Kod izleme: indis hesabı ve köke giden yol

Aşağıdaki kod 1 tabanlı formülleri üç küçük metoda çevirir ve onları kullanarak bir düğümden köke kadar bütün ataları yazdırır.

int sol(int i)     { return 2 * i; }
int sag(int i)     { return 2 * i + 1; }
int ebeveyn(int i) { return i / 2; }
void kokeYol(char[] a, int i) {  // i'den köke
  while (i >= 1) {
    System.out.print(a[i] + " ");
    i = ebeveyn(i);
  }
}

sol, sag ve ebeveyn tek satırlık metotlardır. ebeveyn'de i / 2 ifadesi Java'da tam sayı bölmesidir; sonucun ondalık kısmı atılır, yani aşağı yuvarlanır. Bu, ⌊i / 2⌋'nin ta kendisidir. kokeYol(a, i), i 1'den küçük olmadığı sürece döner. Her turda a[i]'yi yazdırır ve i'yi ebeveynin indisine çeker. Kökün indisi 1'dir; onun “ebeveyni” ⌊1 / 2⌋ = 0 çıkar ve döngü durur. 0. hücrenin boş bırakılması bu yüzden kullanışlıdır: 0 indisi “ebeveyn yok” anlamına gelir.

İzlemede iki nokta öne çıkar. Birincisi, bir indisin geçerli bir çocuk olup olmadığı dizi uzunluğuyla denetlenir: n düğümlü bir ağaçta 2i ≤ n ise sol çocuk vardır, 2i + 1 ≤ n ise sağ çocuk vardır. Bu denetim yapılmazsa dizinin sonundan sonraki bir hücre okunmaya çalışılır ve ArrayIndexOutOfBoundsException alınır. Tam olmayan ağaçlarda ayrıca hücrenin boş olup olmadığına da bakmak gerekir. İkincisi, kardeş düğümler aynı ebeveyni verir: 8 ve 9'un ikisi de 4'e gider. Tam sayı bölmesi, sağ çocuğun indisindeki fazladan 1'i siler.

kokeYol'un her turu indisi yaklaşık yarıya indirir. Döngü, düğümün derinliğinin bir fazlası kadar döner. Tam ağaçta derinlik en çok ⌊log₂ n⌋ olduğundan maliyet O(log n)'dir. Bu sayının küçüklüğü, heap işlemlerinin neden hızlı olduğunu da açıklar: bir öğeyi yukarı taşımak, bu döngüdeki gibi en çok yükseklik kadar adım sürer.

9.3.3Dizide bellek israfı

Dizi gösteriminin zayıf yanı, ağacın şeklinden bağımsız olarak her konuma bir hücre ayırmasıdır. Bir düğümün indisi, düğümün ağaçtaki konumuyla belirlenir; öndeki konumların dolu olup olmadığına bakılmaz. Ağaç tam değilse aradaki boş konumlar dizide boş hücre olarak kalır.

Şekil 9.20'deki zincirde her düğüm bir öncekinin sol çocuğudur, bu yüzden her adımda indis iki katına çıkar: 1, 2, 4, 8, 16. Beş düğüm için 16 hücre gerekir ve 11'i boş kalır. Zincir sağa çarpık olsaydı durum daha da kötüleşirdi. Sağ çocuk indisi 2i + 1 olduğundan indisler 1, 3, 7, 15, 31 olur; beş düğüm için 31 hücre gerekir.

Genel olarak n düğümlü bir ikili ağaç, dizi gösteriminde 2ⁿ − 1 hücreye kadar yer isteyebilir. En kötü durum, yüksekliği n − 1 olan bir zincirdir; dizi bu yükseklikteki mükemmel ağacın bütün konumlarına, yani 2ⁿ − 1 hücreye yer açmak zorundadır. 30 düğümlü sağa çarpık bir zincir bir milyardan fazla hücre ister. Bu, üstel bir israftır ve dizi gösterimini şekli öngörülemeyen ağaçlar için kullanışsız yapar.

9.3.4Bağlı gösterim

İkinci yol, her düğümü ayrı bir nesne yapmak ve çocuklarını referanslarla göstermektir. Bu, bağlı listedeki düğüm fikrinin ağaca uyarlanmış hâlidir. Bağlı listede her düğüm bir sonraki düğümü gösterir; ikili ağaçta ise iki düğümü gösterir: sol çocuğu ve sağ çocuğu.

public class AgacDugumu {
    int veri;
    AgacDugumu sol;   // sol çocuk (yoksa null)
    AgacDugumu sag;   // sağ çocuk (yoksa null)

    public AgacDugumu(int veri) {
        this.veri = veri;   // sol = sag = null
    }
}

AgacDugumu sınıfının üç alanı vardır. veri düğümde saklanan değeri, sol ve sag ise çocuk düğümleri gösterir. Bir çocuk yoksa ilgili referans null'dır. Yapıcı yalnız veri'yi atar. Java'da atanmayan referans alanları varsayılan olarak null olduğu için yeni oluşturulan her düğüm başlangıçta bir yapraktır.

Küçük bir ağaç, düğümleri oluşturup referansları elle bağlayarak kurulabilir:

// 9 kökünde küçük bir ağaç kuralım
AgacDugumu kok = new AgacDugumu(9);
kok.sol = new AgacDugumu(2);
kok.sag = new AgacDugumu(3);
kok.sol.sol = new AgacDugumu(4);

İlk satır kökü, 9 değerli düğümü oluşturur. Sonraki iki satır kökün sol ve sağ çocuğunu, 2 ve 3'ü ekler. Son satır kok.sol.sol zinciriyle 2'nin sol çocuğuna 4'ü yerleştirir. Ortaya çıkan ağaç dört düğümlüdür: 9 kök; 2 ve 3 onun çocukları; 4, 2'nin sol çocuğudur. 2'nin sağ çocuğu ile 3'ün iki çocuğu yoktur.

Bağlı gösterimde bellek yalnız var olan düğümler için ayrılır. Ağaç ne kadar çarpık olursa olsun n düğüm n nesne demektir. Yeni bir düğüm eklemek, bir nesne oluşturup uygun referansı ona yöneltmekten ibarettir; ekleme yeri biliniyorsa bu O(1) sürer. Bedeli ise erişimdedir. Bir düğüme ulaşmak için kökten başlayıp referansları izlemek gerekir; indisle doğrudan atlamak mümkün değildir. Ebeveyne çıkmak da ancak düğüme ayrıca bir ebeveyn referansı eklenirse mümkündür.

Şekil 9.22 referansların nasıl dağıldığını sayma fırsatı verir. Yedi düğümün her birinde iki referans alanı vardır: toplam 14. Bunların 6'sı doludur ve her biri bir kenara karşılık gelir; Teorem 9.1'e göre yedi düğümlü ağaçta 6 kenar vardır. Kalan 8 referans null'dır. Sayıların bu dağılımı rastlantı değildir.

Teoremin pratik anlamı şudur: bağlı ikili ağaçta referans alanlarının yarısından fazlası her zaman boştur. 50 düğümlü bir ağaçta 100 referansın 51'i null'dır. Bu boş alanları değerlendirmek için geliştirilmiş yapılar da vardır. Örneğin “iplikli” (threaded) ikili ağaçlarda boş sol ve sağ referanslar, kök ortada sırasındaki önceki ve sonraki düğümü gösterecek biçimde kullanılır.

9.3.5Dizi mi, bağlı gösterim mi?

İki gösterimin güçlü ve zayıf yanları birbirini tamamlar. Tablo 9.11 bunları yan yana koyar.

Tablodaki üçüncü satır, dizi gösteriminin bir başka avantajını gösterir. i. seviyenin ilk düğümü 2ⁱ indisindedir; o seviyedeki k. düğüm 2ⁱ + k − 1 indisine düşer. Şekil 9.18'deki ağaçta 2. seviyenin 3. düğümü 4 + 3 − 1 = 6 indisindeki F'dir. Bağlı gösterimde aynı düğümü bulmak için seviye seviye gezinmek gerekir.

Seçim için kısa bir kural yeter: ağacın şekli her zaman tam kalıyorsa dizi, şekli öngörülemiyorsa bağlı gösterim tercih edilir. Heap, ekleme ve silmelerde şeklini tam tutar; bu yüzden dizide saklanır. İkili arama ağacı ise eklenen anahtarlara göre herhangi bir şekil alabilir; bağlı gösterim kullanılır.

9.3.6Genel ağaçların gösterimi

Çocuk sayısı sınırsız olduğunda düğüme sabit sayıda referans alanı koymak işe yaramaz. İki yaygın çözüm vardır.

// 1) Çocuk listesi
class GenelDugum {
    int veri;
    List<GenelDugum> cocuklar
        = new ArrayList<>();
}
// 2) İlk çocuk – sonraki kardeş
class KardesDugum {
    int veri;
    KardesDugum ilkCocuk;
    KardesDugum sonrakiKardes;
}

Birinci yolda (GenelDugum) her düğüm, çocuklarının referanslarını bir listede tutar. ArrayList gerektikçe büyüdüğü için çocuk sayısına sınır yoktur. cocuklar listesi üzerinde bir for-each döngüsü, ağaç ADT'sindeki cocuklar(p) metodunun doğrudan karşılığıdır. Bu gösterim sezgiseldir, ama her düğüm ayrı bir liste nesnesi taşır.

İkinci yolda (KardesDugum) her düğüm yalnız iki referans tutar: ilk çocuk (ilkCocuk) ve sonraki kardeş (sonrakiKardes). Bir düğümün bütün çocuklarına ulaşmak için önce ilk çocuğa inilir, sonra kardeş zinciri boyunca sağa yürünür. Çocuk listesi böylece düğümlerin kendisine dağıtılmış bir bağlı listeye dönüşür.

İkinci gösterimde her düğüm tam iki referans taşır. İlk çocuk referansı “sol”, sonraki kardeş referansı “sağ” sayılırsa her genel ağaç bir ikili ağaç olarak saklanabilir. Şekil 9.23'ün sağ yarısı, 45 derece döndürülerek bakıldığında bir ikili ağaçtır: A'nın sol çocuğu B; B'nin sol çocuğu E, sağ çocuğu C; C'nin sağ çocuğu D; E'nin sağ çocuğu F; D'nin sol çocuğu G. Bu dönüşüm, ikili ağaçlar için yazılmış birçok algoritmanın genel ağaçlara da uygulanabilmesini sağlar. Aynı dönüşümle bir orman da tek bir ikili ağaca çevrilebilir: ormandaki ağaçların kökleri birbirinin kardeşi sayılır.

İki gösterim arasında seçim yine kullanım biçimine bağlıdır. Bir düğümün k. çocuğuna sık sık doğrudan erişilecekse çocuk listesi uygundur: cocuklar.get(k) O(1) sürer. İlk çocuk – sonraki kardeş gösteriminde aynı çocuğa kardeş zinciri boyunca k adımda ulaşılır. Buna karşılık bu gösterim, her düğümde sabit ve küçük bir bellek kullanır ve çocuk eklemek için liste nesnesine ihtiyaç duymaz.

9.4Ağaç gezinmeleri

Dizide ya da bağlı listede bütün öğeleri dolaşmanın tek doğal sırası vardır: baştan sona. Ağaçta ise böyle bir tek sıra yoktur. Bir düğüme gelindiğinde önce düğümün kendisi mi işlenecek, yoksa önce alt ağaçları mı? Alt ağaçlardan hangisi önce gezilecek? Yoksa düğümler seviye seviye mi taranacak? Bu soruların her yanıtı farklı bir gezinme verir ve her gezinme farklı bir problemin doğal çözümüdür.

9.4.1Gezinme nedir?

Gezinmeler iki aileye ayrılır. Derinlik öncelikli (depth-first) gezinmeler bir dalın sonuna kadar iner, sonra geri dönüp bir sonraki dala geçer. Bu ailede üç gezinme vardır ve aralarındaki tek fark, kökün alt ağaçlara göre ne zaman ziyaret edildiğidir. Genişlik öncelikli (breadth-first) gezinme ise ağacı seviye seviye tarar: önce kökü, sonra bütün çocukları, sonra bütün torunları ziyaret eder. Bu gezinmeye seviye sırası denir.

Derinlik öncelikli üç gezinmenin adları, kökün sıradaki yerinden gelir: kök başta, ortada ya da sonda. Üçünde de sol alt ağaç sağ alt ağaçtan önce gezilir. Değişen tek şey kökün bu iki alt ağaca göre konumudur. Gezinmeler, ikili ağacın özyinelemeli tanımını izler: kökte ne yapılacağı söylenir, alt ağaçlar için aynı gezinme yeniden uygulanır. Bu yüzden bir gezinmenin çıktısını elle bulurken her alt ağaç, kendi başına küçük bir ağaç gibi ele alınır.

9.4.2Kök başta gezinme

Kök başta (preorder) gezinme üç adımdan oluşur:

1. Kökü ziyaret et.
2. Sol alt ağacı kök başta gez.
3. Sağ alt ağacı kök başta gez.

ziyaret(kok);
kokBasta(kok.sol);
kokBasta(kok.sag);

Bir düğüm, altındaki bütün düğümlerden önce ziyaret edilir. Çıktıda her düğüm, kendi soyunun hepsinden önce gelir. Şekil 9.24'teki ağaçta adımlar şöyledir. Kök 1 ziyaret edilir. Sonra sol alt ağaca, 2 köklü ağaca geçilir ve onun da kökü, 2, hemen ziyaret edilir. 2'nin sol alt ağacı tek düğümlü 4'tür: 4 ziyaret edilir. 2'nin sağ alt ağacı 5'tir: 5 ziyaret edilir. Böylece 1'in sol alt ağacı biter ve sağ alt ağaca geçilir: 3, ardından 3'ün sol çocuğu 6 ve sağ çocuğu 7. Çıktı 1 2 4 5 3 6 7'dir.

Kök başta gezinmenin tipik kullanım alanları, düğümün çocuklarından önce işlenmesinin gerektiği durumlardır. Ağacı kopyalamak bunun en açık örneğidir: bir düğümün kopyası oluşturulmadan onun çocuklarının kopyaları bağlanamaz. Ağacı bir diziye ya da dosyaya yazmak da kök başta sırayla yapılır; dosyayı okuyan kod, her düğümü ebeveyninden sonra gördüğü için ağacı aynı sırayla yeniden kurabilir. İçindekiler sayfası da bir kök başta gezinmedir: bölüm başlığı alt başlıklarından önce yazılır. İfade ağaçlarında kök başta gezinme önek (prefix) gösterimi verir; işleç, işlenenlerinden önce yazılır.

9.4.3Kök ortada gezinme

Kök ortada (inorder) gezinmede kök, iki alt ağacın arasında ziyaret edilir:

1. Sol alt ağacı kök ortada gez.
2. Kökü ziyaret et.
3. Sağ alt ağacı kök ortada gez.

kokOrtada(kok.sol);
ziyaret(kok);
kokOrtada(kok.sag);

Bir düğüm, sol alt ağacındaki bütün düğümlerden sonra ve sağ alt ağacındakilerin hepsinden önce ziyaret edilir. Bu yüzden gezinme kökten başlamaz; kökten başlayıp sola sola inilir ve ilk ziyaret edilen düğüm en soldaki düğüm olur. Şekil 9.24'teki ağaçta 1'den 2'ye, 2'den 4'e inilir. 4'ün sol alt ağacı boştur; 4 ziyaret edilir. 4'ün sağ alt ağacı da boştur ve 2'ye dönülür. 2'nin sol alt ağacı bittiği için 2 ziyaret edilir, ardından sağ alt ağacı olan 5. 1'in sol alt ağacı tamamlanmıştır; şimdi 1 ziyaret edilir. Sağ alt ağaçta yine en sola inilir: 6, sonra 3, sonra 7. Çıktı 4 2 5 1 6 3 7'dir.

Kök ortada çıktısının dikkat çekici bir geometrik anlamı vardır: düğümler, ağaç çiziminde soldan sağa göründükleri sırayla yazılır. Ağaç yatay eksene izdüşürülse, yani her düğüm dikey olarak aşağıya “düşürülse”, sıralama kök ortada çıktısını verir. Şekil 9.24'te soldan sağa sıra 4, 2, 5, 1, 6, 3, 7'dir.

Bu gezinmenin en önemli kullanımı ikili arama ağaçlarındadır. İkili arama ağacında her düğümün solundaki anahtarlar küçük, sağındakiler büyüktür. Kök ortada gezinme önce küçükleri, sonra düğümü, sonra büyükleri yazar. Bu her alt ağaçta tekrarlandığı için anahtarlar küçükten büyüğe sıralı çıkar. Tersi de doğrudur: kök ortada çıktısı sıralı olan bir ikili ağaç, (farklı anahtarlar için) bir ikili arama ağacıdır. İfade ağaçlarında kök ortada gezinme ara ek (infix) gösterimi verir; ama parantezler kaybolur.

9.4.4Kök sonda gezinme

Kök sonda (postorder) gezinmede kök, iki alt ağacın ikisi de bittikten sonra ziyaret edilir:

1. Sol alt ağacı kök sonda gez.
2. Sağ alt ağacı kök sonda gez.
3. Kökü ziyaret et.

kokSonda(kok.sol);
kokSonda(kok.sag);
ziyaret(kok);

Her düğüm, bütün soyundan sonra ziyaret edilir. Kök en son yazılır. Şekil 9.24'teki ağaçta önce en soldaki yaprak 4 ziyaret edilir. Sonra 2'nin sağ çocuğu 5 gelir. 2'nin iki alt ağacı da bittiği için 2 yazılır. 1'in sağ alt ağacına geçilir: önce 6, sonra 7, sonra 3. En sonda kök 1 yazılır. Çıktı 4 5 2 6 7 3 1'dir.

Kök sonda gezinme, bir düğümün işinin çocuklarının sonucuna bağlı olduğu her durumda kullanılır. Ağacı silmek bunun tipik örneğidir: önce çocuklar silinmelidir, yoksa ebeveyn silindiğinde çocuklara ulaşan referanslar kaybolur. Dosya sisteminde bir klasörü silmek de böyle çalışır; boş olmayan bir klasör silinemez, önce içindekiler silinir. Bir klasörün diskte kapladığı toplam alanı hesaplamak da kök sondadır: önce alt klasörlerin boyutları bulunur, sonra toplanır. Ağacın düğüm sayısı ve yüksekliği de aynı mantıkla hesaplanır. İfade ağaçlarında kök sonda gezinme sonek (postfix) gösterimi verir; ifadenin değeri de bu sırayla hesaplanır.

Üç gezinmenin çıktıları arasında kolay denetlenebilir bir ilişki vardır. Kök başta çıktısının ilk öğesi köktür; kök sonda çıktısının son öğesi köktür; kök ortada çıktısında kök, sol ve sağ alt ağaçların arasında durur. Tablo 9.12'deki çıktılarda bu kolayca görülür: 1, kök başta çıktısının başında, kök sonda çıktısının sonunda ve kök ortada çıktısının tam ortasındadır. Bu gözlem, iki gezinme çıktısından ağacı yeniden kurmanın da temelidir.

9.4.5Üç gezinme, tek tur: Euler turu

Derinlik öncelikli üç gezinmeyi tek bir resimde birleştirmenin zarif bir yolu vardır. Ağacın çevresinde, kökün solundan başlayıp kenarlara sol elimizle dokunarak yürüdüğümüzü düşünelim. Bu yürüyüşe Euler turu (Euler tour) denir. Tur ağacın bütün kenarlarını iki kez geçer: bir kez inerken, bir kez çıkarken. Her düğüme de üç kez uğranır: önce solundan, sonra altından, sonra sağından.

Bir düğümü hangi uğrayışta yazdığımıza göre üç gezinmeden biri ortaya çıkar.

• Düğümü solundan geçerken, yani ona ilk kez varıldığında yazarsak kök başta sırası çıkar: A B D E C.
• Altından geçerken, yani sol alt ağacı bitmiş ve sağ alt ağaca henüz başlanmamışken yazarsak kök ortada sırası çıkar: D B E A C.
• Sağından geçerken, yani iki alt ağaç da bitmişken yazarsak kök sonda sırası çıkar: D E B C A.

Yaprakların üç uğrayışı art arda gelir, çünkü yaprağın alt ağaçları boştur. Bu yüzden yapraklar üç gezinmede de aynı göreli sırada çıkar: D, E, C. Bir gezinmeden ötekine yalnız iç düğümlerin yeri değişir. Euler turu, üç gezinmenin aslında aynı turun farklı anları olduğunu gösterir. Tur her kenarı iki kez geçtiği için n düğümlü ağaçta 2(n − 1) kenar adımı sürer; maliyet O(n)'dir. Bu, üç gezinmenin de O(n) olduğunun bir başka açıklamasıdır.

Euler turu fikri gezinmeleri birleştirmekten fazlasına yarar. Bazı işler, bir düğümün hem öncesinde hem sonrasında bir şey yapmayı gerektirir. Örneğin bir ifade ağacını tam parantezli yazarken bir alt ağaca girerken “(” açılır, alttan geçerken işleç yazılır, çıkarken “)” kapanır. Bu, üç uğrayışın üçünün de kullanıldığı bir Euler turudur.

9.4.6Seviye sırası gezinme

Seviye sırası (level-order) gezinme kökten başlar, her seviyeyi soldan sağa tarar, sonra bir alt seviyeye iner. Çizgelerdeki genişlik öncelikli aramanın (breadth-first search, BFS) ağaçtaki hâlidir.

Derinlik öncelikli gezinmelerden farklı olarak seviye sırası, alt ağaçların yapısını izlemez. 2'yi ziyaret ettikten sonra onun çocuğu 4'e değil, kardeşi 3'e geçer. 2'nin çocukları ancak bütün 1. seviye bittikten sonra gelir. Bu yüzden seviye sırası doğal biçimde özyinelemeyle yazılamaz. Özyineleme, bir alt ağacı bitirmeden ötekine geçmez; seviye sırası ise iki alt ağaç arasında sürekli gidip gelir.

Çözüm bir kuyruktur (queue). Kuyruk, önce gelenin önce çıktığı FIFO (first-in, first-out) düzeniyle çalışır. Bir düğüm ziyaret edilirken çocukları kuyruğun arkasına eklenir. Önce eklenen düğümlerin çocukları da önce işlenir. Bir seviyenin bütün düğümleri, bir sonraki seviyenin düğümlerinden önce kuyruğa girdiği için seviyeler sırasıyla taranır.

Seviye sırasının kullanım alanları, seviyelerin anlam taşıdığı işlerdir. Ağacı seviye seviye yazdırmak, her seviyedeki değerlerin toplamını ya da en büyüğünü bulmak, köke en yakın yaprağı bulmak ve ağacın en geniş seviyesini (genişliğini) hesaplamak bunlara örnektir. Köke en yakın yaprak için seviye sırası en uygun yöntemdir. Kuyruktan çıkan ilk yaprak, köke en yakın olanlardan biridir; daha derindeki düğümlere hiç inmeden gezinme durdurulabilir.

9.5Gezinmelerin kodu

Gezinmelerin tanımları özyinelemelidir ve en kısa kodları da özyinelemeli yazılır. Ama özyinelemenin arkasında görünmeyen bir yapı çalışır: çağrı yığını (call stack). Her metot çağrısı yığına bir çerçeve (stack frame) ekler; çerçeve, çağrının parametrelerini, yerel değişkenlerini ve metodun döndükten sonra nereden devam edeceğini tutar. Bu kesim önce üç özyinelemeli gezinmeyi çağrı yığını üzerinde izler. Ardından aynı gezinmeleri, çağrı yığınının yerine açık bir Deque yığını kullanarak özyinelemesiz yazar. Son olarak seviye sırasını bir kuyrukla kodlar.

Bu kesimdeki bütün kodlar bağlı gösterimdeki AgacDugumu sınıfını kullanır. Özyinelemeli izlemeler 9 kökündeki dört düğümlü ağaç üzerinde yapılır: 9'un çocukları 2 ve 3; 2'nin sol çocuğu 4. Bu ağacın yüksekliği 2'dir.

9.5.1Özyinelemeli kök başta ve çağrı yığını

public void kokBasta(AgacDugumu kok) {
  if (kok == null) {
    return;
  }
  System.out.print(kok.veri + " ");
  kokBasta(kok.sol);
  kokBasta(kok.sag);
}

Metodun ilk iş olarak yaptığı şey, ağacın boş olup olmadığını denetlemektir. kok == null ise boş bir alt ağaçtayızdır ve yapılacak bir şey yoktur; metot hemen döner. Bu taban durumdur. Ağaç boş değilse önce kökün değeri yazdırılır (satır 5), sonra sol alt ağaç (satır 6), en son sağ alt ağaç (satır 7) için aynı metot çağrılır. Satır 8'deki kapanış parantezine gelindiğinde çağrı biter ve çerçevesi yığından çıkar.

Taban durumun null ile tanımlanması kodu sadeleştirir. Yaprak için özel bir durum yazılmaz: yaprağın iki çocuğu null'dır ve iki özyinelemeli çağrı hemen döner. Bunun bedeli, her null çocuk için bir çağrı daha yapılmasıdır. Teorem 9.5'e göre n düğümlü ağaçta n + 1 null referans vardır; toplam çağrı sayısı n + (n + 1) = 2n + 1'dir. Dört düğümlü ağaçta 9 çağrı yapılır.

İzlemenin en önemli gözlemi, çağrı yığınının derinliğiyle ilgilidir. 4. ve 5. adımlarda yığında dört çerçeve vardır: 9, 2, 4 ve 4'ün null çocuğu. Bu, izlemedeki en büyük derinliktir. Yığın derinliği, kökten en derin null çocuğa inen yolla belirlenir. Yükseklik h ise bu yolda h + 1 düğüm ve bir null çağrısı vardır; yığında en çok h + 2 çerçeve bulunur. Burada h = 2 ve en çok 2 + 2 = 4 çerçeve görülür.

Zaman maliyeti O(n)'dir: her düğüm için bir çağrı ve her null referans için bir çağrı yapılır; her çağrı sabit iş yapar. Ek bellek, yığın derinliği kadardır: O(h). Dengeli ağaçta bu O(log n), çarpık ağaçta O(n)'dir.

9.5.2Özyinelemeli kök ortada

public void kokOrtada(AgacDugumu kok) {
  if (kok == null) {
    return;
  }
  kokOrtada(kok.sol);
  System.out.print(kok.veri + " ");
  kokOrtada(kok.sag);
}

Kod kök başta ile aynıdır; tek fark yazdırma satırının iki özyinelemeli çağrının arasına alınmasıdır. Bu küçük değişiklik, değerin hangi anda yazılacağını değiştirir. Bir çağrı başladığında değer hemen yazılmaz; önce sol alt ağaç bütünüyle gezilir. Değer, sol çağrı döndükten sonra, satır 6'da yazılır.

Çıktı 4 2 9 3'tür. Kök 9, sol alt ağacının (4 ve 2) arkasından, sağ alt ağacının (3) önünden gelir. İzlemede 9 numaralı çerçevenin ömrüne bakmak öğreticidir. Çerçeve ilk adımda oluşur, ama 9 ancak 11. adımda yazılır. Arada çerçeve, satır 5'teki çağrının dönmesini bekler. Yığındaki bir çerçeve, “burada yarım kalmış bir iş var” bilgisini taşır.

9.5.3Özyinelemeli kök sonda

public void kokSonda(AgacDugumu kok) {
  if (kok == null) {
    return;
  }
  kokSonda(kok.sol);
  kokSonda(kok.sag);
  System.out.print(kok.veri + " ");
}

Bu kez yazdırma iki çağrının arkasına, satır 7'ye alınmıştır. Sol çağrı satır 5'ten, sağ çağrı satır 6'dan yapılır. Bir düğümün değeri, iki alt ağacının da tamamen gezilmesinden sonra yazılır.

Çıktı 4 2 3 9'dur. Üç izleme yan yana konduğunda çağrı sırasının hiç değişmediği görülür. Üç metotta da çağrılar aynı sırayla yapılır ve aynı sırayla döner: 9, 2, 4, null, null, … Değişen tek şey, yazdırmanın bu sıranın hangi noktasında yapıldığıdır. Bu, Euler turu gözleminin kod düzeyindeki karşılığıdır. Çağrının başlangıcı düğümün solundan geçişe, iki çağrının arası altından geçişe, çağrının sonu sağından geçişe karşılık gelir.

9.5.4Yığınla kök başta

Özyineleme, çağrı yığınını sistemin kendisine bırakır. Çağrı yığınının boyutu ise sınırlıdır; Java'da varsayılan ayarlarla birkaç bin ile birkaç on bin çerçeve arasında bir derinlikte StackOverflowError alınır. Çok derin, örneğin yüz binlerce düğümlü bir zincir biçimindeki ağaçta özyinelemeli gezinme çöker. Çözüm, çağrı yığınının yaptığı işi java.util.Deque ile açık bir yığına yaptırmaktır. Bu yığın heap bellekte yaşar ve ancak bellek bitince dolar.

public void kokBastaYigin(AgacDugumu kok) {
  if (kok == null) return;
  Deque<AgacDugumu> yigin = new ArrayDeque<>();
  yigin.push(kok);
  while (!yigin.isEmpty()) {
    AgacDugumu gecici = yigin.pop();
    System.out.print(gecici.veri + " ");
    if (gecici.sag != null)
      yigin.push(gecici.sag);  // önce sağ
    if (gecici.sol != null)
      yigin.push(gecici.sol);  // sol üstte
  }
}

Kök başta, açık yığınla yazılması en kolay gezinmedir. Bir düğüm yığından çıkarıldığı anda yazdırılabilir, çünkü kök başta gezinmede düğüm çocuklarından önce gelir. Döngünün her turu üst düğümü çıkarır (pop), değerini yazdırır, sonra çocuklarını yığına iter (push). İtme sırası önemlidir: önce sağ, sonra sol. Yığın LIFO çalıştığı için en son itilen sol çocuk üstte kalır ve bir sonraki turda önce o çıkar. Böylece sol alt ağaç bütünüyle gezildikten sonra sağ çocuk sıraya gelir.

Yığının içeriği, özyinelemedeki “yarım kalmış işler”in listesidir. 2. turun sonunda yığında 3, 5, 4 vardır. Bu, “önce 4'ün alt ağacı, sonra 5'in alt ağacı, sonra 3'ün alt ağacı gezilecek” demektir. Özyinelemeli sürümde aynı bilgi, 2 ve 9 çerçevelerinin hangi satırda beklediğinde saklıydı.

Her düğüm yığına tam bir kez itilir ve bir kez çıkarılır; döngü n tur döner, zaman O(n)'dir. Yığının boyutu yükseklikle sınırlıdır: her seviyeden en çok bir sağ kardeş beklerken bir de üstteki düğüm bulunur. Bu ağaçta yığın en çok 3 öğe tutmuştur (2. turun sonunda). Ek bellek O(h)'dir.

9.5.5Yığınla kök ortada

Kök ortada gezinmede bir düğüm, yığına girdiği anda yazdırılamaz; önce sol alt ağacının bitmesi gerekir. Bu yüzden yığın burada “sonra yazdırılacak” düğümleri tutar. Algoritma iki hareketten oluşur. gecici bir düğümü gösterdiği sürece o düğüm yığına itilir ve sola inilir. gecici null'a ulaştığında sola gidecek yer kalmamıştır; yığının üstündeki düğümün sol alt ağacı bitmiştir. O düğüm çıkarılır, yazdırılır ve sağ alt ağacına geçilir.

public void kokOrtadaYigin(AgacDugumu kok) {
  if (kok == null) return;
  Deque<AgacDugumu> yigin = new ArrayDeque<>();
  AgacDugumu gecici = kok;
  while (!yigin.isEmpty() || gecici != null) {
    if (gecici != null) {
      yigin.push(gecici);
      gecici = gecici.sol;
    } else {
      gecici = yigin.pop();
      System.out.print(gecici.veri + " ");
      gecici = gecici.sag;
    }
  }
}

Döngü koşulu iki parçalıdır: !yigin.isEmpty() || gecici != null. Yalnız yığının boşluğuna bakmak yetmez. Kök yazdırıldıktan hemen sonra yığın boş olabilir; ama gecici kökün sağ çocuğunu gösterir ve sağ alt ağaç henüz gezilmemiştir. İzleme bu anı içerir. Örnek olarak 1'in çocukları 2 ve 3, 2'nin çocukları 4 ve 5, 3'ün yalnız sol çocuğu 6 olan ağacı kullanalım.

8. adım, döngü koşulunun neden iki parçalı olduğunu gösterir. Bu adımın sonunda yığın boştur; koşul yalnız !yigin.isEmpty() olsaydı döngü burada biter ve 3 ile 6 hiç yazdırılmazdı. gecici != null parçası, gezilmeyi bekleyen bir sağ alt ağaç olduğunu yakalar. Döngü ancak yığın boş ve gecici null olduğunda, 12. adımdan sonra biter. Çıktı 4 2 5 1 6 3'tür.

Her düğüm bir kez itilir ve bir kez çıkarılır. Ayrıca her null çocuğa bir kez ulaşılır. Toplam iş O(n)'dir. Yığın her an kökten gecici'ye inen yol üzerindeki, sol alt ağacı henüz bitmemiş düğümleri tutar; boyutu en çok h + 1'dir. Ek bellek O(h)'dir.

9.5.6Yığınla kök sonda

Kök sonda en zor yığınlı gezinmedir. Bir düğüm ancak iki alt ağacı da bittiğinde yazdırılabilir. Yığının üstünde bir düğüm görüldüğünde sol alt ağacının bittiği bilinir, ama sağ alt ağacın bitip bitmediği bilinmez. Kod bu yüzden yığındaki düğümü hemen çıkarmaz; önce peek ile bakar.

public void kokSondaYigin(AgacDugumu kok) {
  AgacDugumu simdiki = kok;
  Deque<AgacDugumu> yigin = new ArrayDeque<>();
  while (simdiki != null || !yigin.isEmpty()) {
    if (simdiki != null) {
      yigin.push(simdiki);
      simdiki = simdiki.sol;
    } else {
      AgacDugumu gecici = yigin.peek().sag;
      if (gecici == null) {
        gecici = yigin.pop();
        System.out.print(gecici.veri + " ");
        while (!yigin.isEmpty()
           && gecici == yigin.peek().sag) {
          gecici = yigin.pop();
          System.out.print(gecici.veri + " ");
        }
      } else {
        simdiki = gecici;
      }
    }
  }
}

Kodun mantığı üç parçadır.

• Sola inme. simdiki null değilse düğüm yığına itilir ve sola inilir. Bu, kök ortadaki sola inmenin aynısıdır.
• Sağ alt ağaca geçme. Sola gidecek yer kalmayınca üstteki düğümün sağ çocuğuna bakılır (yigin.peek().sag). Sağ çocuk varsa düğüm henüz yazdırılamaz; simdiki sağ çocuğa atanır ve o alt ağaca girilir. Düğüm yığında kalır.
• Yazdırma ve yukarı çıkma. Sağ çocuk yoksa üstteki düğümün iki alt ağacı da bitmiştir; düğüm çıkarılır ve yazdırılır. Ardından iç while döngüsü yukarı bakar. Az önce yazdırılan düğüm, yığındaki yeni üst düğümün sağ çocuğuysa, o ebeveynin sağ alt ağacı da bitmiştir; o da çıkarılıp yazdırılır. Bu, ebeveyn zinciri boyunca sağ çocuk olmayı sürdüren düğümlerde tekrarlanır.

İç döngüdeki gecici == yigin.peek().sag karşılaştırması referans eşitliğidir: aynı nesne mi, diye sorar. Bu karşılaştırma, “bu ebeveynin sağ alt ağacından şimdi mi dönüyoruz?” sorusunun yanıtıdır. Yanıt evetse ebeveyn yazdırılır. Yanıt hayırsa, yani az önce yazdırılan düğüm sol çocuksa, ebeveynin sağ alt ağacına henüz girilmemiştir ve iç döngü durur. İzleme 1'in çocukları 2 ve 3, 2'nin çocukları 4 ve 5, 3'ün yalnız sağ çocuğu 6 olan ağaç üzerinde yapılır.

İzlemenin son kısmı iç döngünün gücünü gösterir. 15. adımda 6 yazdırılınca iç döngü art arda iki düğümü daha yazdırır. 6, 3'ün sağ çocuğudur; 3'ün iki alt ağacı da bitmiştir. 3 de 1'in sağ çocuğudur; 1'in de iki alt ağacı bitmiştir. Tek bir yaprak, ebeveyn zinciri boyunca bir dizi düğümün “tamamlanmasını” tetiklemiştir. 3'ün sol çocuğunun olmaması da kodu bozmaz. 12. adımda simdiki = 3.sol doğrudan null olur ve 13. adımda sağ alt ağaca geçilir.

Maliyet yine O(n)'dir. Her düğüm bir kez itilir, bir kez çıkarılır; her peek ya bir çıkarma ya da bir sağ alt ağaca geçişle sonuçlanır. Yığın kökten o anki düğüme inen yolu tuttuğu için boyutu en çok h + 1'dir. Aynı sonuca daha kısa bir yoldan da varılır. Yığınlı kök başta kodunda çocuklar ters sırayla (önce sol, sonra sağ) itilirse “kök, sağ, sol” sırası çıkar. Bu çıktı ikinci bir yığınla ters çevrilir. Ters çevrilmiş “kök, sağ, sol” tam olarak “sol, sağ, kök”tür. Bu yöntem kolaydır, ama O(n) ek bellek ister.

9.5.7Kuyrukla seviye sırası

public void seviyeSirasi(AgacDugumu kok) {
  if (kok == null) return;
  Queue<AgacDugumu> kuyruk = new LinkedList<>();
  kuyruk.add(kok);
  while (!kuyruk.isEmpty()) {
    AgacDugumu gecici = kuyruk.poll();
    System.out.print(gecici.veri + " ");
    if (gecici.sol != null)
      kuyruk.add(gecici.sol);
    if (gecici.sag != null)
      kuyruk.add(gecici.sag);
  }
}

Seviye sırası kodu, yığınla kök başta koduna çok benzer. Üç fark vardır. Yığının yerinde bir Queue (burada LinkedList) bulunur. push ve pop yerine add (arkaya ekle) ve poll (önden çıkar) kullanılır. Çocuklar doğal sırayla eklenir: önce sol, sonra sağ. Kuyruk FIFO olduğu için önce eklenen sol çocuk önce çıkar; ters sırayla eklemeye gerek yoktur.

İzleme 4 kökündeki ağaç üzerinde yapılır: 4'ün çocukları 3 ve 7; 3'ün çocukları 5 ve 8; 7 yapraktır.

2. tur seviye sırasının özünü gösterir. 3 çıkarılırken çocukları 5 ve 8 kuyruğun arkasına, 7'nin arkasına eklenir. 7, 3 ile aynı seviyededir ve 3'ün çocuklarından önce işlenir. Kök başta olsaydı 3'ten sonra hemen 5 ve 8 gelirdi; çıktı 4 3 5 8 7 olurdu. Seviye sırası ise 4 3 7 5 8 verir.

Her düğüm kuyruğa bir kez girer ve bir kez çıkar; zaman O(n)'dir. Ek bellek ise yığınlı gezinmelerden farklı bir büyüklüğe bağlıdır. Kuyrukta aynı anda bulunan düğümler en çok iki ardışık seviyeye yayılır. Bu yüzden kuyruğun boyutu ağacın genişliğiyle, yani en kalabalık seviyedeki düğüm sayısı w ile sınırlanır; ek bellek O(w)'dir. Bu izlemede kuyruk en çok 3 düğüm tutmuştur. Mükemmel ağaçta son seviyede yaklaşık n/2 düğüm bulunur; seviye sırası bu ağaçlarda O(n) bellek harcar. Yığınlı kök ortada ise aynı ağaçta yalnız O(log n) bellek kullanır.

9.6Gezinmelerin uygulamaları

Gezinmeler yalnız düğümleri yazdırmak için değildir. Ağaç üzerinde çalışan hemen her algoritma bir gezinmedir: düğümleri belirli bir sırayla ziyaret eder ve her ziyarette bir iş yapar. Bu kesim, gezinme kalıbının nasıl gerçek problemlere uygulandığını örneklerle gösterir.

9.6.1İfade ağacı

Bir aritmetik ifade doğal olarak bir ağaçtır. (3 + 4) × (5 − 2) ifadesinde en son yapılacak işlem çarpmadır; çarpmanın iki işleneni de birer alt ifadedir. Bu yapı bir ikili ağaçla doğrudan temsil edilir.

Ağaçta parantez yoktur; parantezlerin görevini ağacın yapısı üstlenir. Toplama ve çıkarma, çarpmadan daha derinde durduğu için önce hesaplanır. İşlem önceliği ve parantez bilgisi ağacın şekline gömülmüştür. Aynı ağaç, üç derinlik öncelikli gezinmeyle üç farklı gösterim verir.

Önek ve sonek gösterimler parantez gerektirmez; işleçlerin ve işlenenlerin sırası ifadeyi tek anlamlı belirler. Kök ortada çıktısı ise parantezsiz yazıldığında anlam değiştirir. 3 + 4 × 5 − 2 olağan öncelik kurallarıyla 3 + 20 − 2 = 21'e eşit görünse de bu bir rastlantıdır; okunan ifade ağaçtaki ifade değildir. Doğru ara ek gösterimi elde etmek için her iç düğümün alt ağacı parantez içine alınmalıdır. Bu da düğüme girerken “(”, çıkarken “)” yazan bir Euler turudur.

9.6.2Kod izleme: hesapla()

İfade ağacının değeri kök sonda mantığıyla hesaplanır: bir işleç, iki işleneninin değeri bilinmeden uygulanamaz. Aşağıdaki kod, yaprakta bir sayı (sayi), iç düğümde bir işleç karakteri (islec) tutan bir IfadeDugumu sınıfı varsayar.

int hesapla(IfadeDugumu d) {
  if (d.sol == null && d.sag == null)
    return d.sayi;               // yaprak: işlenen
  int a = hesapla(d.sol);
  int b = hesapla(d.sag);
  switch (d.islec) {             // iç düğüm: işleç
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    default:  return a / b;
  }
}

Metot önce düğümün yaprak olup olmadığına bakar. İki çocuğu da yoksa düğüm bir işlenendir ve sayısı döndürülür; taban durum budur. Değilse sol alt ağacın değeri a'ya (satır 4), sağ alt ağacın değeri b'ye (satır 5) hesaplatılır. En son switch ile işleç uygulanır. Sol ve sağın sırası çıkarma ile bölmede önemlidir: a - b'de a sol işlenendir. İfade ağacı dolu olduğu için bir iç düğümün iki çocuğu da vardır; tek çocuklu düğüm durumu ele alınmaz.

Değerler ağaçta aşağıdan yukarı akar: yapraklar sayılarını, iç düğümler hesapladıkları değeri ebeveynlerine verir. İşleçlerin uygulanma sırası +, −, ×'tir; bu tam olarak kök sonda sırasıdır ve sonek gösterimdeki 3 4 + 5 2 − × dizisinin okunuşuyla örtüşür. Sonek ifadeyi bir yığınla değerlendiren algoritma da aynı işi yapar; burada yığın, özyinelemenin çağrı yığınıdır. Her düğüm bir kez işlenir; zaman O(n), ek bellek O(h)'dir.

9.6.3En büyük değeri bulma

Sıralı olmayan bir ikili ağaçta en büyük değeri bulmak için her düğüme bakmak gerekir. Özyinelemeli çözüm şöyle düşünür: ağacın en büyüğü, kökün değeri, sol alt ağacın en büyüğü ve sağ alt ağacın en büyüğü arasındaki en büyüktür.

public int enBuyukBul(AgacDugumu kok) {
  if (kok == null) {
    return Integer.MIN_VALUE;
  }
  int sonuc = kok.veri;
  int sol = enBuyukBul(kok.sol);
  int sag = enBuyukBul(kok.sag);
  if (sol > sonuc)
    sonuc = sol;
  if (sag > sonuc)
    sonuc = sag;
  return sonuc;
}

Boş ağaç için hangi değerin döndürüleceği dikkat ister. Boş ağacın “en büyük değeri” yoktur; ama döndürülen değer karşılaştırmayı bozmamalıdır. Integer.MIN_VALUE (−2³¹) hiçbir int değerden büyük olamaz; sol > sonuc karşılaştırmasında hiçbir zaman kazanmaz. Bu yüzden boş alt ağaç sonucu etkilemez. Metodun gövdesi kök sonda kalıbındadır: iki alt ağacın sonucu alınır, sonra kökle birleştirilir.

Tablo, çağrıların bitiş sırasına göre yazılmıştır: 5, 8, 3, 7, 4. Bu, kök sonda sırasıdır. Her düğüm bir kez ziyaret edilir ve her null çocuk için bir çağrı yapılır; beş düğümlü ağaçta toplam 11 çağrı vardır. Zaman O(n)'dir. Ağaç bir ikili arama ağacı olsaydı en büyük değer çok daha hızlı bulunurdu: kökten sağa sağa inmek yeterdi ve maliyet O(h) olurdu. Sıralı olmayan bir ağaçta ise bütün düğümlere bakmaktan kaçınılamaz.

9.6.4Özyinelemeli ağaç fonksiyonları

hesapla ve enBuyukBul aynı kalıbı izler. Boş ağaç için bir taban değer döndürülür; boş olmayan ağaçta iki alt ağacın sonucu özyinelemeyle alınır ve kökle birleştirilir. Bu kalıp, ağacın birçok temel özelliğini birkaç satırla hesaplamaya yeter.

int boyut(AgacDugumu k) {            // düğüm sayısı
    if (k == null) return 0;
    return 1 + boyut(k.sol) + boyut(k.sag);
}

int yukseklik(AgacDugumu k) {        // kenar sayısı
    if (k == null) return -1;        // boş ağaç: -1
    return 1 + Math.max(yukseklik(k.sol),
                        yukseklik(k.sag));
}

int yaprakSayisi(AgacDugumu k) {
    if (k == null) return 0;
    if (k.sol == null && k.sag == null) return 1;
    return yaprakSayisi(k.sol) + yaprakSayisi(k.sag);
}

• boyut(k) düğüm sayısını verir. Boş ağaçta 0 düğüm vardır. Boş olmayan ağaçta kök için 1, sol alt ağaçtakiler için boyut(k.sol), sağdakiler için boyut(k.sag) toplanır.
• yukseklik(k) yüksekliği kenar sayısıyla verir. Taban durumda −1 döndürülür. Bu seçim ilk bakışta tuhaf gelir, ama tanımı tutarlı kılar: yaprağın iki çocuğu da boştur ve yüksekliği 1 + max(−1, −1) = 0 çıkar. Taban durumda 0 döndürülseydi yaprağın yüksekliği 1 olurdu; bu da yüksekliği düğüm sayısıyla ölçmek demektir.
• yaprakSayisi(k) iki taban durum kullanır. Boş ağaçta 0 yaprak vardır. İki çocuğu da null olan düğüm bir yapraktır ve 1 döndürür. Diğer düğümlerde yaprak sayısı, iki alt ağacın yaprak sayılarının toplamıdır; düğümün kendisi yaprak olmadığı için eklenmez.

9 kökündeki dört düğümlü ağaçta (9'un çocukları 2 ve 3; 2'nin sol çocuğu 4) bu metotlar boyut = 4, yukseklik = 2 ve yaprakSayisi = 2 verir; yapraklar 4 ve 3'tür. Üç metot da her düğümü bir kez işler: O(n) zaman, çağrı yığını için O(h) alan.

9.6.5Kod izleme: boyut()

boyut'un izlemesi, değerlerin alt ağaçlardan yukarı nasıl taşındığını gösterir. Bütün özyinelemeli çağrılar tek satırdan, satır 3'ten yapılır; Java ifadeyi soldan sağa hesapladığı için önce boyut(k.sol), sonra boyut(k.sag) çağrılır.

İzlemede dokuz çağrı yapılır: dört düğüm ve beş null çocuk için. Bu, 2n + 1 = 9'dur. Her düğümün döndürdüğü sayı, o düğümün alt ağacındaki düğüm sayısıdır: 4 için 1, 2 için 2, 3 için 1, 9 için 4. Böylece tek bir kök sonda gezinmesi bütün alt ağaçların boyutunu da hesaplamış olur. Bu bilgi düğümlerde saklanırsa, örneğin “ağaçtaki k. en küçük anahtar” gibi sorular hızla yanıtlanabilir.

9.6.6Kod izleme: yukseklik()

yukseklik'te sol çağrı satır 3'ten, sağ çağrı satır 4'ten yapılır: Math.max'ın iki argümanı iki ayrı satıra yazılmıştır. İzleme aynı ağaç üzerindedir.

Sonuç 2'dir: kökten en derin yaprak 4'e giden 9–2–4 yolu iki kenarlıdır. Çağrı yapısı boyut ile aynıdır, birleştirme işlemi farklıdır: toplama yerine en büyük alınır. Kalıbın gücü buradadır. Taban değeri ve birleştirme işlemi değiştirilerek aynı iskeletle düğümlerin toplamı, en küçük değer, belirli bir değerin kaç kez geçtiği gibi birçok özellik hesaplanabilir.

9.6.7Kod izleme: yaprakSayisi()

yaprakSayisi bir yaprakta alt çağrı yapmadan döner. Bu yüzden izlemesi daha kısadır: yaprakların null çocukları hiç çağrılmaz.

Bu izlemede yalnız beş çağrı yapılır: dört düğüm ve 2'nin boş sağ çocuğu. boyut'taki dokuz çağrıdan azdır, çünkü yaprak denetimi yaprakların null çocuklarına inmeyi önler. İkinci taban durumun bir başka işlevi daha vardır. O satır olmasaydı metot boş ağaçta 0 döndürür ve hiçbir zaman 1 üretmezdi; her ağaç için sonuç 0 çıkardı. Yaprak, sayılacak şeyin kendisidir; bu yüzden ayrı bir taban durum ister.

9.6.8Gezinmelerden ağacı yeniden kurma

Bir ağacın tek bir gezinme çıktısı, ağacı belirlemez. Örneğin kök başta çıktısı 1 2 olan iki ağaç vardır: 2, 1'in sol çocuğu da olabilir sağ çocuğu da. Ama iki uygun gezinme birlikte verilirse ve düğüm değerleri birbirinden farklıysa ağaç tek biçimde kurulabilir.

Kurma yöntemi gezinmelerin tanımından çıkar. Kök başta çıktısının ilk öğesi köktür. Bu değer kök ortada çıktısında bulunur. Kök ortada çıktısında kökün solundaki öğeler sol alt ağacı, sağındakiler sağ alt ağacı oluşturur. Sol alt ağaçtaki öğe sayısı bilindiği için kök başta çıktısında da hangi öğelerin sol alt ağaca ait olduğu bulunur. Aynı işlem iki alt ağaca özyinelemeyle uygulanır. Kök sonda ile çalışırken tek fark, kökün çıktının son öğesi olmasıdır.

Kök başta ile kök sonda birlikte neden yetmez? İki gezinmede de kökün yeri bellidir, ama sol ve sağ alt ağaçları ayıran bir bilgi yoktur. Kök başta A B ve kök sonda B A çıktıları hem “B, A'nın sol çocuğu” hem de “B, A'nın sağ çocuğu” ağacına uyar. Ayrımı yalnız kök ortada çıktısı yapar: soldaki çocuk kökten önce, sağdaki sonra yazılır. Her düğümün 0 ya da 2 çocuğu olan dolu ağaçlarda ise belirsizlik kalkar; çünkü tek çocuklu düğüm yoktur.

int p = 0; // pre[] içinde sıradaki kök
AgacDugumu kur(int[] pre, int[] in, int bas, int son) {
    if (bas > son) return null;       // boş aralık
    AgacDugumu k = new AgacDugumu(pre[p++]);
    int m = bas; while (in[m] != k.veri) m++;
    k.sol = kur(pre, in, bas, m - 1); // soldakiler
    k.sag = kur(pre, in, m + 1, son); // sağdakiler
    return k;
}

kur(pre, in, bas, son), kök ortada dizisinin in[bas..son] aralığındaki öğelerden bir alt ağaç kurar ve kökünü döndürür. Aralık boşsa (bas > son) alt ağaç da boştur ve null döner. Değilse kök başta dizisinde sıradaki öğe, pre[p], bu alt ağacın köküdür; düğüm oluşturulur ve p bir artırılır. p bir alan olduğu için bütün çağrılar arasında paylaşılır ve kök başta dizisinde ileri doğru tek bir kez ilerler. Sonra kökün değeri kök ortada aralığında aranır ve indisi m'ye yazılır. in[bas..m−1] sol, in[m+1..son] sağ alt ağaçtır. Önce sol alt ağaç kurulur. Bu sıra zorunludur, çünkü kök başta dizisinde sol alt ağacın öğeleri sağdakilerden önce gelir.

Maliyeti belirleyen, m'yi bulan doğrusal aramadır. Her düğüm için kendi aralığında bir arama yapılır. Dengeli ağaçta aralıklar her seviyede yarıya iner ve toplam O(n log n) olur. Çarpık ağaçta ise aralıklar birer birer küçülür ve toplam O(n²)'ye çıkar. İyileştirme kolaydır: in dizisindeki her değerin indisi önceden bir eşlemeye (HashMap) yazılırsa m O(1)'de bulunur ve kurma O(n)'e iner.

9.6.9Gezinmelerin maliyeti

Bütün gezinmeler her düğümü bir kez ziyaret eder; ziyaret başına iş sabittir. Zaman maliyetleri bu yüzden aynıdır: O(n). Gezinmeler ek bellekte ayrışır.

Derinlik öncelikli gezinmelerde belleği yükseklik belirler. Dengeli ağaçta h ≈ log₂ n olduğundan bellek küçüktür. Çarpık ağaçta ise h = n − 1'dir ve bellek O(n)'e çıkar. Bu durumda özyinelemeli sürüm, çağrı yığınının sınırına takılıp StackOverflowError verebilir; yığınlı sürüm aynı belleği heap'te kullandığı için çalışmayı sürdürür.

Seviye sırasında belleği genişlik belirler. Mükemmel ağaçta son seviyede yaklaşık n/2 düğüm vardır; kuyruk bu seviyeyi tutarken O(n) bellek ister. Çarpık ağaçta ise her seviyede bir düğüm vardır ve kuyruk hiçbir zaman bir iki öğeden fazlasını tutmaz. İki aile böylece birbirinin tersi davranır. Derin ve dar ağaçta seviye sırası, geniş ve sığ ağaçta derinlik öncelikli gezinme daha az bellek harcar. Örneğin n düğümlü mükemmel ağaçta seviye sırasının ek belleği O(n), özyinelemeli kök ortadanın ek belleği O(log n)'dir.

9.7Sık yapılan hatalar

Ağaç kodlarındaki hataların çoğu birkaç tipe ayrılır. Aşağıdaki tablo, notun içinde ayrı ayrı anlatılan hataları bir arada verir; bir ağaç kodunu gözden geçirirken kontrol listesi olarak kullanılabilir.

Tablodaki hataların ortak bir kökü vardır: ağacın özyinelemeli yapısını kodda tam yansıtmamak. Bir ağaç ya boştur ya da bir kök ve iki alt ağaçtan oluşur. Doğru bir ağaç metodu bu iki durumu da açıkça ele alır. Boş ağaç için anlamlı bir değer döndürür. Boş olmayan ağaçta alt ağaçların sonuçlarını, kökün nerede yer alacağına dikkat ederek birleştirir. Gezinmeler arasındaki fark da yalnız bu son noktadadır: kök, alt ağaçların önünde mi, arasında mı, arkasında mı?

9.8Özet

• Ağaç, düğümler ve onları ebeveyn–çocuk ilişkisiyle bağlayan kenarlardan oluşan hiyerarşik bir yapıdır. Tek bir kök vardır; kök dışındaki her düğümün tam bir ebeveyni vardır. Bu yüzden döngü yoktur, n düğümlü ağaçta n − 1 kenar bulunur ve iki düğüm arasında tek bir yol vardır.
• İç düğüm en az bir çocuğu olan, yaprak hiç çocuğu olmayan düğümdür. Ebeveyn, çocuk, kardeş, ata ve soy aile ağacındaki anlamlarıyla kullanılır; aynı seviyede olmak kardeş olmak demek değildir.
• Derece çocuk sayısıdır. Derinlik kökten düğüme, yükseklik düğümden en uzak yaprağa kenar sayısıdır. Ağacın yüksekliği kökün yüksekliği, yani en büyük derinliktir. Düğüm sayısıyla ölçen kaynaklarda bütün değerler bir fazladır.
• İkili ağaçta her düğümün en çok iki çocuğu vardır ve sol ile sağ ayrılır. Dolu: her düğümde 0 ya da 2 çocuk. Tam: son seviye dışındakiler dolu, son seviye soldan dolar. Mükemmel: bütün yapraklar aynı derinlikte; hem dolu hem tam.
• İkili ağaçta d derinliğinde en çok 2^d, yüksekliği h olan ağaçta en çok 2^h+1 − 1 düğüm bulunur; ⌊log₂ n⌋ ≤ h ≤ n − 1. Dolu ikili ağaçta yaprak sayısı iç düğüm sayısından bir fazladır.
• Dizi gösteriminde 1 tabanlı indis i'nin çocukları 2i ve 2i + 1, ebeveyni ⌊i/2⌋'dir; tam ağaçlarda (heap) idealdir, çarpık ağaçlarda 2ⁿ − 1 hücreye kadar israf eder. Bağlı gösterimde her düğüm sol ve sağ referans taşır; n + 1 referans null'dır. Genel ağaçlar çocuk listesiyle ya da ilk çocuk – sonraki kardeş gösterimiyle saklanır.
• Kök başta K-S-S, kök ortada S-K-S, kök sonda S-S-K sırasıyla gezer; üçü de aynı Euler turunun farklı anlarıdır. Seviye sırası ağacı seviye seviye bir kuyrukla tarar.
• Özyinelemeli gezinmeler çağrı yığınında en çok h + 2 çerçeve kullanır. Açık yığınlı sürümler aynı işi heap bellekte yapar: kök başta için önce sağ, sonra sol itilir; kök ortada sola iner ve çıkarırken yazar; kök sonda peek ile sağ alt ağacın bitip bitmediğine bakar.
• İfade ağacında kök başta önek, kök sonda sonek, parantezli kök ortada ara ek gösterimi verir; değer kök sonda mantığıyla hesaplanır. boyut, yukseklik, yaprakSayisi ve enBuyukBul aynı kalıbı izler: boş ağaç için taban değer, sonra alt ağaç sonuçlarının birleştirilmesi.
• Kök ortada ile kök başta (ya da kök sonda) çıktıları, değerleri farklı bir ikili ağacı tek biçimde belirler. Bütün gezinmeler O(n) zaman ister; ek bellek derinlik öncelikli gezinmelerde O(h), seviye sırasında O(w)'dir.

9.9Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• ağaç tree
• düğüm node
• kenar edge
• kök root
• ebeveyn parent
• çocuk child
• kardeş sibling
• ata ancestor
• soy descendant
• yaprak leaf
• iç düğüm internal node
• derece degree
• derinlik depth
• seviye level
• yükseklik height
• yol path
• alt ağaç subtree
• döngü cycle
• konum position
• soyut veri tipi abstract data type (ADT)
• ikili ağaç binary tree
• dolu ikili ağaç full binary tree
• tam ikili ağaç complete binary tree
• mükemmel ikili ağaç perfect binary tree
• ikili arama ağacı binary search tree (BST)
• heap heap
• gezinme traversal
• kök başta preorder
• kök ortada inorder
• kök sonda postorder
• seviye sırası level-order
• genişlik öncelikli arama breadth-first search (BFS)
• derinlik öncelikli arama depth-first search (DFS)
• ifade ağacı expression tree
• özyineleme recursion
• taban durum base case
• çağrı yığını call stack
• çerçeve stack frame
• kuyruk queue

9.10Kendini Dene

1. Bir genel ağaçta A köktür; A'nın çocukları B ve C, B'nin çocukları D, E, F, C'nin çocuğu G, G'nin çocukları H ve I'dır. Yapraklar ve iç düğümler hangileridir? Ağacın derecesi, kenar sayısı ve yüksekliği kaçtır? G'nin derinliği ve yüksekliği nedir?

   Cevap

   Yapraklar D, E, F, H, I; iç düğümler A, B, C, G'dir (5 + 4 = 9 düğüm). En büyük derece B'nindir (3); ağacın derecesi 3'tür. Kenar sayısı 9 − 1 = 8'dir. En uzun yol A→C→G→H'dir; ağacın yüksekliği 3'tür. G'nin derinliği 2 (A→C→G), yüksekliği 1'dir (G→H).

2. Yüksekliği 5 olan bir ikili ağaçta en az ve en çok kaç düğüm bulunabilir? 100 düğümlü bir ikili ağacın yüksekliği en az kaç olabilir?

   Cevap

   En az h + 1 = 6 (zincir), en çok 2⁶ − 1 = 63 düğüm (mükemmel ağaç). 100 düğüm için yükseklik 5 yetmez (en çok 63 düğüm), 6 yeter (en çok 127 düğüm); en az yükseklik ⌊log₂ 100⌋ = 6'dır.

3. 21 düğümlü dolu bir ikili ağaçta kaç yaprak ve kaç iç düğüm vardır? Aynı ağaç bağlı gösterimde saklanırsa kaç null çocuk referansı bulunur?

   Cevap

   n = 2i + 1'den i = 10, y = i + 1 = 11'dir. null referans sayısı n + 1 = 22'dir. Denetim: her yaprağın iki null referansı vardır, 2 · 11 = 22; iç düğümlerin iki çocuğu da dolu olduğu için başka null yoktur.

4. 0 tabanlı dizi gösteriminde indis 9'daki düğümün ebeveyninin ve çocuklarının indisleri nedir? Aynı düğüm 1 tabanlı dizide hangi indiste durur ve bu indislerin karşılıkları nedir?

   Cevap

   0 tabanlı: ebeveyn ⌊(9 − 1)/2⌋ = 4, sol çocuk 2 · 9 + 1 = 19, sağ çocuk 20. 1 tabanlıda aynı düğüm indis 10'dadır: ebeveyn ⌊10/2⌋ = 5, çocuklar 20 ve 21. Her 1 tabanlı indis, 0 tabanlı karşılığından tam bir fazladır.

5. Kök 10; 10'un çocukları 5 ve 15; 5'in çocukları 2 ve 7; 7'nin yalnız sol çocuğu 6; 15'in yalnız sağ çocuğu 20 olan ağacın kök başta, kök ortada, kök sonda ve seviye sırası çıktıları nedir? Bu ağaç bir ikili arama ağacı mıdır?

   Cevap

   Kök başta: 10 5 2 7 6 15 20. Kök ortada: 2 5 6 7 10 15 20. Kök sonda: 2 6 7 5 20 15 10. Seviye sırası: 10 5 15 2 7 20 6. Kök ortada çıktısı küçükten büyüğe sıralı olduğu için ağaç bir ikili arama ağacıdır.

6. Bir önceki sorudaki ağaçta kokBastaYigin çalıştırılıyor. Her turun sonunda yığında (alttan üste) neler vardır? Yığın en çok kaç öğe tutar?

   Cevap

   Başta [10]. 10 çıkar, 15 ve 5 itilir: [15, 5]. 5 çıkar, 7 ve 2 itilir: [15, 7, 2]. 2 çıkar: [15, 7]. 7 çıkar, 6 itilir: [15, 6]. 6 çıkar: [15]. 15 çıkar, 20 itilir: [20]. 20 çıkar: []. Yığın en çok 3 öğe tutar; çıktı kök başta sırasıdır.

7. ((9 − 3) / (1 + 2)) × 4 ifadesinin ağacında kök hangi işleçtir? Önek ve sonek gösterimleri nedir, hesapla hangi değeri döndürür?

   Cevap

   En son yapılan işlem çarpma olduğu için kök ×'tir; sol alt ağacın kökü /, sağ çocuğu 4'tür. Önek: × / − 9 3 + 1 2 4. Sonek: 9 3 − 1 2 + / 4 ×. hesapla önce 9 − 3 = 6, sonra 1 + 2 = 3, 6 / 3 = 2, en son 2 × 4 = 8 hesaplar ve 8 döndürür.

8. Kök ortada çıktısı 8 4 9 2 5 1 3 7, kök sonda çıktısı 8 9 4 5 2 7 3 1 olan ağaç hangisidir? Kök başta çıktısı nedir?

   Cevap

   Kök sonda çıktısının son öğesi kök: 1. Kök ortada 1'in solu 8 4 9 2 5, sağı 3 7'dir. Sağ alt ağaçta kök sonda sırasının sondan bir önceki öğesi 3 köktür; 7 onun sağındadır. Sol alt ağaçta kök 2'dir; solunda 8 4 9, sağında 5 vardır. 8 4 9'un kökü 4'tür; 8 sol, 9 sağ çocuktur. Ağaç 1(2(4(8, 9), 5), 3(—, 7))'dir. Kök başta: 1 2 4 8 9 5 3 7.

9. Kök başta çıktısı A B, kök sonda çıktısı B A olan kaç farklı ikili ağaç vardır? Hangi ek bilgi ağacı belirler?

   Cevap

   İki ağaç vardır: B, A'nın sol çocuğu ya da sağ çocuğu olabilir; iki ağacın kök başta ve kök sonda çıktıları aynıdır. Kök ortada çıktısı ayrımı yapar: B sol çocuksa B A, sağ çocuksa A B çıkar. Belirsizliğin nedeni A'nın tek çocuklu olmasıdır.

10. yukseklik metodunda taban durum return -1 yerine return 0 yazılmış olsun. 9 kökündeki dört düğümlü ağaçta (9'un çocukları 2 ve 3; 2'nin sol çocuğu 4) metot ne döndürür? Bir yaprak için ne döndürür?

    Cevap

    Yaprak için 1 + max(0, 0) = 1 döner. 2 için 1 + max(1, 0) = 2, 3 için 1, kök için 1 + max(2, 1) = 3 döner. Metot artık yüksekliği düğüm sayısıyla ölçer: her değer kenar tanımındakinden bir fazladır (doğru yanıt 2'dir).

9.11İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Bölüm 8: genel ve ikili ağaç ADT'lerini konum soyutlamasıyla tanımlar, bağlı ve dizi gerçeklemelerini verir; gezinmeleri, Euler turunu ve ifade ağaçlarını bu nottakine yakın bir Java koduyla anlatır.
• D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3. baskı, 1997), Kesim 2.3: ağaç gezinmelerinin klasik incelemesidir; özyinelemesiz gezinme algoritmalarını, iplikli ikili ağaçları ve genel ağaçların ikili ağaçlarla gösterimini ayrıntılı işler.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 10'daki köklü ağaçların gösterimi kesimi ve Ek B.5: ilk çocuk – sonraki kardeş gösterimini ve ağaçlarla ilgili tanım ve sayma sonuçlarını daha biçimsel bir dille verir.

9.12Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
3. D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3. baskı, Addison-Wesley, 1997.
4. Oracle, Java SE 17 API Specification: java.util.Deque, java.util.ArrayDeque, java.util.Queue ve java.util.LinkedList belgeleri.
5. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.

İlgili sayfalar: Bölüm 9 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.