Bölüm 12: Kılavuzlu İkili Ağaçlar

12.1Boş işaretçiler ve kılavuz fikri

Bağlı gösterimde bir ikili ağacın her düğümü üç alandan oluşur: sol alt ağacı gösteren işaretçi, veri ve sağ alt ağacı gösteren işaretçi. C'de bu düğüm kendine başvuran bir yapıyla (self-referential struct) tanımlanır:

typedef struct agac *agac_gost;
struct agac {
    agac_gost solcocuk;   /* sol alt ağaç */
    char      veri;
    agac_gost sagcocuk;   /* sağ alt ağaç */
};

Çocuğu olmayan bir yöndeki işaretçiye NULL yazılır. NULL, hiçbir nesneyi göstermeyen boş işaretçidir (null pointer). Bir yaprağın iki işaretçisi de boştur. Tek çocuklu bir düğümün işaretçilerinden biri boştur. Bu bölümün sorusu basittir: bir ağaçta kaç işaretçi boş kalır ve bu alanlar bir işe yarayabilir mi?

12.1.1n düğümde n + 1 boş işaretçi

Ağacın biçimi ne olursa olsun boş işaretçilerin sayısı yalnız düğüm sayısına bağlıdır. Bunu bir sayma kanıtı gösterir.

Kanıt, ağacın dengeli ya da çarpık olmasına hiç bakmaz. Şekil 12.1 bunu üç örnekle gösterir. Soldaki iki ağaç 4 düğümlüdür ve biçimleri çok farklıdır; ikisinde de 5 işaretçi boştur. Sağdaki 10 düğümlü ağaçta 11 boş işaretçi vardır.

Oran dikkat çekicidir. 2n alanın n + 1'i, yani yarıdan fazlası hiçbir bilgi taşımaz. 64 bitlik bir makinede bir işaretçi 8 bayttır; bir milyon düğümlü bir ağaçta yaklaşık 8 MB bellek boş işaretçilere gider. Bu alanları atmak mümkün değildir, çünkü hangi düğümün hangi yönde çocuğu olacağı önceden bilinmez. Ama bu alanlara anlamlı bir değer yazılabilir.

12.1.2Perlis ve Thornton'un fikri

A. J. Perlis ve C. Thornton 1960'ta boş işaretçilerin ağaçtaki başka düğümleri göstermek için kullanılabileceğini önerdiler. Bu işaretçilere kılavuz (thread) adını verdiler. Kılavuz, düğümün gerçek bir çocuğu değildir; gezinmede hangi düğüme geçileceğini gösteren bir yol işaretidir.

Fikrin değeri gezinmenin ek belleğinde görülür. Bir ikili ağacı kök ortada (inorder) gezmenin iki bilinen yolu vardır. Özyinelemeli yordam her düğüm için bir çağrı açar. Bir yol boyunca açık kalan çağrıların sayısı ağacın yüksekliği h kadardır; çağrı yığını (call stack) bu yüzden O(h) bellek kullanır. Özyinelemesiz (iteratif) yordam ise aynı işi açık bir yığınla yapar: sola inerken geçtiği düğümleri yığına koyar, sonra onlara geri döner. Bu yığın da O(h) yer tutar.

Dengeli bir ağaçta h yaklaşık log₂ n'dir ve bu bedel küçüktür. Ama çarpık ağaçta (skewed tree) bütün düğümler tek bir yöne dizilir ve h = n olur. Bir milyon düğümlü sola çarpık bir ağaçta özyinelemeli gezinme bir milyon çağrıyı aynı anda açık tutar. Varsayılan çağrı yığını çoğu sistemde bu kadar derinliği kaldırmaz ve program çöker.

Kılavuzlu ağaçta durum farklıdır. Her düğümden kök ortada sırada sonraki düğüme, yani ardıla, ya doğrudan bir kılavuzla ya da birkaç gerçek bağ izlenerek gidilir. Nereye dönüleceği ağacın içinde yazılı olduğu için hiçbir şeyi hatırlamak gerekmez. Gezinme tek bir işaretçi değişkeniyle yapılır ve ek bellek O(1) olur. Bunun bedeli de vardır: her işaretçi alanı için onun gerçek çocuk mu yoksa kılavuz mu olduğunu söyleyen birer bitlik bilgi tutmak gerekir.

12.2Kılavuzları kurmak

Bir boş işaretçinin hangi düğümü göstereceği keyfî değildir. Kural, kök ortada gezinme sırasına göre konur. Bu yüzden önce o sıradaki “önceki” ve “sonraki” düğüm kavramları kesinleştirilmelidir.

12.2.1Kök ortada öncül ve ardıl

Kök ortada gezinme bir düğümde önce sol alt ağacı, sonra düğümün kendisini, en son sağ alt ağacı ziyaret eder. Ana örnek ağaçta bu sıra H D I B E A F C G'dir. Bu dizide her düğümün bir solundaki ve bir sağındaki komşusu bellidir.

Örnek sırada E'nin öncülü B, ardılı A'dır. H ilk düğüm olduğu için öncülsüzdür; G son düğüm olduğu için ardılsızdır. Kılavuzların kuralı bu iki kavramla yazılır.

Şekil 12.2 kuralların ana örneğe uygulanmış hâlidir. Düz mavi çizgiler gerçek çocuk bağlarıdır. Kesikli kırmızı oklar kılavuzlardır. Kılavuzlar ağacın kök ortada sırasını ağacın içine örer: her yapraktan sağa çıkan kırmızı ok, sırada bir sonraki düğüme gider.

Kılavuzların bir ortak özelliği vardır: hepsi ağaçta yukarı doğru bir düğümü gösterir. Bunun nedeni şudur. Sol alt ağacı olmayan bir düğümün öncülü, düğümün içinde bulunduğu sağ alt ağacın sahibi olan en yakın atadır. Sağ alt ağacı olmayan bir düğümün ardılı da düğümün içinde bulunduğu sol alt ağacın sahibi olan en yakın atadır. Örneğin I, B'nin sol alt ağacındadır ve I'nın sağ alt ağacı yoktur; I'nın ardılı B'dir. Aşağı doğru yolculuk gerçek bağlarla yapılır, yukarı doğru dönüşler kılavuzlarla. Yığının hatırlamak zorunda olduğu bilgi tam da bu dönüş yollarıdır.

12.2.2Kılavuzları tek tek kurmak

Kılavuzlar elle kurulurken önce kök ortada sıra yazılır. Sonra her boş işaretçi için o sırada düğümün bir solundaki ya da bir sağındaki düğüm okunur. Ana örnekte on boş alan vardır (Örnek 12.1). Tablo 12.2 her birinin nereyi göstereceğini verir.

Tablodaki her satır, sıradaki bir komşuluğa karşılık gelir. Kök ortada sırada sekiz komşu çift vardır (H–D, D–I, …, C–G). Bu çiftlerin bazıları gerçek bağlarla zaten birbirine bağlıdır; D ile H gibi. Geri kalan her komşuluk bir kılavuzla kurulur. Şekil 12.3 kurmanın başını ve sonunu gösterir. Üstte sıradan ağaç ve on boş işaretçisi, altta on kılavuzun hepsi yerindedir. Alttaki şeklin altına kök ortada sıra da yazılmıştır; her kırmızı okun bu sırada bir komşuyu gösterdiği oradan okunabilir.

12.2.3Kılavuz bayrakları

Kâğıt üzerinde kılavuzlar kırmızı, gerçek bağlar siyah çizilir. Derleyici için ise iki işaretçi arasında hiçbir fark yoktur: ikisi de bir düğümün adresidir. Bir gezinme yordamı p->solCocuk'u izlediğinde gerçek bir sol çocuğa mı inecek, yoksa yukarıdaki bir öncüle mi dönecek, bunu adresin kendisinden anlayamaz. Bu yüzden her işaretçinin yanında onun türünü söyleyen bir bilgi saklanır. Her düğüme iki ek alan eklenir:

typedef struct kilavuz_agac *kilavuz_gost;
struct kilavuz_agac {
    short int    solKilavuz; /* TRUE: solCocuk kılavuz */
    kilavuz_gost solCocuk;
    char         veri;
    kilavuz_gost sagCocuk;
    short int    sagKilavuz; /* TRUE: sagCocuk kılavuz */
};

Yapı, sıradan ikili ağaç düğümüne iki alan ekler. solKilavuz doğru (TRUE) ise solCocuk bir kılavuzdur, yani öncül gösterir; yanlış (FALSE) ise gerçek bir sol çocuğu gösterir. sagKilavuz aynı bilgiyi sağ işaretçi için taşır. TRUE ve FALSE sabitleri bir sayım tipiyle tanımlanır:

enum { FALSE, TRUE };      /* FALSE = 0, TRUE = 1 */

Sayım tipinde ilk ada 0, ikinciye 1 verilir. Böylece FALSE 0, TRUE 1 olur ve if (p->solKilavuz) gibi koşullar doğrudan çalışır. İlk satırdaki typedef, struct kilavuz_agac * tipine kilavuz_gost kısa adını verir. Bu satır yapının tanımından önce gelir; yapının alanları kendi tipinden işaretçi tuttuğu için önce adın bilinmesi gerekir. Yapı tanımı kapanış parantezinden sonra noktalı virgülle biter (8. satır). Bu noktalı virgül unutulursa derleyici hatayı çoğu zaman bir sonraki satırda bildirir ve hatanın yeri karışır.

Bayraklar belleği artırmaz mı? Artırır, ama zaman açısından kazanç çok daha büyüktür. Ders anlatımında bu karar açıkça söylenir: zaman karmaşıklığı alan karmaşıklığından daha önemlidir ve iki bayrak gerçekte iki bitle tutulabilir. Ne kadar yer harcandığını ölçmek öğreticidir. Yapının boyutu yalnız alanların toplamı değildir. Derleyici her alanı kendi hizalama sınırına yerleştirir ve araya dolgu baytları (padding) koyar. Tablo 12.3 x86-64 üzerinde sizeof ve offsetof ile ölçülen değerleri verir.

40 baytın 19'u dolgudur. İşaretçiler 8'in katı olan adreslere yerleşmek zorundadır; araya giren küçük alanlar her seferinde 8 baytlık bir yuvayı tek başına kaplar. Alanlar büyükten küçüğe sıralanırsa (önce iki işaretçi, sonra iki short, en son char) aynı yapı 24 bayta iner. Bayraksız sıradan düğüm de 24 bayttır. Yani alan sırası iyi seçilirse bu makinede bayraklar hiç ek bellek getirmez; iki işaretçinin arkasında zaten boş kalan dolgu baytlarına yerleşirler. Bayraklar bit alanı (unsigned solKilavuz : 1) olarak tanımlansa da sonuç değişmez. Sunumdaki alan sırası, düğümün kâğıttaki çizimini izler: sol bayrak, sol işaretçi, veri, sağ işaretçi, sağ bayrak. Bu sıra okumayı kolaylaştırır ama bellekte en savurgan yerleşimdir.

12.2.4Başlık düğümü

Tablo 12.2'de iki kılavuz havada kalmıştı. H'nin sol işaretçisi öncül göstermeli, ama H sıradaki ilk düğümdür. G'nin sağ işaretçisi ardıl göstermeli, ama G son düğümdür. Bu iki alana NULL yazmak, “hiçbir işaretçi boş değildir” düzenini bozar ve gezinme yordamlarına özel durum ekler. Çözüm, bağlı listelerden bilinen başlık düğümüdür.

Boş ağaçta yalnız başlık vardır. Bu durumda başlığın sol işaretçisi de kendisini gösterir ve solKilavuz TRUE'dur: gösterilen şey gerçek bir kök değil, bir kılavuzdur. Ağaca ilk düğüm eklendiğinde sol işaretçi bu düğüme çevrilir ve solKilavuz FALSE yapılır.

Bu düzen bir C yordamıyla kurulur. Sunumda yer almayan iki küçük yardımcı yazılır. kilavuz_dugum, yeni bir düğüm için bellek ayırır. bos_kilavuzlu_agac ise başlığı Tablo 12.4'teki gibi doldurur:

kilavuz_gost kilavuz_dugum(char veri) {
  kilavuz_gost d = malloc(sizeof *d);
  if (d == NULL) {               // bellek kalmadı
    fprintf(stderr, "bellek yok\n");
    exit(EXIT_FAILURE);
  }
  d->veri = veri;
  d->solCocuk = d->sagCocuk = NULL;   // ekleme yordamı dolduracak
  d->solKilavuz = d->sagKilavuz = TRUE;
  return d;
}
kilavuz_gost bos_kilavuzlu_agac(void) {
  kilavuz_gost L = kilavuz_dugum('-');  // başlık: verisi kullanılmaz
  L->solCocuk = L;  L->solKilavuz = TRUE;   // ağaç boş
  L->sagCocuk = L;  L->sagKilavuz = FALSE;  // sağı hep kendisi
  return L;
}

malloc, istenen kadar bellek bulamazsa NULL döndürür. Dönen değer denetlenmeden d->veri'ye yazmak, boş işaretçi üzerinden yazmak demektir ve tanımsız davranıştır. Yordam bu yüzden NULL gelince bir ileti basıp programı bitirir. sizeof *d ifadesi, d'nin gösterdiği tipin boyutunu verir. Tip adı tekrar yazılmadığı için yapı değişse bile ifade doğru kalır. Yeni düğümün işaretçileri NULL yapılır; düğüm ağaca eklenirken saga_ekle ya da sola_ekle bu değerlerin üzerine yazar. Bayrakların ilk değeri de aynı nedenle önemsizdir. bos_kilavuzlu_agac'ta başlığın verisine '-' yazılır; bu değer hiçbir yerde okunmaz.

Şekil 12.4'ün üst yarısı boş ağacı, alt yarısı ana örneği başlıkla birlikte gösterir. Şekildeki T ve F harfleri her düğümün iki yanındaki kılavuz bayraklarıdır. Başlığın solu köke (A) gider ve sol bayrağı F'dir. H'nin sol ve G'nin sağ kılavuzu artık başlığa bağlıdır. Başlığın sağ işaretçisi kendi üstüne kıvrılır.

Başlıkla birlikte ağaç bir halka gibi kapanır. Kök ortada sırada son düğümden sonra başlığa, başlıktan sonra yeniden ilk düğüme gelinir. Gezinme yordamları bu halkayı kullanır: başlıktan başlar, başlığa dönünce durur. Böylece “ağaç boş mu”, “ilk düğüm hangisi”, “son düğümün ardılı yok” gibi özel durumların hiçbiri ayrı bir if gerektirmez.

12.2.5Neden kök ortada sıra

Kılavuzlar kök ortada sıraya göre kurulur. Aynı ağacın üç gezinme sırası Tablo 12.5'te yan yanadır.

Kök ortada sıranın ayrıcalığı kılavuzların tutarlılığından gelir. Bu sırada sol alt ağacı olmayan bir düğümün öncülü her zaman bir atasıdır; sağ alt ağacı olmayan bir düğümün ardılı da öyle. Yani boş bir sol alan tam da öncülünü, boş bir sağ alan tam da ardılını göstermeye uygundur. Dolu alanlar ise aşağıya iner ve öncül ya da ardıl, o alt ağacın en sağında ya da en solunda bulunur. İki kural birlikte her düğüm için ardılı ve öncülü kısa bir yoldan bulmayı sağlar. Kök önde sırada bu simetri yoktur. Örneğin D'nin kök önde ardılı H'dir ve D'den H'ye zaten gerçek bir sol bağ gider; bir kılavuzun eklediği bir bilgi kalmaz. Ders anlatımında bu yüzden ağacın kök ortada gezinmeye göre kurulduğu vurgulanır. Kök önde ve kök sonda gezinme de aynı kılavuzlarla yapılabilir, ama daha dolambaçlı bir yoldan.

12.3Kök ortada gezinme

Kılavuzlu ağacın bütün gezinme yordamları tek bir soruya dayanır: verilen bir düğümün kök ortada ardılı hangisidir? Bu soru hızlıca yanıtlanabilirse gezinme, başlıktan başlayıp ardıldan ardıla geçmekten ibarettir.

12.3.1Ardılı bulmak

Bir p düğümünün ardılı için iki durum vardır.

• p->sagKilavuz == TRUE ise p->sagCocuk bir kılavuzdur. Kılavuzun tanımı gereği bu işaretçi zaten p'nin ardılını gösterir. Arama gerekmez.
• p->sagKilavuz == FALSE ise p'nin gerçek bir sağ alt ağacı vardır. Kök ortada gezinme p'yi yazdıktan sonra bu alt ağaca girer ve orada ilk olarak en soldaki düğümü yazar. Ardıl, sağ alt ağacın en soldaki düğümüdür. Ona varmak için sağ çocuktan başlanır ve solKilavuz TRUE olana dek sol bağlar izlenir.

Bu iki kural sunumdaki yordamda birkaç satıra sığar:

kilavuz_gost kokortada_ardil_bul(kilavuz_gost L) {
  // L ile işaret edilen (NULL olmayan) öğenin ardılı
  kilavuz_gost p = L->sagCocuk;
  if (!L->sagKilavuz)        // sağ alt ağaç var mı
    while (!p->solKilavuz)   // en soluna dek in
      p = p->solCocuk;
  return p;
}

Yordam satır satır şöyle çalışır.

• Satır 1–2. Yordam bir düğüm işaretçisi alır ve ardılın adresini döndürür. Açıklama satırı ön koşulu söyler: L NULL olmamalıdır. Kılavuzlu ağaçta hiçbir işaretçi NULL olmadığı için yordamın içinde böyle bir denetim gerekmez; ön koşulu sağlamak çağıranın işidir.
• Satır 3. p, L'nin sağ işaretçisini alır. Bu değer hem kılavuz durumunda doğrudan sonuçtur hem de sağ alt ağaç durumunda aramanın başlangıcıdır. İki durumun ortak ilk adımı tek atamada birleşir.
• Satır 4. !L->sagKilavuz doğruysa sağ işaretçi gerçek bir bağdır, yani sağ alt ağaç vardır. Açıklama satırı bayrağı değil, sorunun anlamını yazar: “sağ alt ağaç var mı”.
• Satır 5–6. Sağ alt ağaçta sola inilir. Döngü koşulu p->solKilavuz'a bakar, p->solCocuk'a değil. En soldaki düğümün sol işaretçisi de dolu bir alandır (bir kılavuz), ama bayrağı TRUE'dur.
• Satır 7. İki durumda da p ardılı gösterir ve döndürülür.

Kuralların doğruluğu kök ortada gezinmenin tanımından çıkar.

12.3.2Kod izleme: başlık, A ve I

Yordam üç farklı düğümle çağrılsın. Tablo 12.6 her çağrıda p'nin aldığı değerleri ve karar veren bayrakları sırayla verir. Satır numaraları yukarıdaki koda aittir.

İlk çağrı özel bir sonuç verir: başlığın ardılı kök ortada sıradaki ilk düğümdür (H). Başlığın sağ işaretçisinin kendini göstermesi ve sagKilavuz'unun FALSE olması bunun için seçilmiştir. Yordam, başlığın sağ alt ağacının “kendisi” olduğunu düşünür, oradan sola inmeye başlar ve başlığın solundaki gerçek ağacın en soluna varır. Böylece gezinmeye başlamak için ayrı bir “en soldaki düğümü bul” yordamı gerekmez. Şekil 12.5 bu çağrının ilk ve son anını gösterir.

A için yapılan çağrıda sağ alt ağaç C'de başlar ve tek bir sola inişle F bulunur. I için yapılan çağrıda hiç arama yoktur; sağ işaretçi bir kılavuzdur ve doğrudan B'yi gösterir. Bir yaprağın ardılı her zaman böyle tek adımda bulunur.

12.3.3Yığınsız gezinme

Ardıl yordamı hazır olunca kök ortada gezinme kısa bir döngüdür. Başlıktan başlanır; her turda bir sonraki düğüme geçilir ve yazılır. Başlığa geri dönülünce bütün ağaç gezilmiş olur.

void kilavuz_kokortada_dolas(kilavuz_gost L) {
  kilavuz_gost p = L;        // L: başlık düğümü
  for (;;) {
    p = kokortada_ardil_bul(p);
    if (p == L) break;       // başlığa dönüldü mü
    printf("%c ", p->veri);
  }
}

• Satır 2. p başlığı gösterir. Gezinmenin bütün durumu bu tek değişkendedir.
• Satır 3. for (;;) koşulsuz bir döngüdür; çıkış, gövdedeki break ile yapılır. Çıkış testi ardıl bulunduktan sonra yapılmak zorunda olduğu için koşul döngünün başına konamaz.
• Satır 4. p kendi ardılına ilerler.
• Satır 5. Ardıl başlıksa halka tamamlanmıştır. Son düğümün sağ kılavuzu başlığı gösterdiği için bu durum her zaman gerçekleşir.
• Satır 6. Düğüm yazılır.

Boş ağaçta ilk çağrı başlığın kendisini döndürür. p = başlık->sagCocuk başlıktır. sagKilavuz FALSE olduğu için döngüye girilir, ama başlığın solKilavuz'u TRUE'dur ve hemen çıkılır. p == L doğrudur ve hiçbir şey yazılmadan gezinme biter. Boş ağaç için ayrı bir denetim gerekmemesi başlık düğümünün kazancıdır.

Ana örnekte döngü on kez döner. Tablo 12.7, her turda ardılın hangi kuralla bulunduğunu ve kaç işaretçi izlendiğini verir. “İzlenen” sütunu, satır 3'teki okuma ile döngüdeki her sola inişi birer adım sayar.

Tablodaki iki kural sırayla birbirini izler. Bir yapraktan sonra kılavuzla yukarı çıkılır; iç düğümden sonra sağ alt ağaca girilip en sola inilir. Hiçbir turda bir düğüm iki kez yazılmaz ve hiçbir yerde bir yığına ihtiyaç duyulmaz.

12.3.4Gezinmenin maliyeti

Tek bir kokortada_ardil_bul çağrısı uzun sürebilir. Başlıkla yapılan ilk çağrı kökten en soldaki düğüme kadar iner; bu yol ağacın yüksekliği kadar uzundur. Tek çağrının en kötü maliyeti bu yüzden O(h)'dir. Sola çarpık 1000 düğümlü bir ağaçta bu ilk çağrı 1001 işaretçi izler. Ama bütün gezinmenin toplam maliyeti, çağrı sayısı ile en kötü maliyetin çarpımından çok daha küçüktür.

Ana örnekte sol çocuğu olan düğümler A, B, C ve D'dir. Başlıktan köke giden bağla birlikte beş sola iniş yapılır. Toplam 10 + 5 = 15 adım, Tablo 12.7'nin son sütununun toplamıyla aynıdır. Uç durumlar da sayılarak doğrulandı. Sola çarpık 1000 düğümlü ağaçta her düğümün sol çocuğu vardır ve sınır tam olarak erişilir: 2001 adım. Sağa çarpık 1000 düğümlü ağaçta yalnız başlıktan köke bir sola iniş yapılır: 1001 + 1 = 1002 adım.

Toplam 2n + 1 adım n + 1 çağrıya bölününce çağrı başına ikiden az adım düşer. Tek tek bakıldığında pahalı çağrılar olsa da bir gezinmede bunlar azdır; pahalı bir iniş, sonraki çağrıları ucuzlatır. Bu tür değerlendirmeye amortize analiz (amortized analysis) denir. Ardıl bulmanın amortize maliyeti gezinme içinde O(1)'dir.

Kılavuzların bir kazancı daha vardır. Herhangi bir düğümün adresi elde olduğunda ardılına, gezinmeye baştan başlamadan geçilebilir. Sıradan ağaçta bir düğümün ardılını bulmak için ya ebeveyn işaretçisi gerekir ya da kökten yeniden inmek gerekir. Kılavuzlu ağaç bu soruyu düğümün kendisinden başlayarak yanıtlar.

Böyle bir iyileştirmenin değeri küçümsenmemelidir. Ders anlatımında bir örnek verilir: bir problemin O(n²) sürede çözüldüğü bilinir ve birisi çalışıp O(n^1,89)'a indiren bir algoritma yazar. Üsteki bu küçük fark büyük bir iştir ve literatüre o algoritma geçer. Kılavuzlu gezinme zamanı değil belleği iyileştirir: O(h)'yi O(1)'e indirir. Çarpık ağaçlarda bu, O(n)'den O(1)'e inmek demektir.

12.3.5Kök önde gezinme

Kılavuzlar kök ortada sıraya göre kurulmuştur, ama aynı kılavuzlarla kök önde (preorder) gezinme de yapılabilir. Bunun için kök önde ardılı bulan bir yordam yazılır.

kilavuz_gost kokonde_ardil_bul(kilavuz_gost p) {
  if (!p->solKilavuz)        // sol çocuk varsa o
    return p->solCocuk;
  while (p->sagKilavuz)      // sağ kılavuzlarla çık
    p = p->sagCocuk;
  return p->sagCocuk;        // ilk gerçek sağ çocuk
}

Kök önde gezinmede bir düğüm yazıldıktan sonra varsa sol alt ağacına girilir; sol alt ağacın ilk düğümü onun köküdür. Satır 2–3 bu durumu karşılar: sol bayrak FALSE ise ardıl sol çocuktur. Sol çocuk yoksa ardıl, p'den başlayarak yukarıda bulunan ve henüz gezilmemiş ilk sağ alt ağacın köküdür. Satır 4–5 bu düğümü arar. p'nin sağ işaretçisi kılavuz olduğu sürece kılavuz izlenir. Sağ kılavuz, kök ortada ardıla, yani p'yi sol alt ağacında taşıyan en yakın ataya gider. O atanın sol alt ağacı bitmiştir ve sırada atanın sağ alt ağacı vardır. Ata da sağ alt ağaçsızsa (bayrağı yine TRUE) bir kılavuz daha izlenir. Gerçek bir sağ bağa sahip ilk düğümde durulur ve satır 6 onun sağ çocuğunu döndürür.

Bu yordamla gezinme döngüsü, kök ortada gezinmeyle aynı biçimdedir:

void kilavuz_kokonde_dolas(kilavuz_gost L) {
  kilavuz_gost p = L;        // L: başlık düğümü
  for (;;) {
    p = kokonde_ardil_bul(p);
    if (p == L) break;       // başlığa dönüldü mü
    printf("%c ", p->veri);
  }
}

Başlıktan başlanınca başlığın sol bayrağı FALSE olduğu için ardıl köktür (A). Son düğümden sonra kılavuzlar başlığa çıkar; başlığın sağ bayrağı FALSE, sağ işaretçisi kendisidir. Yordam başlığı döndürür ve gezinme biter. Tablo 12.8 bütün adımları verir.

Bir yaprağın kök önde ardılını bulmak birden çok kılavuz izlemeyi gerektirebilir. Örneğin I'dan sonra tek kılavuzla B'ye çıkılır ve B'nin sağ çocuğu E bulunur. Daha derin bir ağaçta bir yapraktan başlayarak birkaç ata üst üste sağ alt ağaçsız olabilir; bu durumda kılavuz zinciri uzar. Yine de her sağ kılavuz bütün gezinmede en çok bir kez izlenir ve toplam zaman O(n), ek bellek O(1) kalır.

Kök sonda (postorder) gezinme aynı kolaylıkla yazılamaz. Kök sonda sırada bir düğümden sonra genellikle ebeveyni gelir. Düğüm ebeveyninin sağ çocuğuysa ardılı ebeveyndir; sol çocuğuysa ardılı ebeveynin sağ alt ağacındaki ilk kök sonda düğümdür. İki durumda da ebeveyni bilmek gerekir. Kılavuzlar ise ebeveyni değil, kök ortada öncül ve ardılı gösterir; bu ikisi ebeveynle her zaman örtüşmez. H'nin sağ kılavuzu ebeveyni D'yi gösterir, ama I'nın sağ kılavuzu ebeveyni D'yi değil, B'yi gösterir. Kök sonda gezinmeyi kılavuzlarla yapmak mümkündür ama dolambaçlıdır. Her düğüme bir ebeveyn işaretçisi eklemek işi kolaylaştırır.

12.3.6Morris gezinmesi

Kılavuzlu ağaç iki bedel öder: her düğümde bayrak alanları ve ekleme yordamlarının ek karmaşıklığı. J. M. Morris 1979'da bayrak alanı gerektirmeyen bir yöntem önerdi. Morris gezinmesi (Morris traversal), sıradan bir ikili ağaçta kılavuzları gezinme sırasında geçici olarak kurar, işi bitince söker. Ağaç, gezinmenin sonunda başlangıçtaki hâline döner. Yordam, bölümün başında verilen sıradan struct agac düğümüyle çalışır:

void morris_kokortada(agac_gost L) {
  while (L) {
    if (!L->solcocuk) {             /* sol yok: yaz, sağa */
      printf("%c", L->veri);  L = L->sagcocuk;
    } else {
      agac_gost p = L->solcocuk;    /* kök ortada öncülü */
      while (p->sagcocuk && p->sagcocuk != L)
        p = p->sagcocuk;
      if (!p->sagcocuk) {           /* geçici kılavuz kur */
        p->sagcocuk = L;  L = L->solcocuk;
      } else {                      /* kılavuzu sök */
        p->sagcocuk = NULL;
        printf("%c", L->veri);  L = L->sagcocuk;
      }
    }
  }
}

Yordamın fikri şudur. Sol alt ağacı olan bir L düğümüne gelindiğinde, sola inmeden önce dönüş yolu hazırlanır. L'nin kök ortada öncülü, sol alt ağacının en sağındaki düğümdür. Bu düğümün sağ işaretçisi boştur, çünkü en sağdaki düğümün sağ çocuğu olamaz. Bu boş alana L'nin adresi yazılır: geçici bir kılavuz. Sol alt ağaç gezilip öncüle varıldığında bu kılavuz izlenerek L'ye dönülür. L'ye ikinci gelişte öncül yeniden aranır; bu kez öncülün sağ işaretçisinin L'yi gösterdiği görülür. Bu, sol alt ağacın bittiğinin işaretidir. Kılavuz sökülür, L yazılır ve sağa geçilir.

• Satır 2. L NULL olana dek döner. Son düğümün sağ işaretçisi gerçekten NULL'dır; döngü orada biter.
• Satır 3–4. Sol alt ağaç yoksa düğüm yazılır ve sağa geçilir. Sağ işaretçi gerçek bir çocuk da olabilir, daha önce kurulmuş geçici bir kılavuz da. Yordam ikisini ayırt etmez; ikisinde de doğru düğüme gidilir.
• Satır 6–8. Öncül aranır: sol çocuktan başlanır, sağa gidilebildiği sürece gidilir. Koşulun ikinci yarısı (p->sagcocuk != L) önemlidir. Kılavuz daha önce kurulmuşsa en sağdaki düğümün sağ işaretçisi L'yi gösterir; bu sınama olmasaydı arama kılavuzu izleyip L'ye, oradan yeniden sola dönerdi.
• Satır 9–10. Öncülün sağı boşsa ilk geliştir: kılavuz kurulur ve sola inilir.
• Satır 11–13. Öncülün sağı L'yi gösteriyorsa ikinci geliştir: kılavuz sökülür, L yazılır, sağa geçilir.

Yordam A(B(D, E), C) ağacında, yani A'nın çocukları B ve C, B'nin çocukları D ve E olan beş düğümlü ağaçta izlensin. Tablo 12.9 her turu, Şekil 12.6 dört anı gösterir.

Tablo, her geçici kılavuzun tam iki kez görüldüğünü gösterir: kurulurken ve sökülürken. Sol çocuğu olan her düğüm bir kılavuz doğurur; bu ağaçta iki tane (A ve B için). Gezinme bittiğinde D'nin ve E'nin sağ işaretçileri yeniden NULL'dır. Sonuç, aynı ağaçta özyinelemeli kök ortada gezinmenin çıktısıyla karşılaştırılarak doğrulandı:

void kokortada(agac_gost p) {
  if (p) {
    kokortada(p->solcocuk);
    printf("%c", p->veri);
    kokortada(p->sagcocuk);
  }
}

Morris gezinmesinin zamanı da O(n)'dir. Sol çocuğu olan her düğüm için öncül iki kez aranır. Her arama, sol çocuktan başlayıp sağa giden bir yolu yürür. Farklı düğümlerin bu yolları ortak kenar içermez; bir kenar en çok bir düğümün öncül yolunda bulunur. Yolların toplam uzunluğu bu yüzden en çok n − 1'dir ve iki kez yürünmeleri toplamı 2(n − 1) ile sınırlar. Buna her düğümde yapılan sabit iş eklenir. Ölçüm bunu doğrular: beş düğümlü örnekte toplam 13, yedi düğümlü tam ağaçta 18 işaretçi hareketi yapılır.

Yöntemin bir sınırı vardır. Gezinme sürerken ağaç geçici olarak değişir: bazı NULL alanlar başka düğümleri gösterir. Bu sırada başka bir iş parçacığı ağacı okursa döngülerle karşılaşır ve yanlış sonuç alır. Gezinme bir hata ya da erken çıkışla yarıda kesilirse ağaç bozuk kalır. Morris gezinmesi bu yüzden ağaca tek başına erişen ve gezinmeyi sonuna dek götüren yordamlar için uygundur.

12.4Düğüm ekleme

Kılavuzlu ağaçta gezinme kolaydır; bedeli eklemede ödenir. İkili arama ağacına düğüm eklemek tek bir işaretçi atamasıdır: yeni düğüm, boş bir çocuk alanına yazılır. Kılavuzlu ağaçta ise boş alan yoktur. Yeni düğüm eklendiğinde hem onun kendi kılavuzları doğru yerleri göstermeli hem de çevresindeki kılavuzlar yeni sıraya uymalıdır. Ekleme bu yüzden tek başına kolay bir yordam değildir; biraz girifttir.

12.4.1Ekleme neden girift

Yeni bir düğüm bir ebeveynin ya sağına ya da soluna eklenir. Sol ve sağ eklemenin işaretçi atamaları birbirinin aynası olsa da birebir aynı değildir; bu yüzden iki ayrı yordam yazılır: saga_ekle ve sola_ekle. Önce saga_ekle ele alınır. Sağa eklemede iki durum vardır:

1. Ebeveynin sağ alt ağacı yoktur. Yeni düğüm bir yaprak olarak ebeveynin sağına yerleşir.
2. Ebeveynin sağ alt ağacı vardır. Yeni düğüm ebeveyn ile bu alt ağacın arasına girer; eski alt ağaç yeni düğümün sağ alt ağacı olur.

İkinci durum sıradan ikili arama ağacına eklemede hiç ortaya çıkmaz; orada yeni düğüm hep bir yaprak olur. Kılavuzlu ağaçta ise iki durum da işe yarar: ikincisi, bir düğümü ağacın ortasına sokmanın yoludur.

12.4.2Durum 1: sağ alt ağacı olmayan ebeveyne ekleme

Ağaç A(–, B(C, –)) olsun: başlığın solunda A; A'nın sol çocuğu yok, sağ çocuğu B; B'nin sol çocuğu C, sağ çocuğu yok. Kök ortada sıra A C B'dir. Yeni düğüm D, B'nin sağına eklenecektir. B'nin sağ işaretçisi bir kılavuzdur ve B sıranın son düğümü olduğu için başlığı gösterir. Ekleme altı atamayla yapılır:

cocuk->sagCocuk  = baba->sagCocuk;
cocuk->sagKilavuz = TRUE;  // ebeveynin sağı yoktu
cocuk->solCocuk  = baba;
cocuk->solKilavuz = TRUE;
baba->sagCocuk   = cocuk;
baba->sagKilavuz = FALSE;  // TRUE idi

Her atamanın gerekçesi kök ortada sıradan okunur. Ekleme sonrası sıra A C B D olacaktır. D, B'den hemen sonra gelir; D'nin öncülü B, ardılı B'nin eski ardılıdır. Tablo 12.10 atamaları sırayla izler, Şekil 12.7 ilk ve son durumu gösterir.

Atamaların sırası rastgele değildir. 1. satır ebeveynin sağ işaretçisini okur, 5. satır onun üzerine yazar. Bu iki satırın yeri değişirse cocuk->sagCocuk'a ebeveynin eski ardılı yerine çocuğun kendi adresi yazılır ve ardıl bilgisi kaybolur. Genel kural şudur: bir alanın eski değeri gerekiyorsa önce o değer kullanılır, sonra alan değiştirilir. Atamaların hepsi sabit sürelidir; Durum 1'in maliyeti O(1)'dir.

12.4.3Durum 2: ebeveynin sağ alt ağacı var

Şimdi ağaç A(–, B(C, D(E, F))) olsun. B'nin sağ çocuğu D, D'nin çocukları E ve F'dir. Kök ortada sıra A C B E D F'dir. Yeni düğüm X, B'nin sağ çocuğu yapılacaktır. İstenen şudur: D alt ağacı kaybolmamalı ve X'in sağ alt ağacı olmalıdır. Kırmızı işaretçiler de yine doğru yerleri göstermelidir. Ekleme sonrası sıra A C B X E D F olacaktır.

Bu sıradan iki gereksinim okunur. X'in öncülü B'dir; bu Durum 1'deki gibidir. Ama X'ten sonra gelen düğüm E'dir, yani D alt ağacının en soldaki düğümü. E'nin sol kılavuzu eskiden B'yi gösteriyordu, çünkü E'nin eski öncülü B idi. Ekleme sonrası E'nin öncülü X olur. Öyleyse çocuk, ebeveynin eski ardılının öncülü yapılmalıdır.

Durum 1'in altı ataması bu ağaca olduğu gibi uygulanırsa ne olur? Deneme sonucu şudur: gezinme A C B X D F yazar; E kaybolur. Nedeni 2. satırdır. cocuk->sagKilavuz = TRUE, X'in sağ işaretçisini (D'yi gösteriyor) bir kılavuz sayar. Gezinme X'ten sonra kılavuz kuralıyla doğrudan D'ye atlar ve D'nin sol alt ağacına hiç inmez. E'nin sol kılavuzu da hâlâ B'yi gösterir. Ağaç bozulmuştur ve hiçbir derleyici uyarısı bunu haber vermez.

Düzeltme iki parçalıdır:

• 2. satır cocuk->sagKilavuz = baba->sagKilavuz olarak yazılır. Durum 1'de ebeveynin bayrağı TRUE'dur ve çocuğa kırmızılık geçer; Durum 2'de FALSE'tur ve siyahlık korunur. Ebeveynin alt ağacı artık çocuğun alt ağacıdır.
• Durum 2'de ebeveynin eski ardılının, yani yeni düzende çocuğun ardılının, sol kılavuzu çocuğa çevrilir.

Bu iki değişiklikle her iki durumun da üstesinden gelen tek bir yordam yazılabilir.

12.4.4Tek yordam: saga_ekle

void saga_ekle(kilavuz_gost baba,
               kilavuz_gost cocuk) {
  // cocuk'u baba'nın sağ çocuğu yapar (kılavuzlu)
  kilavuz_gost p;
  cocuk->sagCocuk   = baba->sagCocuk;
  cocuk->sagKilavuz = baba->sagKilavuz;
  cocuk->solCocuk   = baba;
  cocuk->solKilavuz = TRUE;
  baba->sagCocuk    = cocuk;
  baba->sagKilavuz  = FALSE;
  if (!cocuk->sagKilavuz) { // ebeveynin alt ağacı var mı
    p = kokortada_ardil_bul(cocuk);
    p->solCocuk = cocuk;     // ardılın öncülü çocuk
  }
}

Yordam satır satır şöyle okunur. Satır numaraları yukarıdaki koda aittir.

• Satır 1–2, açık tanım. Yordamın adı ne yaptığını söyler; giden parametreler (baba, cocuk) bellidir; dönüş değeri yoktur (void). Açık tanımlı bir yordam, gövdesi okunmadan kullanılabilir.
• Satır 5–6. Çocuğun sağ işaretçisi ve sağ bayrağı ebeveynden alınır. Durum 1'de kırmızılık (TRUE), Durum 2'de siyahlık (FALSE) korunur. Ortak iş, ortak biçimde yazılmıştır.
• Satır 7–8. Çocuğun öncülü ebeveyndir: sol işaretçi ebeveyne gider, sol bayrak TRUE olur.
• Satır 9. Ebeveynden çocuğa gerçek bağ.
• Satır 10. Ebeveynin sağ bayrağı FALSE yapılır. Durum 2'de bayrak zaten FALSE'tur ve bu atama gereksiz ama zararsızdır; Durum 1'de gereklidir. Bir if ile ayırmak yerine iki durumda da yazmak kodu sadeleştirir.
• Satır 11–13. Çocuğun sağ bayrağı FALSE ise çocuğun gerçek bir sağ alt ağacı vardır; bu Durum 2'dir. Çocuğun ardılı bulunur ve onun sol kılavuzu çocuğa çevrilir. Durum 1'de yalnız bir sınama yapılır ve yordamdan çıkılır.

11. satırdaki koşul bayrağı sınar ama sorduğu soru şudur: ebeveynin sağ alt ağacı var mıydı? 5–6. satırlardan sonra ebeveynin eski sağ bilgisi çocuğa taşınmış olduğu için bu soru çocuğun bayrağına bakılarak yanıtlanır. Açıklama satırı da bayrağı değil, bu soruyu yazar.

Tablo 12.11, saga_ekle(B, X) çağrısını Durum 2 ağacında satır satır izler.

10. satırdan sonra ağaç neredeyse doğrudur; X yerindedir ve gezinme bile A C B X E D F yazar, çünkü gezinme sol kılavuzları kullanmaz. Ama E'nin sol kılavuzu hâlâ B'yi gösterir. Kök ortada tersten gezinen ya da öncül arayan bir yordam bu hatayı hemen ortaya çıkarır. Ders anlatımı bu noktada uyarır: kodun doğru çalıştığına hemen karar verilmemelidir; daha işletilecek bir if bloğu vardır.

Aynı yordam Durum 1 ağacında da denendi. saga_ekle(B, D), A(–, B(C, –)) ağacında altı atamalı kodla aynı sonucu verir: sıra A C B D, D'nin sol kılavuzu B'yi, sağ kılavuzu başlığı gösterir. Ebeveynin bayrağı TRUE olduğu için 11. satırdaki koşul yanlıştır ve if bloğu çalışmaz.

Maliyet. 5–10. satırlar sabit süredir. 12. satırdaki ardıl araması, çocuğun sağ alt ağacında sola iner; bu yol en çok ağacın yüksekliği kadardır. saga_ekle'nin zamanı en kötü durumda O(h), Durum 1'de O(1)'dir. Ek bellek O(1)'dir.

12.4.5Sola ekleme

sola_ekle, çocukla gösterilen düğümü ebeveynin sol çocuğu yapar. Yordam saga_ekle'nin aynasıdır: sol ile sağ ve öncül ile ardıl yer değiştirir. Ebeveynin eski öncülü, çocuğun öncülü olur. Ebeveynin sol alt ağacı varsa o alt ağacın en sağındaki düğümün, yani çocuğun yeni öncülünün, sağ kılavuzu çocuğa çevrilir. Bunun için kök ortada öncülü bulan bir yordam gerekir. Öncül kuralı ardıl kuralının aynasıdır: sol alt ağaç varsa onun en sağındaki düğüm, yoksa sol kılavuzun gösterdiği düğüm.

kilavuz_gost kokortada_oncel_bul(kilavuz_gost L) {
  kilavuz_gost p = L->solCocuk;
  if (!L->solKilavuz)
    while (!p->sagKilavuz) p = p->sagCocuk;
  return p;
}
void sola_ekle(kilavuz_gost baba, kilavuz_gost cocuk) {
  cocuk->solCocuk   = baba->solCocuk;
  cocuk->solKilavuz = baba->solKilavuz;
  cocuk->sagCocuk   = baba;
  cocuk->sagKilavuz = TRUE;      // ardılı ebeveyn
  baba->solCocuk    = cocuk;
  baba->solKilavuz  = FALSE;
  if (!cocuk->solKilavuz) {      // baba'nın sol alt ağacı vardı
    kilavuz_gost p = kokortada_oncel_bul(cocuk);
    p->sagCocuk = cocuk;         // öncülün ardılı çocuk
  }
}

kokortada_oncel_bul yordamı başka bir iş için de kullanılabilir: başlıktan başlayıp başlığa dönene dek öncülden öncüle geçmek, ağacı kök ortada tersten gezer. Bu, alıştırmalarda ele alınır. Başlığın öncülü, kök ortada sıradaki son düğümdür: başlığın sol bayrağı FALSE, sol işaretçisi köktür ve kökten sağa sağa inilince en sağdaki düğüme varılır.

12.4.6Ağacı geri vermek

Bir C programında malloc ile alınan her blok işi bitince free ile geri verilmelidir. Verilmeyen bloklar program sonuna dek bellekte kalır. Buna bellek sızıntısı denir. Uzun çalışan bir programda sızıntı, belleğin yavaş yavaş tükenmesine yol açar. Kılavuzlu ağacı geri vermek de gezinme ile yapılır:

void kilavuzlu_agac_sil(kilavuz_gost L) {
  kilavuz_gost p = kokortada_ardil_bul(L), sonraki;
  while (p != L) {
    sonraki = kokortada_ardil_bul(p);  // önce ardıl bulunur
    free(p);                           // sonra düğüm geri verilir
    p = sonraki;
  }
  free(L);                             // en son başlık
}

Sıra önemlidir. Bir düğüm free ile geri verildikten sonra onun alanlarını okumak, serbest bırakılmış belleği okumaktır ve tanımsız davranıştır. Bu yüzden önce ardıl bulunur ve sonraki'ne yazılır, sonra düğüm geri verilir. Ardıl yordamı yalnız p'nin ve sağ alt ağacındaki düğümlerin alanlarını okur. Bu düğümler henüz geri verilmemiştir, çünkü kök ortada sırada p'den sonra gelirler. Başlık en son geri verilir; gezinmenin durma koşulu onun adresine bakar.

Bu notun bütün kodları, malloc ve free çağrılarını sayan bir sarmalayıcıyla sınandı. Sunumdaki kodlar ve notun ek yordamları tek bir sürücüde çalıştırıldı: 32 malloc ve 32 free sayıldı; ayrıntılı sınamada bu sayılar 2116'şar oldu. Sızıntı yoktur.

12.4.7Kod kalitesi

Kılavuzlu ağaç yordamları kısadır ama hataya açıktır. Bu yordamlar, iyi kod yazmanın birkaç ilkesini somut olarak gösterir.

NULL denetiminin yeri. saga_ekle, baba'nın ya da cocuk'un NULL olup olmadığını denetlemez. Bu bir unutkanlık değil, bir tasarım kararıdır. Ders anlatımındaki gerekçe şudur: saga_ekle tek başına kullanılmak için değil, başka bir yordamın içinde kullanılmak için yazılmıştır; NULL denetimi onu kullanan yordamda yapılmalıdır. Örneğin kılavuzlu bir ikili arama ağacına ekleme yapan yordam önce yeni değerin sağa mı sola mı ekleneceğini bulur. Sıradan ağaçtaki tek atamanın yerine saga_ekle ya da sola_ekle'yi çağırır. Bu noktada baba zaten gerçek bir düğümdür. Ama yordam bir kütüphanenin parçası olacak ve herkes doğrudan çağırabilecekse denetim yordama konmalıdır. Denetim yapılmıyorsa bu, açıklamada yazılmalıdır: “baba ve cocuk NULL olmamalı”. Genel amaçlı bir yordam için savunmacı bir sarmalayıcı şöyle yazılabilir:

#include <assert.h>
void saga_ekle_denetimli(kilavuz_gost baba, kilavuz_gost cocuk) {
  // baba ve cocuk NULL olmamalı; cocuk henüz ağaçta olmamalı
  assert(baba != NULL && cocuk != NULL);
  saga_ekle(baba, cocuk);
}

assert, koşulu yanlışsa programı dosya adı ve satır numarasıyla durdurur. Programcı hatalarını erken yakalar ve sınama sırasında çok değerlidir. NDEBUG tanımlanarak derlenen sürümde kaldırılır; bu yüzden kullanıcı girdisinden gelebilecek hatalar için değil, “bu asla olmamalı” denen durumlar için kullanılır. Kullanıcı hatasına karşı bir hata kodu döndürmek daha uygundur.

Açıklama satırı. Açıklama satırı kodun ne yapmak istediğini söylemeli, kodun kendisini tekrarlamamalıdır.

/* KÖTÜ: kodu tekrarlıyor */
if (!cocuk->sagKilavuz)  // sağ kılavuz FALSE mu
/* İYİ: niyeti söylüyor */
if (!cocuk->sagKilavuz)  // ebeveynin alt ağacı var mı

“Sağ kılavuz FALSE mu” açıklaması okura yeni bir şey söylemez; aynı bilgi kodda yazılıdır. “Ebeveynin alt ağacı var mı” ise niyeti söyler. Niyet ile kod yan yana durunca okur ikisini karşılaştırabilir: “yapmak istediği doğru, ama kodu yanlış yazmış” diyebilir. Hata ayıklama böyle kolaylaşır. Ders anlatımında bu konu açıkça vurgulanır: sonradan gelen okur “ben onu zaten biliyorum” dememeli; açıklama satırları kodda söylenenden farklı bir şey söylemelidir.

Tek yordam. Her durum için ayrı yordam yazmak mümkündü: cocukYok_sagaEkle, cocukVar_sagaEkle, cocukYok_solaEkle, cocukVar_solaEkle. Bu, kodu bölük pörçük eder; kullanan, hangi yordamı çağıracağına her seferinde karar vermek zorunda kalır. Karmaşıklığı artırmadan dört yordamı ikiye indirmek iyidir. Ama ters yöndeki aşırılıktan da kaçınılmalıdır. İç içe if'lerle bütün durumları tek bir yordama sıkıştırmak okunmaz bir kod doğurur. Öyle olacağına ayrı ayrı yordamlar daha iyidir. saga_ekle'nin başarısı, iki durumun ortak işini ortak biçimde tanımlamasından gelir: kılavuz bayrağını ebeveynden kopyalamak iki durumu tek atamada karşılar. Yöntem şöyle özetlenebilir: önce üç beş farklı durum analiz edilir; sonra yordamın adı, dönüş değeri ve parametreleri belirlenir; ortak işler ortak biçimde yazılır. Sonuç sade, okunabilir ve bakımı kolay bir koddur. Ders anlatımı bu ilkeleri yazılım mühendisliğinin temeli sayar ve öğrenilmelerinin yıllar aldığını hatırlatır.

Teyakkuz. Kılavuzlu ağaç kodu yazarken her satırda “bunu yapıyorum, ama doğru mu yapıyorum?” diye sormak gerekir. Durum 1'in kodu Durum 1 için kusursuzdur ve Durum 2'de sessizce ağacı bozar. saga_ekle'nin ilk altı satırından sonra ağaç doğru görünür ama bir kılavuz hâlâ yanlıştır. Bu tür hatalar ancak bütün durumların ayrı ayrı denenmesiyle ve hem ileri hem geri gezinmeyle yakalanır.

12.5Kazanç, bedel ve karmaşıklık özeti

Kılavuzlu ağacın getirdiği ve götürdüğü şeyler iki listede toplanabilir. Kazançlar: gezinme yığınsız ve O(1) ek bellekle yapılır; her düğümden ardıla ve öncüle en çok O(h)'de, gezinme içinde amortize O(1)'de geçilir; boş alanlar boşa gitmez. Bedeller: her düğümde iki bayrak tutulur; ekleme ve silme daha girift olur; ağaca dokunan her yordam kılavuzları gözetmek zorundadır. Tablo 12.13 bölümün yordamlarının maliyetlerini bir arada verir.

12.6Sık yapılan hatalar

1. Bayrağa bakmadan işaretçiyi gerçek çocuk sanmak. Kılavuzlu ağaçta hiçbir işaretçi NULL değildir. NULL'a dek inen bir döngü durmaz; kılavuzlar ve başlık üzerinden halkada döner. Her iniş solKilavuz ya da sagKilavuz ile denetlenir.
2. Başlık düğümünü unutmak. Başlıksız bir ağaçta ilk düğümün sol ve son düğümün sağ kılavuzu havada kalır. Bunlara NULL yazılırsa gezinme yordamları özel durum ister; yazılmazsa çöp değerler izlenir.
3. Sağa eklemenin ikinci durumunda ardılın sol kılavuzunu güncellememek. İleri gezinme yine doğru sonuç verir ve hata gizli kalır; öncül arayan ya da tersten gezinen bir yordam yanlış düğüme gider.
4. cocuk->sagKilavuz'u sabit TRUE yazmak. İkinci durumda ebeveynin sağ alt ağacı bir kılavuz sayılır ve o alt ağacın sol kısmı gezinmeden düşer. Örnekte E kaybolur.
5. Boş ağaçta başlığın solKilavuz'unu unutmak. Boş ağaçta başlığın solu kendisidir ve bayrağı TRUE'dur. Bu bayrağa bakmadan L->solCocuk'u kök sanan bir arama başlığın verisini gerçek bir değer gibi okur.
6. Büyük ve küçük harfi karıştırmak. C büyük ve küçük harfe duyarlıdır: baba->SagCocuk ya da baba->SagKilavuz derlenmez, çünkü yapının alanı sagCocuk'tur. Kılavuzlu yapıda solCocuk, sıradan yapıda solcocuk yazıldığına da dikkat edilmelidir.
7. Atama sırasını bozmak. baba->sagCocuk = cocuk satırı cocuk->sagCocuk = baba->sagCocuk'tan önce yazılırsa ebeveynin eski ardılı kaybolur ve çocuk kendini gösterir.
8. Ağacı geri verirken önce free etmek. Düğüm geri verildikten sonra ardılı aranırsa serbest bırakılmış bellek okunur. Önce ardıl bulunur, sonra düğüm geri verilir.

12.7Alıştırmalar ve çözümleri

12.7.1Bir ağacın kılavuzlarını çizmek

Soru. A(B(D, E), C(–, F)) ağacının kılavuzlarını çiziniz; kaç kılavuz vardır?

Çözüm. Kök ortada sıra D B E A C F'dir. Ağaçta 6 düğüm vardır; Teorem 12.1'e göre 6 + 1 = 7 boş alan, yani 7 kılavuz olur. Kılavuzlar Örnek 12.2'de tek tek verildi: D → başlık, D → B, E → B, E → A, C → A, F → C, F → başlık. 2'si başlığa gider. Çözüm, ağacı kurup bayrakları sayan bir programla da doğrulandı.

12.7.2Öncül bulmak

Soru. Kök ortada öncülü bulan kokortada_oncel_bul yordamını yazınız.

Çözüm. Yordam ardıl bulmanın aynasıdır ve sola ekleme kesiminde verildi. Sol bayrak TRUE ise sol işaretçi doğrudan öncülü gösterir. Değilse sol çocuktan başlanır ve sağ bayrak TRUE olana dek sağa gidilir. Ana örnekte A'nın öncülü şöyle bulunur: p = B; B'nin sağ bayrağı FALSE, p = E; E'nin sağ bayrağı TRUE; sonuç E.

12.7.3Tersten gezinme

Soru. Kılavuzlu ağacı kök ortada tersten (G C F A …) gezen yordamı yazınız.

Çözüm. Başlıktan başlanır ve başlığa dönene dek öncülden öncüle ilerlenir:

void kilavuz_ters_dolas(kilavuz_gost L) {
  kilavuz_gost p = L;
  for (;;) {
    p = kokortada_oncel_bul(p);
    if (p == L) break;
    printf("%c ", p->veri);
  }
}

Başlığın öncülü son düğümdür (G); ilk düğümün (H) öncülü de başlıktır. Ana örnekte çıktı G C F A E B I D H'dir. Zaman Θ(n), ek bellek O(1)'dir; gerekçe Teorem 12.3'ün aynasıdır.

12.7.4Boş ağaca ilk düğüm

Soru. Boş ağaca (yalnız başlık) ilk düğümü sola_ekle(baslik, x) ile eklemek doğru mudur?

Çözüm. Doğrudur. Başlığın sol işaretçisi kendisini gösterir ve sol bayrağı TRUE'dur. sola_ekle bu ikisini çocuğa taşır: çocuğun solu başlığı gösterir ve bir kılavuzdur. Çocuğun sağı da ebeveyni, yani başlığı gösterir ve TRUE'dur. Başlığın solu çocuğa çevrilir ve sol bayrağı FALSE olur. Çocuğun sol bayrağı TRUE olduğu için if bloğu çalışmaz. Sonuçta tek düğümün iki kılavuzu da başlığı gösterir; bu, Tanım 12.3'teki düzenin tam kendisidir.

12.7.5Kök sonda gezinmenin zorluğu

Soru. Kök sonda gezinme kılavuzlarla neden zordur? Hangi ek bilgi işi kolaylaştırır?

Çözüm. Bir düğümün kök sonda ardılı ebeveynine bağlıdır. Düğüm ebeveyninin sağ çocuğuysa ya da ebeveynin sağ alt ağacı yoksa ardıl ebeveyndir; değilse ardıl, ebeveynin sağ alt ağacında kök sonda sırada ilk düğümdür. İki durumda da ebeveynin kim olduğu ve düğümün onun hangi çocuğu olduğu bilinmelidir. Kılavuzlar kök ortada öncül ve ardılı gösterir; bunlar ebeveynle her zaman örtüşmez. Her düğüme bir ebeveyn işaretçisi eklemek bu bilgiyi doğrudan verir ve kök sonda ardılı sabit sayıda adım ve bir iniş ile bulunur.

12.7.6Kılavuzlu ikili arama ağacına ekleme

Soru. Kılavuzlu bir ikili arama ağacına ekleme yordamını saga_ekle ve sola_ekle kullanarak yazınız.

Çözüm. Arama sıradan ikili arama ağacındaki gibidir; tek fark, inilecek yönün bayrağı TRUE olduğunda durulmasıdır. O noktada aranan değer düğümden küçükse sola_ekle, büyükse saga_ekle çağrılır. Yeni düğüm her zaman yaprak olur; bu yüzden iki yordam da birinci durumda çalışır ve sabit sürede biter.

int kilavuzlu_bst_ekle(kilavuz_gost L, char x) {
  // x yoksa ekler ve 1 döndürür; varsa 0 döndürür
  kilavuz_gost p;
  if (L->solKilavuz) {                  // ağaç boş
    sola_ekle(L, kilavuz_dugum(x));
    return 1;
  }
  p = L->solCocuk;                      // kökten başla
  for (;;) {
    if (x == p->veri) return 0;
    if (x < p->veri) {
      if (p->solKilavuz) break;         // sol çocuk yok
      p = p->solCocuk;
    } else {
      if (p->sagKilavuz) break;         // sağ çocuk yok
      p = p->sagCocuk;
    }
  }
  if (x < p->veri) sola_ekle(p, kilavuz_dugum(x));
  else             saga_ekle(p, kilavuz_dugum(x));
  return 1;
}

Ağaç boşsa (başlığın sol bayrağı TRUE) ilk düğüm başlığın soluna eklenir; önceki alıştırma bunun doğru olduğunu gösterdi. Yordam M F T B H P X K sırasıyla çağrıldı; sonra H bir kez daha eklenmek istendi ve 0 döndü. Kök ortada gezinme B F H K M P T X, ters gezinme X T P M K H F B yazdı. Arama O(h), ekleme O(1) sürer; toplam O(h)'dir.

12.8Özet

• n düğümlü ikili ağaçta 2n işaretçinin n − 1'i doludur; kalan n + 1 alan boştur.
• Kılavuzlu ikili ağaçta boş sol işaretçi kök ortada öncüle, boş sağ işaretçi kök ortada ardıla bağlanır. Bu işaretçilere kılavuz denir.
• solKilavuz ve sagKilavuz bayrakları gerçek bağı kılavuzdan ayırır. Alan sırası iyi seçilirse bayraklar 64 bitlik makinede dolgu baytlarına sığar.
• Başlık düğümü havada kalan iki kılavuzu toplar; kök L->solCocuk'tadır, başlığın sağı kendisidir. Boş ağaçta başlığın sol bayrağı TRUE'dur.
• Ardıl: sağ bayrak TRUE ise doğrudan sağ işaretçi; değilse sağ alt ağacın en solu. Öncül bunun aynasıdır.
• Kılavuzlu kök ortada gezinme en çok 2n + 1 işaretçi izler: Θ(n) zaman, O(1) ek bellek. Kök önde gezinme de aynı kılavuzlarla yapılır; kök sonda için ebeveyn bilgisi gerekir.
• Morris gezinmesi bayrak olmadan, kılavuzları geçici kurup sökerek O(n) zaman ve O(1) bellekle gezinir; gezinme sırasında ağaç değiştiği için eşzamanlı okumaya uygun değildir.
• saga_ekle kılavuz bayrağını ebeveynden kopyalayarak iki durumu tek yordamda birleştirir; ikinci durumda çocuk, ebeveynin eski ardılının öncülü yapılır. sola_ekle onun aynasıdır.
• İyi kod: açık tanımlı yordam, niyeti söyleyen açıklama, NULL denetiminin doğru yerde yapılması ve ortak işlerin ortak biçimde yazıldığı tek yordam.

12.9Kavram listesi

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

• boş işaretçi null pointer
• kılavuz thread
• kılavuzlu ikili ağaç threaded binary tree
• öncül predecessor
• ardıl successor
• başlık düğümü header node
• kök ortada inorder
• kök önde preorder
• kök sonda postorder
• gezinme traversal
• Morris gezinmesi Morris traversal
• çağrı yığını call stack
• çarpık ağaç skewed tree
• yükseklik height
• amortize analiz amortized analysis
• kendine başvuran yapı self-referential struct
• ikili arama ağacı binary search tree

12.10Kendini Dene

1. 15 düğümlü bir ikili ağaç kılavuzlu hâle getiriliyor. Kaç kılavuz kurulur ve kaçı başlığa gider?

   Cevap

   Boş alan sayısı 15 + 1 = 16'dır; 16 kılavuz kurulur. Ağacın biçimi ne olursa olsun yalnız ikisi başlığa gider: ilk düğümün sol ve son düğümün sağ kılavuzu.

2. Ana örnekte kokortada_ardil_bul(B) hangi düğümü döndürür? Döngü kaç kez döner?

   Cevap

   E'yi döndürür. B'nin sağ bayrağı FALSE, p = E olur. E'nin sol bayrağı TRUE olduğu için döngüye hiç girilmez: 0 tur.

3. Ana örnekte kokonde_ardil_bul(I) hangi düğümü döndürür?

   Cevap

   E. I'nın sol bayrağı TRUE olduğu için sağ kılavuzlar izlenir: I → B. B'nin sağ bayrağı FALSE'tur; döngü biter ve B'nin sağ çocuğu E döner.

4. Ana örneğe saga_ekle(E, Y) uygulanıyor. Hangi durumdur? Y'nin kılavuzları nereyi gösterir ve yeni kök ortada sıra nedir?

   Cevap

   E bir yapraktır; sağ alt ağacı yoktur, birinci durumdur. Y'nin sol kılavuzu E'yi, sağ kılavuzu E'nin eski ardılı A'yı gösterir. Sıra H D I B E Y A F C G olur.

5. Ana örneğe saga_ekle(A, Y) uygulanıyor. Hangi düğümün kılavuzu değişir?

   Cevap

   İkinci durumdur; A'nın sağ alt ağacı (C) Y'nin sağ alt ağacı olur. Y'nin ardılı C'nin en solundaki F'dir. F'nin sol kılavuzu A yerine Y'yi gösterir. Sıra H D I B E A Y F C G olur.

6. Sola çarpık 1000 düğümlü kılavuzlu bir ağaçta kokortada_ardil_bul(başlık) kaç işaretçi izler? Bütün gezinme kaç izler?

   Cevap

   İlk çağrı başlıktan köke, sonra 999 sol bağla en alttaki düğüme iner: satır 3'teki okumayla birlikte 1001 işaretçi. Bütün gezinme 2n + 1 = 2001 işaretçi izler; bu, Teorem 12.3'ün sınırına tam olarak erişen durumdur.

7. Morris gezinmesi A(B(D, E), C) ağacında kaç geçici kılavuz kurar? Genel olarak bu sayı neye eşittir?

   Cevap

   İki: E → A ve D → B. Sol çocuğu olan her düğüm için bir kılavuz kurulur ve aynı kılavuz daha sonra sökülür.

8. saga_ekle'de 10. satır (baba->sagKilavuz = FALSE) silinirse hangi durumda ağaç bozulur?

   Cevap

   Birinci durumda, ama sinsi biçimde. Ebeveynin bayrağı TRUE kalır. Kök ortada gezinme yine doğru sonuç verir, çünkü “kılavuz” sanılan sağ işaretçi zaten çocuğu, yani ebeveynin ardılını gösterir. Öteki yordamlar ise çocuğu atlar. A(B, –) ağacına C sağdan eklenince kök ortada gezinme B A C yazar; kök önde gezinme A B, tersten gezinme A B yazar. C kaybolmuştur. İkinci durumda bayrak zaten FALSE olduğu için zarar olmaz.

12.11İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Kesim 5.5. Bu notun yapısı, insert_right yordamı ve başlık düğümü düzeni oradaki biçimiyle izlenmiştir.
• D. E. Knuth, The Art of Computer Programming, Cilt 1, Kesim 2.3.1. Kılavuzlu ağaçlar, ardıl bulma ve kılavuzlu ağaca ekleme algoritmaları kanıtlarıyla ve alıştırmalarla anlatılır.
• J. M. Morris, “Traversing binary trees simply and cheaply”, Information Processing Letters 9(5), 1979. Geçici kılavuzlarla bayraksız gezinmenin özgün kısa makalesidir.

12.12Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. bs., Silicon Press, 2008. Kesim 5.5, Threaded Binary Trees.
2. A. J. Perlis, C. Thornton, “Symbol manipulation by threaded lists”, Communications of the ACM 3(4), 1960.
3. J. M. Morris, “Traversing binary trees simply and cheaply”, Information Processing Letters 9(5), 1979.
4. D. E. Knuth, The Art of Computer Programming, Cilt 1: Fundamental Algorithms, 3. bs., Addison-Wesley, 1997. Kesim 2.3.1.

İlgili sayfalar: Bölüm 12 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.