Bölüm 11: Arama Ağaçları

11.1İkili arama ağacı

Ağaç, her düğümün bir ebeveyni ve sıfır ya da daha çok çocuğu olan hiyerarşik bir yapıdır. Ebeveyni olmayan tek düğüme kök, çocuğu olmayan düğümlere yaprak denir. İkili ağaçta her düğümün en çok iki çocuğu vardır ve bunlar sol çocuk ile sağ çocuk olarak ayrılır. Bir düğüm ile onun altındaki bütün düğümler birlikte bir alt ağaç (subtree) oluşturur. Bu notta ağacın derinliği, kökten en uzak yaprağa giden yoldaki düğüm sayısıdır. Tek düğümlü ağacın derinliği 1, boş ağacınki 0'dır. Ağaç gezinmesinde üç sıra kullanılır. Kök önde (preorder) gezinmede önce kök, sonra sol ve sağ alt ağaç ziyaret edilir. Kök ortada (inorder) gezinmede sıra sol alt ağaç, kök, sağ alt ağaçtır. Kök sonda (postorder) gezinmede ise kök en sona kalır. Bu kavramlar ağaçlar konusundan bilinir; burada yalnız hatırlatma amacıyla verildi.

11.1.1Neden yeni bir yapı?

Bir öğrenci işleri sistemi düşünülsün. Sistem her gün binlerce kez öğrenci numarasıyla kayıt arar. Yeni öğrenciler kaydolur, mezun olanlar sistemden çıkar. Kayıtlar sırasız bir dizide tutulursa arama için bütün dizi taranır ve maliyet O(n) olur. Kayıtlar numaraya göre sıralı tutulursa ikili arama O(lg n)'de sonuç verir. Fakat bu kez her ekleme ve silmede sırayı korumak için öğeler kaydırılır; bu da O(n) işlem demektir. Bağlı listede ekleme ve silme birkaç işaretçi değişikliğiyle yapılır. Ama listenin ortasına doğrudan atlanamaz; ikili arama kullanılamaz ve arama yine O(n)'dir.

İkili arama ağacı ikili aramanın fikrini bağlı bir yapıya taşır. Sıralı dizide ikili arama önce ortadaki öğeye bakar. Aranan değer daha küçükse sol yarıda, daha büyükse sağ yarıda aramayı sürdürür. İkili arama ağacının kökü bu “ortadaki öğe” gibi davranır. Sol alt ağaç sol yarının, sağ alt ağaç sağ yarının yerini tutar. Fark şuradadır: yarılar dizideki ardışık hücreler değil, işaretçilerle bağlanmış düğümlerdir. Yeni bir öğe eklemek için hiçbir öğe kaydırılmaz; yalnız uygun yerdeki bir NULL işaretçi yeni düğümü gösterecek biçimde değiştirilir.

11.1.2Tanım ve sıralı gezinme

Tanımın dördüncü maddesi onu özyinelemeli yapar: aynı koşul her düğümde, o düğümün kök olduğu alt ağaç için de geçerlidir. İkinci ve üçüncü maddelerdeki “bütün” sözcüğü önemlidir. Koşul yalnız düğümün çocuklarını değil, alt ağacın en derindeki öğelerini de kapsar. Kökün sol alt ağacının en altındaki, en sağdaki öğe bile kökten küçük olmalıdır.

Birinci madde ağacı bir küme gibi kullanır. Aynı değer ağaca ikinci kez girmez. Uygulamada değer çoğu zaman bir kaydın anahtarıdır (key): öğrenci numarası, T.C. kimlik numarası ya da bir sözcük. Kaydın öteki alanları anahtarla birlikte düğümde durur. Tekrarlı anahtarlara izin vermek gerekirse ya düğüme bir sayaç eklenir ya da eşit anahtarlar kurala göre hep aynı yana (örneğin sağa) konur. Bu notta tanıma uyulur: eşit değer gelirse ekleme yapılmaz.

Tanım ikili arama ağacını ikili ağaçların bir alt kümesi yapar. Her ikili arama ağacı bir ikili ağaçtır; ağaç üzerinde yazılmış gezinme, kopyalama ve eşitlik yordamları ona da uygulanır. Tersi doğru değildir. Sıradan bir ikili ağaçta değerler herhangi bir düzende durabilir. Tanımdaki düzenin en önemli sonucu aşağıdaki teoremdir.

Kanıt. Önce ağacın ikili arama ağacı olduğu varsayılsın ve düğüm sayısı üzerinden tümevarım yapılsın. Boş ağaç ve tek düğümlü ağaç için iddia açıktır. Daha büyük bir ağaçta kök ortada gezinme önce sol alt ağacı, sonra kökü, sonra sağ alt ağacı yazar. Sol ve sağ alt ağaçlar da ikili arama ağacıdır; tümevarım varsayımına göre her biri kendi içinde artan sırada yazılır. Sol alt ağaçtaki bütün değerler kökten küçük, sağdakiler kökten büyüktür. Öyleyse üç parça art arda geldiğinde dizi baştan sona artandır. Ters yön için kök ortada dizinin kesin artan olduğu varsayılsın. Sol alt ağacın her değeri dizide kökten önce, sağ alt ağacın her değeri kökten sonra yazılır. Dizi artan olduğuna göre soldakiler kökten küçük, sağdakiler büyüktür. Değerler de birbirinden farklıdır. Alt ağaçların kök ortada dizileri bu dizinin ardışık parçalarıdır; onlar da artandır. Tümevarımla alt ağaçlar da ikili arama ağacıdır. ∎

Teoremin pratik bir sonucu vardır. Bir değer kümesini sıralamak için değerler boş bir ikili arama ağacına tek tek eklenir, sonra ağaç kök ortada gezilir. Bu yönteme ağaç sıralaması (tree sort) denir. Ağaç dengeli kalırsa toplam maliyet O(n lg n) olur. Teorem ikinci bir işe de yarar: bir ağacın ikili arama ağacı olup olmadığı, kök ortada gezinip her değerin öncekinden büyük olduğuna bakılarak O(n) sürede denetlenir.

11.1.3Tanımı denetlemek

Şekil 11.1 üç ikili ağacı gösterir. Soldaki ağaçta her düğüm yalnız kendi çocuklarıyla karşılaştırılırsa bir sorun görünmez. 15'in sol çocuğu 9, sağ çocuğu 22'dir ve 9 < 15 < 22'dir. 20'nin çocukları 19 ve 21'dir; onlar da doğru yerdedir. Ancak 22, kökü 18 olan ağacın sol alt ağacındadır. Tanımın ikinci maddesi sol alt ağaçtaki bütün değerlerin 18'den küçük olmasını ister. 22 bu koşulu bozar; ağaç ikili arama ağacı değildir. Bu ağaçta 22 aranırsa kökte 22 > 18 karşılaştırması aramayı sağa yollar ve 22 hiçbir zaman bulunamaz.

Ortadaki ağaç dengesiz görünse de geçerlidir. 95'in solundaki her değer (80, 50, 2) 95'ten küçüktür; 80'in solu 50, 50'nin solu 2'dir ve sıralama hiçbir yerde bozulmaz. Tanım ağacın biçimi hakkında bir şey söylemez; yalnız değerlerin düzenini sınırlar. Sağdaki ağaçta kökün sağındaki her değer 35'ten büyüktür. 40'ın solunda 38 ve onun sağında 39 durur. İkisi de 40'tan küçük ve 35'ten büyüktür. Bu değerler, kökten kendilerine gelen yol üzerindeki her düğümün koşulunu sağlar; ağaç geçerlidir.

Örnekler, denetimin nasıl yapılacağını da gösterir. Her düğümün değeri için bir alt ve bir üst sınır vardır. Kökün sınırı yoktur. Bir düğümden sola inildiğinde üst sınır o düğümün değeri olur, sağa inildiğinde alt sınır. Soldaki ağaçta 22'ye kökten sola, sonra sağa inilerek gelinir. Alt sınır 15, üst sınır 18'dir; 22 bu aralığa girmez. Bu fikrin C gerçeklemesi alıştırmalar kesiminde verilir.

11.1.4Düğümün C'deki yapısı

Ağacın her düğümü bir struct ile temsil edilir. Düğümde bir veri alanı ve iki işaretçi bulunur. İşaretçilerden biri sol çocuğu, öteki sağ çocuğu gösterir. Çocuk yoksa işaretçinin değeri NULL'dır. Sunumdaki tanım aşağıdadır.

typedef enum { FALSE, TRUE } boolean;
typedef struct dugum *agac_gost;
struct dugum {
    agac_gost solcocuk;
    int       veri;
    agac_gost sagcocuk;
};
/* ogeal(): malloc + NULL denetimi,
   çocukları NULL yapar */

İlk satır, C'de olmayan mantıksal tipi bir sayımla (enum) kurar: FALSE 0, TRUE 1 değerini alır. İkinci satır agac_gost adını “struct dugum'a işaretçi” anlamında tanımlar. Bu tanım yapının kendisinden önce gelir. C'de henüz tanımlanmamış bir yapıya işaretçi bildirmek serbesttir; derleyicinin bilmesi gereken tek şey işaretçinin boyutudur. Böylece yapının içinde kendi tipine işaretçi kullanılabilir. Bu tür yapılara öz başvurulu yapı (self-referential structure) denir.

64 bitlik bir makinede her işaretçi 8, int 4 bayttır. Derleyici veri'den sonra 4 baytlık bir boşluk bırakır, çünkü sagcocuk 8'in katı olan bir adreste başlamalıdır. Bu yüzden sizeof(struct dugum) 24 bayttır; değer zig cc ile x86-64 üzerinde ölçülerek doğrulandı. Yani her düğüm 4 baytlık bir veri için 20 baytlık ek yük taşır. Bağlı yapıların esnekliğinin bedeli budur.

Sunum düğüm ayıran ogeal() yordamını yalnız açıklamasıyla verir: malloc ile yer ayırır, NULL denetimi yapar ve çocukları NULL yapar. Aşağıda bu tarife uyan bir gerçekleme var. Notun bütün sürücü programları bu yordamı kullandı.

agac_gost ogeal(void) {
  agac_gost r = malloc(sizeof *r);   /* 24 bayt */
  if (!r) {
    fprintf(stderr, "Bellek yetersiz\n");
    exit(EXIT_FAILURE);
  }
  r->solcocuk = r->sagcocuk = NULL;
  return r;
}

malloc(sizeof *r) yazımı, ayrılan boyutu tipin adı yerine işaretçinin gösterdiği nesneden alır. Yapının adı değişse de satır doğru kalır. malloc bellek bulamazsa NULL döndürür. Bu durumda r->solcocuk'a yazmak tanımsız davranış olur; yordam bu yüzden hatayı bildirip programı sonlandırır. Son satırdaki iki atama çok önemlidir. malloc belleği temizlemez; çocuk işaretçileri rastgele bir adres taşıyabilir. Ağaç yordamları bir dalın sonunu NULL ile tanır. Çocukları temizlenmemiş bir yaprak, yordamları belleğin rastgele bir yerine yönlendirir.

Tablo 11.1, kökü 47 olan küçük bir ağacın bellekteki görünümünü örnek adreslerle verir. Ağacın düğümleri bellekte art arda durmak zorunda değildir; her biri malloc'un bulduğu ayrı bir yerdedir. Ağacın biçimi yalnız işaretçi alanlarındaki adreslerle belirlenir.

Tabloda kök işaretçisi L'nin değeri 0x1A40'tır. L->veri 47'yi, L->solcocuk->veri 26'yı verir. 26 bellekte 55'ten sonra durur, ama ağaçta 55'in solundadır. Düğümlerin bellek sırası ile ağaçtaki yerleri arasında bir ilişki yoktur.

11.2Ekleme

İkili arama ağacına ekleme, bağlı listeye eklemeden daha kısıtlıdır. Listede yeni öğe başa, sona ya da araya konabilir. İkili arama ağacında ise yeni değerin yeri tektir ve ağacın içeriğiyle belirlenir. Bu kesim önce bu yerin nasıl bulunduğunu, sonra ekleme sırasının ağacın biçimini nasıl değiştirdiğini anlatır. Ardından ekleme yordamı C ile yazılır ve adım adım izlenir.

11.2.1Yeri ağaç belirler

Sunumda hoca bu noktayı bir sınıf anısıyla anlatır. Bir öğrenciden bir değer söylemesi istenir. Öğrenci “15'in sağına ekleyin” diye yer de gösterir. Hoca yerin öğrencinin değil, ağacın işi olduğunu söyler. Gerçekten de ekleme yordamının imzası yalnız eklenecek değeri ve ağacı alır; yer bilgisi almaz. Yordam yeni değeri kökten başlayarak arar, bulamadığı yerde ekler. Değer ağaçta yoksa arama bir NULL işaretçide biter. O NULL, yeni değerin tanımı bozmadan durabileceği tek yerdir.

Yer tek olsa da aynı değer kümesi farklı ağaçlarla gösterilebilir. Ağacın biçimi, değerlerin hangi sırayla eklendiğine bağlıdır. Sunumdaki soru bu durumu küçük bir örnekle sorar.

Örneğin son adımındaki sayım genel bir sınır verir.

Kanıt. Kök 1. düzeydedir. Her düğümün en çok iki çocuğu olduğundan i. düzeyde en çok 2ⁱ⁻¹ düğüm bulunur. Derinliği k olan ağaçta düzeyler 1'den k'ye kadardır. Toplam en çok 1 + 2 + 4 + … + 2^k−1 = 2^k − 1 olur. n düğüm sığması için 2^k − 1 ≥ n, yani k ≥ lg(n + 1) gerekir; k tam sayı olduğundan k ≥ ⌈lg(n + 1)⌉'dir. Üst sınır için her düzeyde en az bir düğüm bulunduğu yeterlidir: k düzey en az k düğüm ister, öyleyse k ≤ n'dir. ∎

n = 5 için alt sınır ⌈lg 6⌉ = 3, üst sınır 5'tir. Şekil 11.2 bu iki ucu ve aradaki derinliği gösterir. Sınırların anlamı açıktır. Ağaçta arama en kötü durumda derinlik kadar düğüme bakar. Derinliği ⌈lg(n + 1)⌉'e yakın bir ağaç ikili arama kadar hızlıdır. Derinliği n'ye yakın bir ağaç ise bağlı listeden farksızdır.

11.2.2Ekleme sırası ağacın biçimini değiştirir

Sunum aynı dokuz değeri iki farklı sırayla iki boş ağaca ekler. Değerler 17, 26, 34, 47, 49, 52, 55, 84, 93'tür. Soldaki ağaca ekleme sırası 47, 55, 49, 26, 34, 17, 52, 84, 93'tür. Sağdaki ağaca ise 26, 17, 47, 93, 84, 52, 34, 55, 49 sırasıyla eklenir. Her adımda kural aynıdır: kökten başlanır, yeni değer düğümdekinden küçükse sola, büyükse sağa inilir ve ilk NULL'a konur.

Soldaki ağaçta ilk değer 47 kök olur. 55 ondan büyüktür ve sağına girer. 49, 47'den büyük olduğu için sağa iner; orada 55'ten küçük olduğu için 55'in soluna konur. 26 ve 34 kökün solunda yerleşir; 17 de 26'nın solunu alır. 52, 47 → 55 → 49 yolunu izleyip 49'un sağına; 84, 55'in sağına; 93 de 84'ün sağına girer. Sonuçta en uzun yol 47 → 55 → 49 → 52'dir ve ağacın derinliği 4'tür.

Sağdaki ağaçta kök 26'dır. 17 onun soluna, 47 sağına girer. Sonraki 93, 47'nin sağına; 84, 93'ün soluna; 52 de 84'ün soluna iner. Her yeni değer bir öncekinin altına eklendiği için ağaç aşağı doğru uzar. 34, 47'nin soluna yerleşir. 55, 26 → 47 → 93 → 84 → 52 yolundan geçip 52'nin sağına, 49 da 52'nin soluna konur. En uzun yol 26 → 47 → 93 → 84 → 52 → 55'tir ve derinlik 6'dır. Şekil 11.3 eklemelerin yarısından sonraki ve en sondaki durumu gösterir.

İki ağaç aynı kümeyi tutar ve ikisi de tanıma uyar. Kök ortada gezinmeleri, Teorem 11.1 gereği aynı sıralı diziyi verir. Ama arama maliyetleri farklıdır. Soldaki ağaçta en kötü arama 4 düğüme, sağdakinde 6 düğüme bakar. Ekleme sırası ağacın biçimini, biçim de bütün işlemlerin süresini belirler. Sunumdaki ifadeyle verilerin eklenme sırası önemlidir.

11.2.3Çarpıklık ve dengeli ağaçlar

Ekleme sırasının en kötü hâli, verilerin sıralı gelmesidir. 1, 2, 3, …, n sırasıyla eklenen her değer öncekilerin hepsinden büyüktür; her biri en sağdaki düğümün sağına girer. Ağaç sağa uzanan bir zincire döner. Ters sırada gelen veri de sola uzanan bir zincir kurar. Bütün düğümleri tek bir yöne uzanan bu ağaçlara çarpık ağaç (skewed tree) denir. Çarpık ağacın derinliği n'dir ve her işlem bağlı listedeki kadar sürer. Sıralı veri gerçek hayatta sanıldığından sık görülür. Tarihe göre gelen kayıtlar, artan sırayla verilen öğrenci numaraları ya da önceden sıralanmış bir dosya bu duruma örnektir.

Derinliği lg n düzeyinde kalan ağaca dengeli ağaç (balanced tree) denir. Dengeli bir ikili arama ağacında ekleme, silme ve arama O(lg n) sürer. Sorun, dengenin kendiliğinden korunmamasıdır. Bu soruna iki tür çözüm geliştirilmiştir.

• Kendini dengeleyen ağaçlar (self-balancing trees), her ekleme ve silmeden sonra ağacı yerel değişikliklerle yeniden dengeler. AVL ağacı ve kırmızı-siyah ağaç bu türdendir. Derinlik her durumda O(lg n)'de kalır.
• Sık kullanılan düğümleri köke yaklaştıran ağaçlar, dengeyi değil erişim hızını hedefler. Bir düğüme her erişildiğinde o düğüm döndürmelerle köke taşınır. Sık aranan değerler böylece kökün yakınında toplanır. Sunumda “zig-zag” adıyla anılan bu yapının kaynaklardaki adı splay ağacıdır (splay tree). Yapıyı 1985'te D. Sleator ile R. Tarjan önermiştir. Tek bir işlem pahalı olabilir, ama uzun bir işlem dizisinde işlem başına ortalama maliyet O(lg n)'dir.

Hoca bu konuda şunu söyler: ağacın dengeli olması çok önemliyse ağacı dengeli kuran algoritmalar kullanılmalıdır. Bu algoritmalar çok zor değildir, yalnız biraz daha uzundur. Notun son büyük kesimi bunların en bilinenini, AVL ağacını ayrıntılı ele alır.

11.2.4Ağaçtan ekleme sırasına, gezinmeden ağaca

Sunum bu noktada üç soru işaretiyle iki düşündürücü soru sorar. İlki şudur: ağacın görüntüsünden verilerin eklenme sırası elde edilebilir mi? Gelen veriye göre oluşan ağaç tek midir?

Sorunun ikinci yarısının cevabı evettir. Ekleme yordamı rastgelelik içermez; aynı değerler aynı sırayla geldiğinde her seferinde aynı ağaç oluşur. Ama ters yön tek değildir. 2, 1, 3 sırası kökü 2, solu 1, sağı 3 olan ağacı kurar. 2, 3, 1 sırası da aynı ağacı kurar; çünkü 1 ile 3 birbirinin yolunda değildir ve hangisinin önce geldiği önemsizdir. Bir ekleme sırasının belirli bir ağacı kurması için tek koşul vardır: her düğüm kendi soyundan önce eklenmelidir. Bir ata, soyundaki bir düğümden sonra gelirse o düğüm başka bir yere yerleşir. Kök önde sıra bu koşulu her zaman sağlar; çünkü bir düğümü, alt ağacındaki bütün düğümlerden önce yazar. Bu yüzden ağacın kök önde gezinmesi daima geçerli bir ekleme sırasıdır.

İkinci soru şudur: kök önde, kök ortada ve kök sonda gezinme sıralarından ağacın görüntüsü elde edilebilir mi? Genel bir ikili ağaçta tek bir gezinme sırası yetmez. Örneğin kök önde sırası A B olan iki ağaç vardır: B, A'nın sol çocuğu da olabilir, sağ çocuğu da. Kök ortada sıra ile kök önde (ya da kök sonda) sıra birlikte verilirse ağaç tek olarak belirlenir. Kök önde sıranın ilk öğesi köktür. Kök ortada sırada kökün solundakiler sol alt ağacı, sağındakiler sağ alt ağacı oluşturur. Aynı işlem alt ağaçlara özyinelemeli uygulanır.

İkili arama ağacında iş kolaylaşır. Kök ortada sıra zaten bilinir: değerlerin artan sırasıdır. Bu yüzden yalnız kök önde sıra (ya da yalnız kök sonda sıra) ağacı belirlemeye yeter. Daha da kısası, kök önde sıradaki değerler boş bir ağaca o sırayla eklenir ve ağaç yeniden kurulur.

Sunumda hoca bu konuya bir gözlem de ekler. Daha önce ikili ağaç yordamları, arka planda gerçek bir ağaç olmadığı için kodu çalıştırarak denenemiyordu. Ekleme yordamı yazıldıktan sonra bu engel kalkar. Birkaç satırla örnek ağaçlar kurulur; gezinme, kopyalama ve eşitlik yordamları bu ağaçlarla gerçekten çalıştırılır. Bu notun bütün sürücü programları da ağaçlarını bu yolla kurdu.

11.2.5Ekleme yordamı

Ekleme algoritması dört gözleme dayanır. Birincisi, her iki çocuğu da olan bir düğüme eklenemez; yeni öğe en az bir çocuğu eksik olan bir düğümün boş yerine girer. İkincisi, gelen değer kökten başlayarak aranır. Düğümdeki değer yeni değerden büyükse sola, küçükse sağa ilerlenir. Üçüncüsü, aynı değer bulunursa tanım bozulacağı için ekleme yapılmaz. Dördüncüsü, arama işaretçisinin ilk rastladığı NULL'ın yerine yeni öğe konur. Ama NULL'a gelindiğinde arama işaretçisi artık hiçbir düğümü göstermez. Yeni düğümün bağlanacağı ebeveyni hatırlamak için bir adım arkadan gelen ikinci bir işaretçi gerekir. Kodda bu işaretçinin adı q'dur.

boolean arama_agacina_ekle(int x, agac_gost *L) {
  agac_gost q = NULL, p = *L, r; // q arka, p ön
  while (p) {                    // NULL'a dek in
    q = p;                       // arkayı günle
    if (x < p->veri) p = p->solcocuk;
    else if (x > p->veri) p = p->sagcocuk;
    else { printf("Benzer deger var.\n");
           return FALSE; }
  }
  r = ogeal();                   // çocuklar NULL
  r->veri = x;
  if (*L == NULL) *L = r;        // boş ağaç: kök
  else if (x < q->veri) q->solcocuk = r;
  else q->sagcocuk = r;
  return TRUE;
}

Kodun satırları şöyle çalışır.

• 2. satır. Üç yerel işaretçi tanımlanır. p ağacın kökünden yola çıkar; *L, çağıranın kök işaretçisinin değeridir. q, p'nin bir adım gerisinde kalır ve başta NULL'dır. r yeni düğümü tutacaktır.
• 3.–9. satırlar. Döngü p NULL olana kadar sürer. Her turda önce q = p ile geri işaretçi güncellenir, sonra p bir düzey iner. x düğümdeki değerden küçükse sol çocuğa, büyükse sağ çocuğa geçilir. İkisi de değilse değerler eşittir: yordam bir uyarı yazar ve FALSE döndürür. Bu durumda ağaçta hiçbir şey değişmez ve bellek ayrılmaz.
• 10.–11. satırlar. Döngü bittiğinde p NULL'dır, q ise yeni düğümün ebeveyni olacak düğümü gösterir. Yeni düğüm ogeal() ile ayrılır; çocukları NULL'dır. Veri alanına x yazılır.
• 12. satır. Ağaç boşsa döngü hiç dönmemiştir ve q hâlâ NULL'dır. Yeni düğüm kök olur: *L = r. Bu atama çağıranın kök değişkenini değiştirir.
• 13.–14. satırlar. Ağaç boş değilse x ebeveynin değeriyle bir kez daha karşılaştırılır ve yeni düğüm ebeveynin sol ya da sağ işaretçisine bağlanır.

Döngüde p'nin hangi yöne gittiği bilinir, ama döngü bitince bu bilgi kaybolur. 13. satırdaki ikinci karşılaştırma bu bilgiyi yeniden üretir. Bunun yerine döngüde bir yön değişkeni tutmak da mümkündür. Kod ise kısalığı seçmiştir. Yalnız bir karşılaştırma fazladan yapılır ve maliyet değişmez.

11.2.6Kod izleme: 50'yi eklemek

Sunum, soldaki ağaca (47, 55, 49, 26, 34, 17, 52, 84, 93) 50'nin eklenmesini izler. Tablo 11.2 her adımda değişkenlerin durumunu verir.

Tablodaki dört karşılaştırma, kökten 52'ye uzanan yoldaki dört düğüme karşılık gelir. Eklemeden önce ağacın derinliği 4'tür; 50, 47 → 55 → 49 → 52 yolunun altına beşinci düzeye girer ve derinlik 5 olur. Ekleme tek bir işaretçiyi değiştirdi: 52'nin sol çocuğunu. Ağacın geri kalanına dokunulmadı. Şekil 11.4 izlemenin dört karesini gösterir.

Aynı çağrı 47 ile yapılsaydı döngünün ilk turunda eşitlik bulunurdu. Yordam “Benzer deger var.” yazıp FALSE döndürürdü. Sürücü programda bu iki durum denendi: 50 için dönüş değeri 1, 47 için 0'dır. Eklemeden sonra ağacın kök önde gezinmesi 47 26 17 34 55 49 52 50 84 93 olur.

11.2.7Neden agac_gost *L?

Ekleme yordamı ağacı agac_gost L olarak değil, agac_gost *L olarak alır. Yani kök işaretçisinin değerini değil, adresini ister. Bunun nedeni boş ağaçtır. Ağaç boşsa (*L == NULL) eklenen öğe kök olur ve çağıranın kök değişkeni bu yeni düğümü göstermelidir. C'de bütün parametreler değerle geçirilir. Yordam agac_gost L alsaydı, L = r ataması yalnız yordamın yerel kopyasını değiştirirdi. Çağıranın kok değişkeni NULL kalır, ayrılan düğüm de hiçbir yerden gösterilmediği için sızardı.

Bir değişkeni bir yordama değiştirtmek için onun adresi gönderilir. Bu yönteme adresle çağrı (call by reference) denir. Kök değişkeni zaten bir işaretçi olduğu için adresi bir işaretçinin işaretçisidir (pointer to pointer). Çağrı arama_agacina_ekle(x, &kok) biçiminde yazılır. Yordamın içinde *L, çağıranın kok değişkeninin kendisidir; *L = r o değişkene yazar.

Aynı sorunun ikinci bir çözümü daha vardır: yordam ağacın yeni kökünü dönüş değeri olarak verir. Sunum bu özyinelemeli sürümü de gösterir.

/* Özyinelemeli alternatif: yeni kökü döndürür */
agac_gost ekle(agac_gost L, int x) {
  if (!L) {
    L = ogeal();
    L->veri = x;
  } else if (x < L->veri)
    L->solcocuk = ekle(L->solcocuk, x);
  else if (x > L->veri)
    L->sagcocuk = ekle(L->sagcocuk, x);
  return L;        /* kok = ekle(kok, x); */
}

Yordam boş bir alt ağaca gelince yeni düğümü ayırır ve onu döndürür. Boş olmayan bir düğümde, değere göre sol ya da sağ alt ağaca ekleme yapar. Alt çağrının dönüşünü ilgili çocuk işaretçisine yeniden atar. Alt ağaç boş değilse alt çağrı aynı işaretçiyi geri verir ve atama hiçbir şeyi değiştirmez. Alt ağaç boşsa alt çağrı yeni düğümü verir ve atama onu ağaca bağlar. Değer eşitse iki dal da atlanır ve düğüm olduğu gibi döner. Kullanım kok = ekle(kok, x); biçimindedir. Çağıran dönüş değerini atamayı unutursa boş ağaca yapılan ilk ekleme kaybolur. Bu sürümde hata bildirimi de yoktur: eşit değer sessizce reddedilir. Sürücü programda dokuz değer iki yordamla ayrı ayrı eklendi; iki ağacın kök önde gezinmesi aynı çıktı.

Ekleme yordamının maliyeti, yeni değerin indiği yolun uzunluğudur. Her düzeyde bir düğüme bakılır ve sabit sayıda işlem yapılır. Ağacın derinliği h ise ekleme O(h) sürer. Dengeli ağaçta h = O(lg n), çarpık ağaçta h = n'dir. Sunum bu aralığı Ω(lg n) – O(n) diye yazar. Alt sınır, hiçbir ağacın derinliğinin ⌈lg(n + 1)⌉'den küçük olamamasından gelir. Örneğin bütün düzeyleri dolu bir ağaçta boş işaretçilerin hepsi son düzeyin altındadır; her ekleme lg(n + 1) düğüme bakar. Döngüsel sürüm yalnız üç işaretçilik ek bellek kullanır, yani O(1). Özyinelemeli sürüm ise her düzey için bir çağrı çerçevesi açar ve O(h) ek bellek ister. Sıralı 2000 değerle kurulan çarpık ağaçta döngüsel yordam sorunsuz çalıştı. Özyinelemeli yordam bu derinlikte 2000 iç içe çağrı yapar. Windows'un varsayılan 1 MB'lık çağrı yığını 30 000 düğümlük bir zinciri de kaldırdı. Ama çağrı derinliği n ile büyür; yeterince uzun bir zincirde yığın taşar.

Sunumda “C99 düzeltmesi” diye anılan bir ayrıntı daha vardır. Kitaptaki özgün kodda q'ya ilk değer verilmez. Ağaç boşken döngü hiç dönmez ve q tanımsız bir değerle kalır. Kod *L == NULL denetimiyle bu değeri kullanmaktan kaçınır. Yine de derleyiciler “ilk değer verilmeden kullanılabilir” uyarısı verir. Sunumdaki kod q = NULL ile başlar; böylece uyarı da kalkar, kod da güvenli olur.

11.3Arama

Arama, ikili arama ağacının var oluş nedenidir. Ekleme ve silme de aramayla başlar: ekleme yeni değerin yerini, silme silinecek düğümü arar. Bu kesim aramayı önce bir döngüyle, sonra özyinelemeyle yazar. Ardından özyinelemeli aramadaki ince bir noktayı ve sıralı olmayan genel bir ikili ağaçta aramayı ele alır.

11.3.1Döngüsel arama

Aranan x değeri önce kökteki değerle karşılaştırılır. Eşitse arama biter. x daha küçükse aranan değer, varsa, sol alt ağaçtadır; tanım gereği sağ alt ağaçtaki her değer kökten, dolayısıyla x'ten büyüktür. x daha büyükse aynı akıl yürütme sağ alt ağacı gösterir. Seçilen alt ağaçta aynı işlem tekrarlanır. Bir NULL işaretçiye gelinirse değer ağaçta yoktur.

agac_gost arama_agacinda_ara(int x, agac_gost L) {
  while (L) {           // uygun alt ağaçta in
    if (x == L->veri) return L;
    if (x < L->veri) L = L->solcocuk;
    else             L = L->sagcocuk;
  }
  return NULL;          // bulunamadı
}

Yordam ağacı değerle aldığı L işaretçisini bir gezgin gibi kullanır. 2. satırdaki döngü L NULL olmadıkça sürer. 3. satır eşitliği denetler ve bulunan düğümün adresini döndürür. 4. ve 5. satırlar L'yi uygun çocuğa indirir. Döngüden çıkılırsa (7. satır) değer yoktur ve NULL döner. Burada L'nin değiştirilmesi çağıranı etkilemez; çağıranın kök işaretçisi yerinde kalır. Ekleme yordamının aksine aramaya adres göndermek gerekmez, çünkü arama ağacı değiştirmez.

Dönüş değeri olarak düğümün adresi seçilmiştir. Böylece çağıran hem değerin var olup olmadığını öğrenir, hem de düğümdeki öteki alanlara ulaşır. Anahtarla bir kayıt arandığında asıl istenen çoğu zaman bu öteki alanlardır.

Şekil 11.5 aramanın gücünü görsel olarak gösterir: her karşılaştırma bir alt ağacın tamamını eler. Ağaç dengeliyse her eleme kalan düğümlerin yaklaşık yarısını atar. Bu, sıralı dizide ikili aramanın davranışıdır. Ağaçta olmayan bir değer arandığında da aynı yol izlenir. Örneğin 60 aranırsa 47 → 55 → 84 yoluna bakılır. 84'ün sol çocuğu NULL olduğu için arama üç düğümden sonra NULL döndürür.

Aramanın maliyeti, bakılan yolun uzunluğudur ve ağacın derinliği h ile sınırlıdır: O(h). Dengeli ağaçta bu O(lg n), çarpık ağaçta O(n) eder. Döngüsel yordam ek bellek olarak yalnız L'yi kullanır: O(1).

Sunumda bu yordamın yanında hocanın bir benzetmesi yer alır. Müdür memura görevi tanımlarken çok açık konuşmalıdır; memur sonradan kapıyı çalıp soru sormak zorunda kalmamalıdır. Yordamın tanımı da böyledir. arama_agacinda_ara'nın sözleşmesi açıktır: değer varsa düğümün adresini, yoksa NULL döndürür. Boş ağaçta da doğru çalışır, ağacı değiştirmez ve küresel bir değişkene dokunmaz. Yordamı kullanan, onun içine bakmadan doğru kullanabilir.

11.3.2Özyinelemeli arama

Tanım özyinelemeli olduğu için arama da doğal olarak özyinelemeli yazılır. Boş ağaçta değer yoktur. Kökte değer bulunursa iş biter. Yoksa aynı soru uygun alt ağaca sorulur ve onun cevabı aynen yukarı iletilir.

agac_gost ara(int x, agac_gost L) {
  if (!L) return NULL;          // yok
  if (x == L->veri) return L;   // bulundu
  if (x < L->veri)
    return ara(x, L->solcocuk);
  return ara(x, L->sagcocuk);
}

İlk iki satır temel durumlardır. Ağaç boşsa (2. satır) NULL, kökte değer varsa (3. satır) kökün adresi döner. 4.–6. satırlar özyinelemeli adımdır. Her iki çağrının önünde return bulunur. Alt çağrı ne döndürürse bu çerçeve de onu döndürür ve başka bir iş yapmaz. Bir yordamın son işi kendi kendini çağırmaksa bu çağrıya kuyruk özyinelemesi (tail recursion) denir. Böyle bir yordam kolayca döngüye çevrilir: parametre yeni değeriyle güncellenir ve başa dönülür. Döngüsel arama, bu yordamın tam olarak bu dönüşümle elde edilmiş hâlidir. İyi eniyileme yapan derleyiciler bu dönüşümü kendileri de yapabilir.

Tablo 11.3 çağrıların inişini ve dönüşünü özetler. Üç çerçeve iner, en alttaki çerçeve düğümü bulur ve adresini döndürür. Dönüş yolunda çerçeveler hiçbir hesap yapmaz; aldıkları adresi aynen bir üste verirler. Şekil 11.6 üç anı gösterir: inişin ortasını, bulma anını ve sonucun köke ulaştığı anı.

Zaman maliyeti döngüsel sürümle aynıdır: O(h). Bellek maliyeti farklıdır. Her çağrı bir çerçeve açar ve en derin noktada h çerçeve aynı anda yığında durur. Ek bellek O(h)'dir. Dengeli ağaçta bu birkaç düzine çerçevedir ve önemsizdir. Çarpık ağaçta ise çağrı derinliği n'ye ulaşır.

11.3.3Özyinelemeli aramada bir tuzak

Sunum bir öğrencinin yazdığı aşağıdaki gövdeyi gösterir ve “Bu örnek çalışır mı?” diye sorar.

if (L) {
  if (x == L->veri) return L;
  if (x <  L->veri) return arama(x, L->solcocuk);
  return arama(x, L->sagcocuk);
}
return NULL;   /* L == NULL: boş (alt) ağaç */

Kodun sorduğu asıl soru 3. satırdadır. x kökten küçükse 3. satırdaki if bloğuna girilir ve sol alt ağaçta arama yapılır. Alt çağrı ne döndürürse yordam onu döndürür. 4. satırdaki sağ alt ağaç araması bu durumda asla yapılmaz. Sol alt ağaçta değer bulunamazsa NULL döner ve yordam sağa hiç bakmadan biter.

İkili arama ağacında bu davranış tam olarak istenendir. x kökten küçükse sağ alt ağaçta olamaz; oraya bakmak boşa iştir. Kod doğrudur ve O(h)'dir. Sıralı olmayan genel bir ikili ağaçta ise durum farklıdır. x, kökten küçük olduğu hâlde sağ alt ağaçta bulunabilir; bu kod onu kaçırır. Sürücü programda kökü 5, sol çocuğu 9, sağ çocuğu 2 olan bir ağaçta 2 arandı. 2 < 5 olduğu için arama sola gitti, 9'un solunda NULL'a ulaştı ve “yok” cevabı verdi.

Son satırdaki return NULL da dikkat ister. Sunumun özgün sürümünde bu satırın yanında “Buraya hiç girmez, ama olsun, biz yazalım da…” yorumu vardı. Yorum yanlıştı ve sunumda düzeltildi. L NULL olduğunda if bloğu atlanır ve yordam tam bu satıra gelir. Bu da her başarısız aramanın son çağrısında olur. Satır silinirse yordam boş ağaçta bir değer döndürmeden biter. Bir değer döndürmesi gereken yordamın sonuna ulaşıp o değeri kullanmak C'de tanımsız davranıştır. Derleyici bu durumda uyarı verir; çağıran ise rastgele bir adres alabilir.

Hocanın bu örnekle ilgili bir notu daha vardır: özyinelemeli kod yazılırken bazen örnekteki gibi return satırından sonra da işlem yapılır. Bu, özyinelemenin iki ayrı biçimini hatırlatır. Aramada alt çağrının sonucu olduğu gibi iletilir ve çağrıdan sonra iş kalmaz. Derinlik ya da düğüm sayısı hesaplanırken ise alt çağrıların sonuçları birleştirilir ve dönüşte hesap yapılır. Hangi biçimin gerektiği, problemin her iki alt ağaca da ihtiyaç duyup duymadığına bağlıdır.

11.3.4Her ikili ağaçta arama

Değerleri sıralı olmayan bir ikili ağaçta arama, hangi yöne gidileceğini bilemez. İki alt ağaca da bakmak gerekir. Sunumdaki örnek çözüm önce sol alt ağaca bakar; orada bulamazsa sağa geçer.

agac_gost ara_ozyineli(int veri, agac_gost L) {
  if (!L) return NULL;              /* ağaç boş mu   */
  if (L->veri == veri) return L;    /* aranan bulundu */
  agac_gost T = ara_ozyineli(veri, L->solcocuk);
  return T ? T : ara_ozyineli(veri, L->sagcocuk);
}

Yordamın ilk iki satırı özyinelemeli aramayla aynıdır. 4. satır sol alt ağaçta arar ve sonucu T'de saklar. 5. satırdaki koşullu ifade, T NULL değilse onu döndürür. Değer solda bulunduysa sağa hiç bakılmaz. Solda bulunamadıysa sağ alt ağacın aramasının sonucu döner. Sağda da yoksa bu sonuç NULL'dır.

Yordam ağacın sıralama bilgisini kullanmaz. Değer ağaçta yoksa ya da en son ziyaret edilen düğümdeyse bütün düğümlere bakılır; en kötü durum O(n)'dir. Bu yordam bir ikili arama ağacında da doğru çalışır, ama gereksiz yere yavaştır. Sürücü programda kökü 5, sol çocuğu 9, 9'un sağ çocuğu 1, kökün sağ çocuğu 2 olan genel ağaçta 2, 1 ve 7 arandı. Yordam 2'yi ve 1'i buldu, 7 için NULL döndürdü. Aynı ağaçta ikili arama ağacı yordamları 2'yi bulamadı.

Bu yordamın bellek maliyeti çağrı derinliğidir: O(h). Yordam, ağırlık bulma sınav sorusunun çözümünde de kullanılır. Hoca bu yordamlar için iddialı bir şey söyler: bunları sınıftaki herkesin gözü kapalı yazabilmesi gerekir. Sonra yumuşatır: “Hadi bir gözü açık olsun.” Söylenmek istenen şudur: arama, ekleme ve derinlik yordamları ağaç konusunun alfabesidir. Daha büyük her problem bunların birleşimiyle çözülür.

11.4Derinlik

Ağacın derinliği bütün işlemlerin maliyetini belirler. Onu hesaplayan yordam küçük olsa da öğretici bir örnektir. Problem her iki alt ağacın cevabına ihtiyaç duyar ve özyinelemeli düşünmenin en temiz örneklerinden birini verir. Bu kesim önce döngüsel bir çözümü, sonra özyinelemeli çözümü ve onun iki yanlış kullanımını ele alır.

11.4.1Döngüsel derinlik ve küresel değişken

Sunum bu konuyu bir soruyla açar: derinlik döngüsel olarak yazılsın. Hoca sınıfta görülen tipik çözümlere sert bir tepki verir. O çözümler ağacı bir yığınla gezer ve o ana kadar görülen en büyük düzeyi bir küresel değişkende (global variable) tutar. Hocaya göre bu kod çalışsa bile puan almaz. Bir öğrenci “Doğru çalışıyorsa bir puan da mı vermezsiniz?” diye sorar. Cevap kesindir: çeyrek puan bile verilmez. Neden bu kadar sert olunduğu birazdan anlatılacak. Önce küresel değişken kullanmayan döngüsel bir çözüm görülsün.

/* global değişkensiz döngüsel çözüm:
   düzey düzey gezin, düzeyleri say */
int derinlik_d(agac_gost L) {
  agac_gost k[MAX_SIZE];
  int on = 0, arka = 0, d = 0;
  if (L) k[arka++] = L;
  while (on < arka) {          /* bir düzey */
    int son = arka;
    d++;
    for (; on < son; on++) {
      if (k[on]->solcocuk) k[arka++] = k[on]->solcocuk;
      if (k[on]->sagcocuk) k[arka++] = k[on]->sagcocuk;
    }
  }
  return d;       /* MAX_SIZE >= n olmalı */
}

Çözüm ağacı düzey sırasıyla (level-order) gezer. k dizisi bir kuyruk gibi kullanılır: on sıradaki öğenin, arka ilk boş hücrenin indisidir. Kök kuyruğa konur. Dış döngünün her turu bir düzeyi işler. Tur başında son = arka ile o düzeyin sonu işaretlenir ve d bir artırılır. İç döngü, kuyruktaki o düzeyin düğümlerini sırayla alır ve çocuklarını kuyruğun arkasına ekler. Bu çocuklar bir sonraki düzeydir. Kuyruk boşaldığında bütün düzeyler sayılmıştır ve d derinliği verir. Boş ağaçta kuyruğa hiçbir şey konmaz ve d = 0 döner.

Kuyruktan alınan öğe silinmez; on yalnız ilerler. Bu yüzden dizinin, ağacın bütün düğümlerini alacak kadar büyük olması gerekir: MAX_SIZE ≥ n. Kodun son satırındaki yorum bu koşulu hatırlatır. Her düğüm kuyruğa bir kez girip bir kez çıktığı için süre O(n)'dir. Bellek ise dizinin boyu kadardır ve yığın bölgesinde (stack) durur. Sürücü programda MAX_SIZE 60 000 seçildi; 8 baytlık işaretçilerle bu, yaklaşık 470 KB eder. Windows'ta varsayılan çağrı yığını 1 MB olduğundan birkaç yüz bin düğümlük bir dizi yerel olarak tanımlanamaz. Gerçek bir programda bu dizi malloc ile ayrılmalıdır. Yordam, sunumdaki örnek ağaçlarda ve 50 000 rastgele değerle kurulmuş ağaçta özyinelemeli sürümle aynı sonucu verdi.

Hocanın küresel değişkene tepkisinin nedeni yazılımın ölçeğidir. Büyük firmalarda büyük işler birlikte yapılır. Birinin yazdığı yordamı, öbür uçtaki biri kullanır. Hoca bunu bir benzetmeyle anlatır: kullanan kişi yordamı yazanı tanımaz, belki o başka bir ülkededir. Telefonu açıp “Senin bir max değişkenin var, bu ne oluyor?” diye soramaz. Küresel değişken kullanan bir yordamın üç sorunu vardır.

• Gizli durum. Yordamın sonucu yalnız parametrelerine değil, küresel değişkenin o anki değerine de bağlıdır. Değişken bir önceki çağrıdan kalma bir değer taşıyorsa ikinci çağrı yanlış sonuç verir. Kullanan, her çağrıdan önce değişkeni sıfırlamak gerektiğini bilmek zorunda kalır.
• Ad çakışması. İki ayrı dosyada aynı adla küresel değişken tanımlanırsa bağlayıcı hata verir ya da, daha kötüsü, iki değişkeni sessizce birleştirir.
• Yeniden girilemezlik. Yordam aynı anda iki ağaç için çalıştırılamaz. İki iş parçacığı aynı küresel değişkeni bozar; yordam kendini başka bir ağaç için özyinelemeli olarak da çağıramaz.

Sunum bu tartışmadan üç ilke çıkarır. Birincisi, yordam kendi içinde tam olmalıdır: girdisini parametreden alır, çıktısını dönüş değeriyle verir ve gizli bir durum tutmaz. İkincisi, bir yordamın içinde başka bir yordamın yerel prototipi bildirilebilir. Bu yalnız adı o yordamın içinde görünür kılar; tanım dışarıda kalır. Standart C iç içe yordam tanımına izin vermez. Bu teknik ağırlık bulma sınav sorusunun çözümünde kullanılır. Üçüncüsü, özyinelemeli çözümde her çağrının kendi yerel sol ve sağ değişkeni vardır; küresel bir sayaca hiç gerek kalmaz.

11.4.2Özyinelemeli derinlik

Derinliğin özyinelemeli tanımı tek cümledir. Boş ağacın derinliği 0'dır. Boş olmayan bir ağacın derinliği, sol ve sağ alt ağaçlarından derin olanının derinliğinden 1 fazladır: derinlik(L) = MAX(derinlik(sol), derinlik(sağ)) + 1. Eklenen 1 kökün kendisidir. Kod bu tanımı birebir izler.

int derinlik(agac_gost L) {
  int sol, sag;
  if (L) {                   // işaretçi NULL mı
    sol = derinlik(L->solcocuk);
    sag = derinlik(L->sagcocuk);
    return MAX(sol, sag) + 1;
  }
  else return 0;             // uç yaprağa ulaşıldı
}

2. satırdaki iki yerel değişken, alt ağaçların derinliklerini saklar. 3. satır problemin yeterince küçülüp küçülmediğini sorar. Hoca bu soruyu özellikle vurgular: “Problem yeterince küçüldü mü? Başta da NULL gelebilir!” NULL denetimi yalnız yaprakların altındaki boş çocuklar için değildir; ilk çağrıda ağacın kendisi de boş olabilir. 4. ve 5. satırlar iki alt ağacın derinliğini hesaplar. 6. satır büyüğünü alır ve 1 ekler. 8. satır boş ağaç için 0 döndürür.

Sunumdaki MAX bir makrodur: #define MAX(a,b) ((a) > (b) ? (a) : (b)). Buradaki argümanlar yalnız birer yerel değişkendir; makronun bir argümanı iki kez değerlendirmesi zarar vermez. Aynı makronun tek satırlık sürümde neden tehlikeli olduğu bir sonraki kesimin konusudur.

Sunum yordamı altı düğümlü bir ağaçta izler. A köktür; solunda B, sağında C vardır. B'nin solunda D, C'nin solunda E, E'nin solunda F bulunur. Tablo 11.4 her çerçevenin {sol, sağ} değerlerini ve dönüşünü verir.

Çağrılar önce sol kolu izler. derinlik(A), derinlik(B)'yi; o da derinlik(D)'yi çağırır. D'nin iki çocuğu da NULL'dır; iki alt çağrı 0 döndürür ve D 1 döndürür. B'nin sağ çocuğu yoktur; B MAX(1, 0) + 1 = 2 döndürür. A'nın sol değişkeni 2 olur ve şimdi sağ alt ağaç için derinlik(C) çağrılır. C'den E'ye, E'den F'ye inilir. F 1, E 2, C 3 döndürür. Son olarak A, MAX(2, 3) + 1 = 4 döndürür. Sürücü program aynı ağaçta 4 sonucunu verdi.

Şekil 11.7 çerçevelerin bir özelliğini gösterir. Her düğümün kendi iki yerel değişkeni vardır: sol ve sağ derinlik. Bir çerçeve bitince yerel değişkenleri de yok olur. NULL ile yapılan çağrılar yerel değişkenlerini hiç kullanmadan siler. Yığında aynı anda yalnız kökten o anki düğüme giden yoldaki çerçeveler bulunur; en çok h + 1 çerçeve.

Maliyet analizi şöyledir. Her düğüm için bir çağrı yapılır. Ayrıca her NULL çocuk için de bir çağrı yapılır. n düğümlü bir ikili ağaçta n + 1 boş çocuk işaretçisi bulunur: toplam 2n işaretçinin n − 1'i bir düğümü gösterir, kalanı NULL'dır. Çağrı sayısı tam olarak 2n + 1'dir. Sürücü programda bu sayı 1'den 24'e kadar her zincir uzunluğunda ve 262 143 düğüme kadar dolu ağaçlarda sayaçla doğrulandı. Her çağrı sabit iş yaptığı için zaman Θ(n)'dir. Derinliği bulmak için her düğüme bakmak zorunludur; hiçbir yordam bundan hızlı olamaz. Bellek, çağrı derinliği kadardır: O(h).

11.4.3Tek satırlık sürüm ve makro tuzağı

Aynı yordam yerel değişkenler kullanılmadan tek bir ifadeyle de yazılabilir. Sunum bu sürümü “profesyonelce” bir yazım olarak sunar, ardından içindeki tuzağı gösterir.

int derinlik(agac_gost L) {    /* tek satır */
  return !L ? 0 : MAX(derinlik(L->solcocuk),
                      derinlik(L->sagcocuk)) + 1;
}

Kod okunaklı ve doğru sonuç verir. Ama MAX bir fonksiyon değil, bir makrodur (macro). Önişlemci derlemeden önce MAX(a, b)'yi metin olarak ((a) > (b) ? (a) : (b)) ile değiştirir. Burada a ve b birer yordam çağrısıdır. Açılmış ifade önce iki çağrıyı da karşılaştırma için işletir. Sonra büyük olanı döndürmek için o çağrıyı bir kez daha işletir. Her düğümde alt ağaçlardan biri iki kez hesaplanır.

Çarpık bir ağaçta bunun bedeli üsteldir. Sağa uzanan bir zincirde her düğümün sol çocuğu NULL'dır. Sağ alt ağacın derinliği daha büyük olduğu için sağ çağrı iki kez yapılır. n düğümlü zincirde çağrı sayısı T(n) ise T(n) = 2T(n − 1) + 2 olur. Buradaki 2, düğümün kendi çağrısı ile NULL sol çocuğun çağrısıdır. Çözüm T(n) = 3 · 2ⁿ − 2'dir. Sola uzanan zincirde de durum aynıdır. Orada sağ çocuk NULL'dır, sol çağrı büyük çıkar ve iki kez yapılır. Dolu ve dengeli bir ağaçta iki alt ağacın derinliği eşittir. Karşılaştırma yanlış çıkar ve sağ alt ağaç yeniden hesaplanır. Bu kez T(n) ≈ 3T(n/2) olur ve çözüm Θ(n^{lg 3}) ≈ Θ(n^1,585)'tir. Yani dengeli ağaçta bile süre doğrusal değildir.

Tablo 11.5 farkı sayılarla gösterir. 24 düğümlük bir zincirde iki yordam aynı sonucu (24) verir. Biri 49, öteki elli milyonu aşkın çağrı yapar. Her yeni düğüm makrolu sürümün çağrı sayısını ikiye katlar. 40 düğümlük bir zincirde sayı 3 · 2⁴⁰'ı, yani üç trilyonu aşar. Ölçülen bütün değerler 3 · 2ⁿ − 2 formülüne tam uyar. Dolu ağaçlarda makrolu sürüm (3^k+1 − 1)/2 çağrı yapar; burada k düzey sayısıdır.

Çözüm, makro yerine gerçek bir fonksiyon kullanmaktır. Fonksiyon argümanlarını çağrıdan önce bir kez değerlendirir ve değerleri kopyalar. Ağırlık bulma sınav sorusunun çözümü bu yolu izler:

int max(int a, int b) { return a > b ? a : b; }

Bu fonksiyonla yazılan tek satırlık derinlik yordamı, sürücü programda her ağaçta tam 2n + 1 çağrı yaptı. İkinci çözüm yerel değişkenli sürümdür. Değerler önce değişkenlere alınır; makro artık yalnız değişkenleri karşılaştırır.

Sunumda bu kesimin yanında hocanın bir gözlemi daha yer alır. Hocaya göre özyinelemeli düşünmeyi ve özyinelemeli bağıntıları çözmeyi mühendislere kabul ettirmek zordur. Döngüyle düşünmeye alışmış biri, “Ne güzel kod yazıyorum” der ve yeni bir düşünce tarzına direnir. Derinlik örneği bu direncin neden yersiz olduğunu gösterir. Döngüsel çözüm bir kuyruk, bir boyut sınırı ve iki iç içe döngü ister. Özyinelemeli çözüm ise tanımın kendisidir ve dört satıra sığar.

11.4.4Ek parametre koymak

Sunum bu kesimi A. J. Perlis'in bilinen bir sözüyle açar. Söz kabaca şöyle der: on parametreli bir yordamınız varsa, büyük olasılıkla birkaçını unutmuşsunuzdur. Şaka, parametre listesinin şişmesinin bir tasarım hatası belirtisi olduğunu anlatır.

Bir öğrenci şunu sorar: int derinlik(agac_gost L, int a) biçiminde fazladan bir parametre eklense ve yordam derinlik(L, 0) diye çağrılsa olur mu? Öğrencinin aklındaki çözüm muhtemelen şudur. a o ana kadar inilen düzeyi taşır, her alt çağrıya a + 1 geçirilir ve NULL'a gelindiğinde a döndürülür. Kod çalışabilir. Ama hoca bu tasarımı kabul etmez. Fazladan parametre neden tanımlanıyor ve ilk çağrıda neden sıfır geçiriliyor? Yordamı kullanana ne denecek: “a'ya sıfır geçirmeyi sakın ha unutma!” mı? Hoca bunu bir örnekle somutlaştırır: 0 geçirilince sıralayan, 1 geçirilince sıralayamayan bir sıralama yordamı olur mu?

Sorun, parametrenin bir girdi değil, yordamın iç işleyişine ait bir başlangıç değeri olmasıdır. Kullanıcıya bir yükümlülük yükler ve bu yükümlülük unutulduğunda yordam sessizce yanlış sonuç verir. Gerekirse böyle bir ek parametre, dışarıya açılmayan bir yardımcı yordamda tutulur. Kullanıcıya açılan yordam yalnız L'yi alır ve yardımcıyı doğru başlangıç değeriyle kendisi çağırır.

Her ek parametre de kötü değildir. Sıralama yordamına küçükten büyüğe mi büyükten küçüğe mi sıralanacağını bildiren bir parametre (−1/+1 ya da '<'/'>') verilebilir. Verinin türünü bildiren bir parametre de verilebilir. Bu parametreler yordamın davranışını seçer. Her değerleri anlamlıdır ve kullanıcı bilerek seçim yapar. İlke şudur: parametre davranışı seçmeli, gizli bir başlangıç değeri taşımamalıdır.

11.5Silme

Silme, ikili arama ağacının en ince işlemidir. Ekleme her zaman bir yaprağın altına yapılır ve yalnız bir NULL işaretçiyi değiştirir. Silinecek düğüm ise ağacın herhangi bir yerinde, örneğin kökte olabilir. Düğüm çıkarıldıktan sonra kalan düğümler yeniden bağlanmalı ve ağaç yine tanıma uymalıdır. Silerken ağacın ikili arama ağacı özelliği bozulmamalıdır.

11.5.1Üç durum

Silinecek düğümün çocuk sayısına göre üç durum vardır.

• Çocuksuz düğüm (yaprak). Ebeveynin bu düğümü gösteren işaretçisi NULL yapılır ve düğüm free edilir. Ağacın geri kalanı etkilenmez.
• Tek çocuklu düğüm. Ebeveynin işaretçisi, silinen düğümün tek çocuğunu gösterecek biçimde değiştirilir. Çocuğun alt ağacı bütünüyle bir düzey yukarı çıkar. Bu, sıralamayı bozmaz. Silinen düğüm ebeveyninin solundaysa, onun alt ağacındaki her değer ebeveynden küçüktür. Alt ağaç yukarı çıktığında yine ebeveynin solunda kalır.
• İki çocuklu düğüm. Ebeveynin tek işaretçisi iki alt ağacı birden gösteremez. Silinen düğümün yerine, iki alt ağacın arasına sığan bir değer konmalıdır. Bunun için farklı yöntemler vardır.

Sunum iki çocuklu durumu bir örnek ağaç üzerinde inceler. Ağaca 40, 20, 60, 10, 30, 50, 70, 42, 55, 65, 73, 52, 57, 66, 56 değerleri bu sırayla eklenmiştir. Ağacın derinliği 6'dır; en uzun yol 40 → 60 → 50 → 55 → 57 → 56'dır. Silinecek düğüm 60'tır. 60'ın iki çocuğu vardır: 50 ve 70. Her ikisinin de altında kalabalık birer alt ağaç bulunur.

11.5.2İki çocuklu düğüm: sol alt ağacın en büyüğü

60'ın yerine hangi değer gelebilir? Yeni değer, sol alt ağaçtaki her değerden büyük, sağ alt ağaçtaki her değerden küçük olmalıdır. İki aday vardır. Birincisi sol alt ağacın en büyük değeridir. Bu değer, kök ortada sırada 60'tan hemen önce gelir; ona 60'ın öncülü (predecessor) denir. Sunumda bu değer için “öncül” sözcüğü de geçer. İkincisi sağ alt ağacın en küçük değeridir. Bu değer kök ortada sırada 60'tan hemen sonra gelir ve 60'ın ardılıdır (successor). İkisi de 60'ın yerine konduğunda sıralama korunur. Sunumun birinci yöntemi öncülü kullanır.

Sol alt ağaçtaki en büyük değer nasıl bulunur? Bir alt ağaçta her sağ çocuk ebeveyninden büyüktür. Bu yüzden en büyük değer, alt ağacın kökünden başlayıp sağ işaretçiler üzerinden ilerleyerek bulunur. Sağ çocuğu olmayan ilk düğüm en büyüktür. Örnekte 60'ın sol alt ağacının kökü 50'dir. 50'den sağa 55'e, 55'ten sağa 57'ye gidilir. 57'nin sağ çocuğu yoktur; sol alt ağacın en büyüğü 57'dir.

En büyük öğenin sağ çocuğu yoktur, ama bir sol alt ağacı olabilir. Örnekte 57'nin solunda 56 durur. 57 yerinden alınırken bu sol çocuk unutulmamalıdır. 56, 57'nin ebeveyni olan 55'in sağ bağına aktarılır. Bu güvenlidir: 56, 55'in sağ alt ağacındaydı ve 55'ten büyüktür.

Taşıma iki yolla yapılabilir. Birinci yolda 57'nin düğümü fiziksel olarak 60'ın yerine taşınır. Bunun için dört bağ değişir: 40'ın sağ bağı 57'yi, 55'in sağ bağı 56'yı, 57'nin sol bağı 50'yi, 57'nin sağ bağı 70'i gösterir. İkinci yolda 60'ın düğümü free edilmez. Yalnız veri alanına 57 yazılır. Sonra eski 57 düğümü, tek çocuklu bir düğüm gibi silinir. 55'in sağ bağı 56'ya güncellenir ve bu tek bağ değişikliği yeter. İkinci yol daha kısadır ve sunumdaki kod bu yolu izler. Düğümde veriden başka büyük alanlar varsa veri kopyalamak pahalı olabilir. O durumda birinci yol tercih edilir.

11.5.3Silme yordamı ve işaretçinin işaretçisi

Silme yordamı da ağacı agac_gost *L olarak alır. Silinen düğüm kökse çağıranın kök işaretçisi değişmelidir. Ama yordamın asıl inceliği, yalnız kök için değil, ağacın her bağı için aynı fikri kullanmasıdır.

void sil(int x, agac_gost *L) {
  agac_gost p = *L, *bag = L;  // bag: p'ye giden
  while (p && p->veri != x) {  // x'i ara
    bag = (x < p->veri) ? &p->solcocuk
                        : &p->sagcocuk;
    p = *bag;
  }
  if (!p) return;              // x yok
  if (p->solcocuk && p->sagcocuk) {  // 2 çocuk
    agac_gost *b = &p->solcocuk;     // sol alt
    while ((*b)->sagcocuk)           // ağacın en
      b = &(*b)->sagcocuk;           // büyüğü
    p->veri = (*b)->veri;      // veriyi taşı
    bag = b;  p = *b;          // onu sileceğiz
  }
  *bag = p->solcocuk ? p->solcocuk : p->sagcocuk;
  free(p);
}

Yordamın merkezinde bag değişkeni durur. Tipi agac_gost *, yani işaretçiye işaretçidir. bag, o an incelenen p düğümünü gösteren işaretçinin adresini tutar. Bu işaretçi ya çağıranın kök değişkenidir ya da bir ebeveynin solcocuk veya sagcocuk alanıdır. *bag'e yazmak, p'ye giden bağı değiştirir. Böylece ebeveynin kim olduğunu ve p'nin onun hangi çocuğu olduğunu ayrıca tutmaya gerek kalmaz. Ekleme yordamındaki q işaretçisi ve son satırdaki “sol mu, sağ mı?” sorusu burada tek bir değişkende birleşmiştir.

• 2. satır. p kökü, bag ise kök işaretçisinin adresini (L) tutar. Başta *bag == p'dir.
• 3.–7. satırlar. x aranır. Her adımda önce bag, p'nin sol ya da sağ alanının adresine çevrilir. Sonra p = *bag ile bir düzey inilir. Döngü bitince ya p NULL'dır ya da p->veri == x'tir. Her iki durumda da *bag == p eşitliği korunur.
• 8. satır. x ağaçta yoksa yordam hiçbir şey yapmadan döner.
• 9.–15. satırlar. İki çocuk varsa sol alt ağacın en büyüğü aranır. b da bir işaretçinin adresidir. Başta 60'ın sol alanını gösterir; (*b)->sagcocuk NULL olana kadar sağ alanlara ilerler. Döngü bitince *b en büyük düğümdür ve b, bu düğümü gösteren bağın adresidir. 13. satır en büyük değeri silinecek düğümün veri alanına kopyalar. 14. satırla silinecek düğüm değişir: artık eski en büyük düğüm silinecektir ve ona giden bağ b'dir. Bu düğümün sağ çocuğu olmadığından en çok bir çocuğu vardır.
• 16. satır. Bu noktada p'nin en çok bir çocuğu vardır. Bağ, varsa sol çocuğa, yoksa sağ çocuğa çevrilir. İki çocuk da yoksa sağ çocuk NULL'dır ve bağ NULL olur. Yaprak, tek çocuk ve iki çocuğun ikinci aşaması aynı satırla çözülür.
• 17. satır. Ağaçtan ayrılmış düğüm free edilir.

Sonuncudan önceki satırın sırası önemlidir. Önce *bag güncellenir, sonra p serbest bırakılır. Sıra ters olsaydı 16. satır serbest bırakılmış bir düğümün alanlarını okurdu. Bir başka ayrıntı da 11. satırdaki (*b)->sagcocuk yazımıdır. Parantez gereklidir, çünkü -> işleci *'dan önce uygulanır. *b->sagcocuk yazılsaydı derleyici b'yi bir yapı işaretçisi sayardı ve kod derlenmezdi.

Yordam silinen değeri bulamazsa sessizce döner. Silme sonrasında düğüm sayısı bir azalır. Sürücü programda bu da denetlendi: her silmede free sayacı bir arttı, malloc sayacı değişmedi. Örnek ağaçtaki 15 değerin hepsi tek tek silindiğinde kök işaretçisi NULL oldu. 2000 rastgele değerli bir ağaçtan bütün değerler rastgele sırayla silindi. Her silmeden sonra ağacın hâlâ ikili arama ağacı olduğu denetlendi ve sonunda malloc ile free sayıları eşit çıktı.

11.5.4Kod izleme: 60'ı silmek

Tablo 11.6 sil(60, &L) çağrısını adım adım izler. bag ve b adresleri “&40->sagcocuk” biçiminde, yani gösterdikleri alanla yazıldı.

Silmeden sonra ağaç 40(20(10, 30), 57(50(42, 55(52, 56)), 70(65(−, 66), 73))) biçimindedir. Kök ortada gezinme 10 20 30 40 42 50 52 55 56 57 65 66 70 73'tür ve hâlâ sıralıdır. Sürücü program bu ağacı ve derinliğin 5 olduğunu doğruladı.

Silme yordamının maliyeti iki yolun toplamıdır: silinecek düğüme inen yol ve oradan en büyük öğeye inen yol. Bu ikisi birlikte kökten bir yaprağa giden tek bir yoldan uzun olamaz. Toplam O(h)'dir: dengeli ağaçta O(lg n), çarpık ağaçta O(n). Yordam döngüseldir ve ek bellek olarak birkaç işaretçi kullanır: O(1).

11.5.5Dört yöntem ve derinliğe etkisi

Sunum iki çocuklu silme için dört yöntemi karşılaştırır. İlk ikisi silinen değerin yerine bir değer koyar, son ikisi bir alt ağacı yukarı taşır.

1. Sol alt ağacın en büyüğü. Önceki kesimde anlatılan yöntemdir. 57 yukarı çıkar, 56 55'in sağına bağlanır. Derinlik 5'e iner.
2. Sağ alt ağacın en küçüğü. Ayna yöntemidir. 60'ın sağ alt ağacında sürekli sola gidilir: 70 → 65. 65'in solu yoktur; en küçük 65'tir. 60'ın yerine 65 yazılır. 65'in sağ çocuğu 66, 70'in soluna bağlanır. 50'nin altındaki uzun kol yerinde kaldığı için derinlik 6 olarak kalır.
3. Sağ çocuk yukarı. Silinen düğümün yerine sağ çocuğu (70) kayar. Sol alt ağacın (50'nin alt ağacı) asılacak bir yere ihtiyacı vardır. 50'deki her değer 70'in alt ağacındaki her değerden küçüktür. Bu yüzden 50 alt ağacı, 70 alt ağacının en küçüğünün (65) soluna asılır. Derinlik 7'ye çıkar.
4. Sol çocuk yukarı. Üçüncünün aynasıdır. Yerine sol çocuk (50) kayar. 70 alt ağacı, 50 alt ağacının en büyüğünün (57) sağına asılır. 40 → 50 → 55 → 57 → 70 → 65 → 66 yolu yedi düğüm uzunluğundadır; derinlik 7'dir.

Dört sonucun hepsi geçerli ikili arama ağacıdır. Sürücü programda dördü de ayrı ayrı uygulandı. Her birinde kök ortada gezinme aynı sıralı diziyi verdi. Derinlikler sırasıyla 5, 6, 7 ve 7 çıktı. Aralarındaki fark, ağacın biçiminde ve dolayısıyla sonraki aramaların maliyetindedir. Son iki yöntem bir alt ağacı başka bir alt ağacın en altına astığı için derinliği büyütür. İlk iki yöntem yalnız tek bir düğümü yukarı alır ve derinliği artırmaz. Hoca bu yüzden şu ilkeyi önerir: silinen öğenin kök olduğu ağaç olabildiğince dengeli kalacak biçimde silinmelidir. Pratikte ilk iki yöntem kullanılır. Bazı gerçeklemeler, sürekli aynı yanı kullanmanın ağacı zamanla bir yana yatırmaması için ikisi arasında sırayla geçiş yapar.

İkinci yöntemin kodu birinci yöntemin aynasıdır: sol yerine sağ alt ağaca geçilir ve sağ yerine sol işaretçiler izlenir.

void sil_sag(int x, agac_gost *L) {    /* 2. yöntem */
  agac_gost p = *L, *bag = L;
  while (p && p->veri != x) {
    bag = (x < p->veri) ? &p->solcocuk
                        : &p->sagcocuk;
    p = *bag;
  }
  if (!p) return;
  if (p->solcocuk && p->sagcocuk) {    // 2 çocuk
    agac_gost *b = &p->sagcocuk;       // sağ alt
    while ((*b)->solcocuk)             // ağacın en
      b = &(*b)->solcocuk;             // küçüğü
    p->veri = (*b)->veri;
    bag = b;  p = *b;
  }
  *bag = p->solcocuk ? p->solcocuk : p->sagcocuk;
  free(p);
}

Son satırdaki ifade her iki yöntemde de aynıdır. Sağ alt ağacın en küçüğünün sol çocuğu yoktur. Bu yüzden ifade onu bağın yerine sağ çocuğuna çevirir. Örnekte 70'in sol bağı 66'yı gösterir.

11.6Dengeli ağaçlar

Önceki kesimlerdeki her işlemin maliyeti O(h) idi. Bu kesim h'nin ne kadar büyüyebileceğini sayılarla gösterir. Ardından yüksekliği her durumda O(lg n) tutan AVL ağacını ayrıntılı anlatır. Kırmızı-siyah ağaç ile B-ağacına da kısaca değinir.

11.6.1Dengesizliğin maliyeti

Tablo 11.7, n değerli bir ağacın en iyi ve en kötü durumdaki derinliğini karşılaştırır. Dengeli ağacın derinliği ⌈lg(n + 1)⌉, çarpık ağacınki n'dir.

Tablodaki fark çarpıcıdır. Hoca bunu tek cümleyle özetler: O(n) ile O(lg n) arasındaki fark, 2 000 000 ile 21 arasındaki fark gibidir. Bir milyar kayıtlık bir dizinde dengeli ağaç bir kaydı 30 adımda bulur. Çarpık ağaç ise en kötü durumda bir milyar adım atar.

Rastgele sırada gelen veride durum o kadar kötü değildir. Değerlerin her sırası eşit olasılıklı olduğunda n değerli bir ağacın ortalama derinliği Θ(lg n)'dir. Başarılı bir aramanın ortalama karşılaştırma sayısı yaklaşık 2 ln n ≈ 1,39 lg n'dir. Sürücü programda bu iddia ölçüldü. 1000, 10 000, 100 000 ve 1 000 000 rastgele değer boş ağaçlara eklendi ve düğümlerin ortalama düzeyi hesaplandı. Sonuçlar 12,1; 16,7; 21,0 ve 25,2 çıktı. Kesin formül 2(1 + 1/n)H_n − 3 aynı boyutlar için 12,0; 16,6; 21,2 ve 25,8 verir. Buradaki H_n, 1 + 1/2 + … + 1/n toplamıdır. Ölçümler formüle çok yakındır. 1,39 lg n değeri ise bu formülün baş terimidir ve her boyutta ölçülenden yaklaşık iki fazladır. Ağacın en derin yolu daha uzundu: bir milyon değerde ortalama 47,7 düzey. Bu da lg n ≈ 20'nin iki katından biraz fazladır.

Ortalama durumun iyi olması güvence vermez. En kötü durum sıralı ya da neredeyse sıralı veridir ve gerçekte sık görülür. Bu yüzden her ekleme ve silmeden sonra yerel döndürmelerle derinliği O(lg n)'de tutan ağaçlar geliştirilmiştir. AVL ağacı, kırmızı-siyah ağaç ve B-ağacı bunların en bilinenleridir.

11.6.2AVL ağacı

AVL ağacı, kendini dengeleyen ilk ikili arama ağacıdır. Adı, 1962'de yapıyı yayımlayan G. M. Adelson-Velski ile E. M. Landis'in baş harflerinden gelir. Bu kesimde bir düğümün yüksekliği, o düğümün kök olduğu alt ağacın derinliğidir. Yaprağın yüksekliği 1, boş ağacınki 0'dır. Kodda bu değer yuk adıyla geçer.

Koşul her düğümde, yalnız kökte değil, sağlanmalıdır. Denge faktörü +1 olan düğüm sola, −1 olan düğüm sağa biraz ağırdır; 0 olan düğüm tam dengelidir. Koşulun ne kadar güçlü olduğunu aşağıdaki teorem gösterir.

Kanıt taslağı. Yüksekliği h olan bir AVL ağacının en az kaç düğümü olabileceğine bakılsın; bu sayı N(h) olsun. N(1) = 1 ve N(2) = 2'dir. Yüksekliği h olan en seyrek ağacın bir alt ağacının yüksekliği h − 1 olmalıdır. Öteki alt ağacın yüksekliği, denge koşulu yüzünden en az h − 2'dir. İki alt ağaç da en seyrek biçimde seçilirse N(h) = N(h − 1) + N(h − 2) + 1 bulunur. Bu bağıntı Fibonacci sayılarınınkine benzer. N(h) + 1 değerleri Fibonacci dizisini izler: 2, 3, 5, 8, 13, … Fibonacci sayıları φ^h hızıyla büyür; burada φ = (1 + √5)/2 ≈ 1,618'dir. Öyleyse n ≥ N(h) ≈ φ^h, yani h ≤ log_φ n = lg n / lg φ ≈ 1,44 lg n çıkar. Kesin hesap küçük düzeltmelerle 1,44 lg(n + 2) sınırını verir. ∎

Sürücü programda N(h) hesaplandı: N(5) = 12, N(10) = 143, N(20) = 17 710, N(30) = 2 178 308. Yani yüksekliği 30 olan bir AVL ağacında en az iki milyondan fazla düğüm bulunur. İki milyon düğümlü bir AVL ağacı en kötü durumda 30 düzeylidir, oysa çarpık bir ağaç iki milyon düzeyli olabilir.

Sunumdaki AVL düğümü, sıradan düğüme bir yükseklik alanı ekler. İki yardımcı yordam yükseklik ve denge faktörü hesabını kısaltır.

typedef struct avl *avl_gost;
struct avl {
    int      veri;
    int      yuk;        /* alt ağaç yüksekliği */
    avl_gost sol, sag;
};
int yuk(avl_gost t) { return t ? t->yuk : 0; }
int denge(avl_gost t) {
    return yuk(t->sol) - yuk(t->sag);
}

yuk yordamı boş ağaç için 0 döndürür. Bu sayede çağıran, alt ağacın NULL olup olmadığını ayrıca denetlemez. denge yordamı tanımdaki farkı hesaplar; t'nin boş olmadığını varsayar. Yükseklik her düğümde saklandığı için denge faktörü O(1)'de bulunur. Yükseklik saklanmasaydı her denetimde alt ağaçların derinliği yeniden hesaplanır ve her işlem O(n) olurdu. Düğüm boyutu değişmez: int veri ve int yükseklik birlikte 8 bayt tutar, iki işaretçiyle toplam 24 bayt eder. Sıradan düğümdeki 4 baytlık hizalama boşluğu burada yükseklik alanına gider.

Eklemenin genel planı şöyledir. Ekleme önce sıradan ikili arama ağacı eklemesiyle yapılır. Sonra eklenen düğümden köke doğru yol üzerindeki yükseklikler ve denge faktörleri güncellenir. Faktörü ±2 olan ilk ata bulunursa ağaç o atada yerel bir döndürmeyle düzeltilir. Yeni düğümün o atanın hangi torununda olduğuna göre dört durum vardır: LL, RR, LR ve RL. LL ve RR tek döndürmeyle, LR ve RL çift döndürmeyle düzelir.

11.6.3Tek döndürme: LL ve RR

Döndürme (rotation), ağacın sıralamasını koruyarak yerel yapısını değiştiren bir işlemdir. Sunum şekillerinde z dengesi bozulan ilk atadır. y onun çocuğu, x ise torunudur. T1–T4 üçgenleri, yükseklikleri belli birer alt ağaçtır.

LL durumu. Yeni düğüm z'nin sol çocuğunun (y) sol alt ağacına girmiştir. z'nin faktörü +2'ye çıkar. Düzeltmek için z sağa döndürülür. y yukarı çıkar ve z onun sağ çocuğu olur. y'nin sağ alt ağacı T3, z'nin soluna geçer. Bu geçiş güvenlidir: T3'teki değerler y'den büyük ve z'den küçüktür. Kök ortada sıra döndürmeden önce ve sonra aynıdır: T1 x T2 y T3 z T4.

RR durumu LL'nin aynasıdır. Yeni düğüm z'nin sağ çocuğunun sağ alt ağacına girmiştir ve z'nin faktörü −2'dir. z sola döndürülür; y'nin sol alt ağacı T2, z'nin sağına geçer.

Her iki durumda da döndürme sonrasında alt ağacın yüksekliği eklemeden önceki değerine döner. LL için bu şöyle gösterilir. Eklemeden önce x'in alt ağacının yüksekliği k olsun. z dengeli olduğuna ve ekleme onu +2'ye çıkardığına göre, eklemeden önce T3'ün yüksekliği k, y'ninki k + 1, T4'ünki k'dir. Alt ağacın yüksekliği k + 2'dir. Ekleme x'in alt ağacını k + 1'e, y'yi k + 2'ye çıkarır. Döndürmeden sonra z'nin iki alt ağacı T3 ve T4'tür. İkisinin yüksekliği de k olduğu için z'nin yüksekliği k + 1 olur. y'nin altında yüksekliği k + 1 olan iki alt ağaç vardır: x'in alt ağacı ve z. Böylece y'nin yüksekliği k + 2 olur. Alt ağacın yüksekliği eklemeden önceki gibidir. Bu yüzden yukarıdaki ataların faktörleri değişmez ve eklemede tek bir döndürme yeter.

11.6.4Çift döndürme: LR ve RL

LR durumu. Yeni düğüm z'nin sol çocuğunun (y) sağ alt ağacına, yani x'in altına girmiştir. Burada tek bir sağa döndürme işe yaramaz. z sağa döndürülseydi, ağır olan x alt ağacı z'nin soluna geçerdi ve dengesizlik bu kez öteki yana kayardı. Çözüm iki adımdır. Önce y sola döndürülür. x, y'nin yerine çıkar ve durum LL biçimine dönüşür. Sonra z sağa döndürülür. Torun x, iki atasının üstüne çıkar. y onun solunda, z sağında yer alır. x'in eski alt ağaçlarından T2 y'nin sağına, T3 z'nin soluna geçer. İki tek döndürmeden oluşan bu işleme çift döndürme (double rotation) denir.

RL durumu LR'nin aynasıdır. Yeni düğüm z'nin sağ çocuğunun sol alt ağacındadır. Önce sağ çocuk sağa, sonra z sola döndürülür. LR ile RL'nin sonucunda x üç düğümün ortancasıdır; bu yüzden köke o çıkar. Dört durumun hepsinde sonuç aynı biçimdedir: üç düğümden ortanca değerli olan kök, küçüğü sol, büyüğü sağ çocuk olur; dört alt ağaç sırayla altlarına dağılır.

11.6.5Döndürme kodu ve izlemesi

Sağa döndürme kodu yalnız iki işaretçi değiştirir ve iki yüksekliği yeniden hesaplar. Sunumdaki adlandırma, Weiss'in kitabındaki gibi k1 ve k2'dir: k2 dengesi bozulan düğüm, k1 onun sol çocuğudur.

avl_gost sag_dondur(avl_gost k2) {  // LL
  avl_gost k1 = k2->sol;
  k2->sol = k1->sag;
  k1->sag = k2;
  k2->yuk = 1 + MAX(yuk(k2->sol), yuk(k2->sag));
  k1->yuk = 1 + MAX(yuk(k1->sol), k2->yuk);
  return k1;                       // yeni kök
}

• 2. satır. k1, k2'nin sol çocuğudur ve yeni kök olacaktır.
• 3. satır. k1'in sağ alt ağacı k2'nin soluna geçer. Bu, şekildeki T3'ün geçişidir.
• 4. satır. k2, k1'in sağ çocuğu olur.
• 5.–6. satırlar. Yükseklikler aşağıdan yukarı güncellenir. Önce k2'nin, sonra k1'in yüksekliği hesaplanır. k1'in yeni sağ çocuğu k2'dir ve onun yüksekliği bir önceki satırda bulunmuştur. Sıra tersine çevrilirse k1 eski, yanlış bir değeri kullanır.
• 7. satır. Yeni kök döner. Çağıran, ebeveynin işaretçisini bu düğüme bağlar.

Sunum yordamı küçük bir örnekle izler. Ağaçta 30 köktür; solunda 20, sağında 40 vardır. 20'nin çocukları 10 ve 25'tir. 5 eklenince 10'un soluna girer. 30'un faktörü yük(20) − yük(40) = 3 − 1 = +2 olur. Yeni değer solun solundadır; durum LL'dir ve sag_dondur(30) çağrılır.

Döndürmeden sonra alt ağacın yüksekliği 3'tür; 5 eklenmeden önce de 3 idi. Yalnız iki işaretçi değişti. Döndürme sabit sayıda işlem yapar ve maliyeti O(1)'dir. Sürücü programda aynı ekleme dizisi (30, 20, 40, 10, 25, 5) uygulandı. Tek döndürme sag_dondur(30) oldu ve sonuç ağacı tablodaki gibi çıktı.

Sunum sola döndürmenin kodunu vermez, ama AVL ekleme kodu onu kullanır. Sola döndürme sağa döndürmenin aynasıdır: sol ile sag yer değiştirir. Sürücü programlarda kullanılan sürüm ve yeni AVL düğümü ayıran yordam aşağıdadır.

avl_gost sol_dondur(avl_gost k1) {  // RR
  avl_gost k2 = k1->sag;
  k1->sag = k2->sol;
  k2->sol = k1;
  k1->yuk = 1 + MAX(yuk(k1->sol), yuk(k1->sag));
  k2->yuk = 1 + MAX(k1->yuk, yuk(k2->sag));
  return k2;                       // yeni kök
}
avl_gost yeni_avl(int x) {
  avl_gost t = malloc(sizeof *t);
  if (!t) { fprintf(stderr, "Bellek yetersiz\n"); exit(EXIT_FAILURE); }
  t->veri = x;  t->yuk = 1;
  t->sol = t->sag = NULL;
  return t;
}

11.6.6AVL ağacına ekleme

Sunum, Weiss'in kitabındaki örneği izler. Boş bir AVL ağacına sırasıyla 3, 2, 1, 4, 5, 6, 7, 16, 15 eklenir. Tablo 11.9 her eklemeden sonraki durumu verir.

Tablodaki üç adım ayrıca açıklanmaya değer. 6 eklendiğinde dengesizlik yeni düğümün ebeveyninde değil, kökte ortaya çıkar. 5'in faktörü −1, 4'ünki −1'dir; ama kök 2'nin sol alt ağacının yüksekliği 1, sağınınki 3'tür. Döndürme kökte yapılır ve 4 yeni kök olur. 7 eklendiğinde ise dengesizlik 5'tedir ve kök etkilenmez. 15 eklendiğinde yeni düğüm 7'nin sağ çocuğunun (16) soluna girer. Bu RL durumudur. Önce 16 sağa döndürülür, sonra 7 sola döndürülür ve 15, 7 ile 16'nın ebeveyni olur.

Son ağacın yüksekliği 4'tür. Aynı sıra sıradan bir ikili arama ağacına eklenseydi 3 → 4 → 5 → 6 → 7 → 16 → 15 zinciri oluşurdu ve derinlik 7 olurdu. Sürücü program her eklemeden sonra ağacı, faktörleri ve yapılan döndürmeleri yazdı. Sonuçlar tablonun her satırıyla aynı çıktı. Ayrıca her adımda saklanan yüksekliklerin gerçek yüksekliklere eşit olduğu ve bütün faktörlerin −1..+1 aralığında kaldığı denetlendi.

Sunumdaki ekleme kodu, özyinelemeli ikili arama ağacı eklemesinin dönüş yoluna denge denetimini ekler.

avl_gost avl_ekle(avl_gost t, int x) {
  if (!t) return yeni_avl(x);              /* malloc, yuk = 1        */
  if (x < t->veri)      t->sol = avl_ekle(t->sol, x);
  else if (x > t->veri) t->sag = avl_ekle(t->sag, x);
  else return t;                           /* tekrar eden değer yok  */
  t->yuk = 1 + MAX(yuk(t->sol), yuk(t->sag));
  int d = denge(t);
  if (d >  1 && x < t->sol->veri) return sag_dondur(t);            /* LL */
  if (d < -1 && x > t->sag->veri) return sol_dondur(t);            /* RR */
  if (d >  1) { t->sol = sol_dondur(t->sol); return sag_dondur(t); } /* LR */
  if (d < -1) { t->sag = sag_dondur(t->sag); return sol_dondur(t); } /* RL */
  return t;
}

• 2.–5. satırlar. Sıradan özyinelemeli eklemedir. Boş alt ağaca gelinince yeni düğüm ayrılır ve yüksekliği 1 yapılır. Eşit değer gelirse ağaç değiştirilmeden döner.
• 6.–7. satırlar. Özyinelemeden dönerken bu düğümün yüksekliği güncellenir ve denge faktörü hesaplanır. Bu satırlar yeni düğümden köke giden yoldaki her atada sırayla çalışır.
• 8. satır (LL). Faktör +1'den büyükse ağırlık soldadır. x sol çocuğun değerinden küçükse yeni düğüm solun solundadır; tek sağa döndürme yeter.
• 9. satır (RR). Aynası: faktör −1'den küçük ve x sağ çocuktan büyükse tek sola döndürme yapılır.
• 10. satır (LR). Faktör +2 ama yeni düğüm solun sağındadır. Önce sol çocuk sola döndürülür, sonra düğüm sağa döndürülür.
• 11. satır (RL). Aynası.
• 12. satır. Denge bozulmamışsa düğüm olduğu gibi döner.

Kod durumu yeni değerle çocuğun değerini karşılaştırarak ayırt eder. Yeni değer sol çocuktan küçükse solun soluna, büyükse solun sağına girmiştir. Değerler tekrarsız olduğu için eşitlik olmaz. Kullanım kok = avl_ekle(kok, x); biçimindedir. Yeni kök dönüş değeriyle verildiği için *L parametresi gerekmez.

Eklemede en çok bir döndürme (tek ya da çift) yeterlidir. Döndürme, alt ağacın yüksekliğini eklemeden önceki değerine indirir; üstteki atalar bir değişiklik görmez. Kod yine de yolun bütün atalarında yükseklik hesabı ve denge denetimi yapar, ama bunlar sabit işlemlerdir. Toplam maliyet yolun uzunluğu, yani O(lg n)'dir. Özyineleme yığında O(lg n) çerçeve tutar. Silme de benzer biçimde yapılır, ama bir döndürme alt ağacın yüksekliğini düşürebilir. Bu düşüş bir üst atanın dengesini bozabilir. Silmede bu yüzden köke kadar O(lg n) döndürme gerekebilir.

Sürücü programda AVL ağacının büyük girdilerdeki davranışı da ölçüldü. 1, 2, …, n sıralı değerleri eklendiğinde yükseklik tam ⌈lg(n + 1)⌉ çıktı: 1000 için 10, bir milyon için 20, iki milyon için 21. Sıralı veride hep sağa ağırlık bindiği için yalnız sola döndürme yapıldı: bir milyon eklemede 999 980 döndürme. Bir milyon rastgele değer eklendiğinde yükseklik 24 çıktı. Teoremdeki üst sınır bu boyut için 28'dir. Sıradan ikili arama ağacına aynı sıralı veri eklenseydi derinlik bir milyon olurdu.

11.6.7Kırmızı-siyah ağaç ve B-ağacı

AVL ağacı dengeyi sıkı tutar. Bu sıkılığın bedeli, silmede çok sayıda döndürme gerekebilmesidir. Uygulamada iki başka dengeli ağaç da çok kullanılır.

Kırmızı-siyah ağaç (red-black tree) her düğüme kırmızı ya da siyah bir renk verir ve renklere kurallar koyar:

• Her düğüm kırmızı ya da siyahtır; kök ve NULL yapraklar siyahtır.
• Kırmızı bir düğümün çocukları siyahtır; art arda iki kırmızı düğüm bulunmaz.
• Bir düğümden altındaki NULL'lara giden her yolda aynı sayıda siyah düğüm bulunur.

Bu kurallar en uzun yolun en kısa yolun iki katını geçmemesini sağlar. Sonuçta yükseklik en çok 2 lg(n + 1)'dir. Denge AVL'dekinden gevşektir. Buna karşılık ekleme ve silmedeki döndürme sayısı sınırlıdır. Eklemede en çok iki, silmede en çok üç döndürme ve bir miktar renk değişimi yeter. Ağacın yapısı daha az değiştiği için kırmızı-siyah ağaç çok güncellenen yapılarda tercih edilir. C++ dilindeki std::map, Java'daki TreeMap ve Linux çekirdeğindeki birçok yapı kırmızı-siyah ağaçtır.

B-ağacı (B-tree) 1972'de R. Bayer ile E. McCreight'ın önerdiği m yollu dengeli bir arama ağacıdır. Bir düğümde birden çok anahtar ve en çok m çocuk bulunur. Kök dışındaki her düğüm ⌈m/2⌉ − 1 ile m − 1 arasında anahtar tutar. Bütün yapraklar aynı düzeydedir. Bir düğüm dolduğunda ortadaki anahtarı ebeveynine çıkararak ikiye bölünür. Kök bölündüğünde yeni bir kök oluşur. Bu yüzden B-ağacı yapraklardan değil, kökten büyür.

B-ağacının asıl kullanım yeri disk ve benzeri yavaş bellekleridir. Diskten veri bloklar hâlinde okunur ve bir bloğu okumak, bellekte binlerce karşılaştırma yapmaktan uzun sürer. B-ağacında bir düğüm bir disk bloğuna denk getirilir. m yüzlerce olabilir. Böylece ağacın yüksekliği log_m n düzeyine iner. Bir milyar kayıtlık bir dizin üç dört blok okumayla taranır. Veritabanı dizinleri ve dosya sistemleri, verinin yalnız yapraklarda tutulduğu türevi olan B+ ağacını kullanır.

11.6.8Hangi arama ağacı?

Tablo 11.10 bu kesimde anılan arama ağaçlarını karşılaştırır.

Seçim, işin niteliğine bağlıdır. Veri küçük ve rastgele sıradaysa sıradan ikili arama ağacı yeter ve en sade koddur. Arama sayısı güncelleme sayısından çok büyükse AVL ağacının daha sıkı dengesi aramaları kısaltır. Ekleme ve silme sıksa kırmızı-siyah ağacın az döndürmesi öne çıkar. Veri belleğe sığmıyorsa B-ağacı neredeyse tek seçenektir. Erişimlerin küçük bir kısmı birkaç değere yoğunlaşıyorsa splay ağacı bu değerleri köke yakın tutar. Splay ağacının sütundaki “amortize” sözcüğü, tek bir işlemin değil, uzun bir işlem dizisinin ortalama maliyetini anlatır.

11.7Sınav soruları

Sunumun son bölümü, önceki yıllarda sorulmuş üç sınav sorusunu çözer. Üçü de aynı beceriyi ölçer: küçük, iyi tanımlı yordamları birleştirerek doğru ve verimli kod yazmak ve verilen bir kodun ne kadar iş yaptığını hesaplamak.

11.7.1Bir öğenin ağırlığı

Soru şudur. Değerleri tekrarsız bir ikili ağaçta (arama ağacı olması gerekmez) x değerini içeren öğenin ağırlığı, o öğeden uç düğümlere giden yolların en uzunudur. x ağaçta yoksa ya da ağaç boşsa ağırlık 0'dır. int AgirlikBul(agac_gost L, int x) yordamı küresel değişken kullanılmadan yazılmalıdır.

Tanım dikkatle okunursa ağırlığın, x'i içeren düğümün kök olduğu alt ağacın derinliği olduğu görülür. Problem iki iyi bilinen işin bileşimidir: önce düğümü bulmak, sonra onun derinliğini hesaplamak. Ağaç sıralı olmadığı için arama, her ikili ağaçta çalışan yordamla yapılır.

int AgirlikBul(agac_gost L, int x) {
  /* agacta_ara: x'i içeren öğe ya da NULL */
  agac_gost agacta_ara(agac_gost L, int x);
  int derinlik(agac_gost L);
  return derinlik(agacta_ara(L, x));
}
agac_gost agacta_ara(agac_gost L, int x) {
  if (!L) return NULL;
  if (L->veri == x) return L;
  agac_gost T = agacta_ara(L->solcocuk, x);
  return T ? T : agacta_ara(L->sagcocuk, x);
}
int derinlik(agac_gost L) {
  int max(int a, int b);  /* a,b'den küçük olmayan */
  return L ? max(derinlik(L->solcocuk),
                 derinlik(L->sagcocuk)) + 1 : 0;
}

Çözümün güzelliği üçüncü satırdadır: derinlik(agacta_ara(L, x)). Değer bulunamazsa agacta_ara NULL döndürür. derinlik(NULL) da zaten 0'dır. Böylece “bulunamadı” durumu ayrıca ele alınmaz; iki yordamın tanımları onu kendiliğinden çözer. L == NULL durumu da aynı yolla 0 verir.

Kodun ilk iki satırı, yordam içinde bildirilmiş yerel prototiplerdir. Bu bildirimler agacta_ara ve derinlik adlarını yalnız AgirlikBul'un içinde görünür kılar. Yordamlar dosyada AgirlikBul'dan sonra tanımlandığı için bu bildirimler gereklidir. derinlik de aynı yolla max fonksiyonunu bildirir. Burada makro değil fonksiyon kullanılması bilinçlidir. Makro, derinlik yordamının çağrı sayısını üstel yapardı.

Maliyet iki parçanın toplamıdır. Arama en kötü durumda bütün düğümlere bakar: O(n). Derinlik yalnız bulunan alt ağacı gezer; o da en çok n düğümdür. Toplam O(n)'dir. Sürücü programda kökü 2, çocukları 10 ve 20 olan ağaçta ağırlıklar 2, 1, 1 ve x = 30 için 0 çıktı. Silme örneklerindeki ağaçta 40'ın ağırlığı 6, 60'ınki 5, 50'ninki 4, 56'nınki 1 bulundu.

11.7.2Yordam kaç kez çağrılır?

İkinci soru, aynı problemi çözmeye çalışan kötü bir kodu inceler. Kodda agirlik(L), L'nin kök olduğu alt ağacın derinliğini veren bir yordamdır.

int AgirlikBul(oge_gost L, int x) {
  if (!L) return 0;
  else if (L->veri == x) return agirlik(L);
  if (AgirlikBul(L->solcocuk, x) >
      AgirlikBul(L->sagcocuk, x))
    AgirlikBul(L->solcocuk, x);
  if (AgirlikBul(L->sagcocuk, x) >
      AgirlikBul(L->solcocuk, x))
    AgirlikBul(L->sagcocuk, x);
  return 0;
}

Soru iki bölümlüdür. Ağaç kökü 2, sol çocuğu 10, sağ çocuğu 20 olan üç düğümlü ağaçtır. Birinci bölümde x = 20 ve x = 30 için yordamın kaç kez çağrıldığı sorulur. İkinci bölümde en kötü durum için özyinelemeli bağıntı yazılıp çözülmelidir.

Önce bir yaprağın, ör. 10'un, x'i içermediği durumda ne yaptığına bakılsın. Yaprak NULL değildir ve değeri x'e eşit değildir. Birinci if iki alt çağrı yapar, ikinci if iki alt çağrı daha yapar. Dördü de NULL ile yapılır ve 0 döndürür. 0 > 0 yanlış olduğu için koşulların içindeki çağrılar yapılmaz. Bir yaprak çağrısı kendisiyle birlikte 1 + 4 = 5 çağrı eder.

x = 30 ağaçta yoktur. Kök çağrısı 10'u iki kez, 20'yi iki kez çağırır. Her biri 0 döndürür ve koşullu çağrılar yapılmaz. Toplam 1 + 4 · 5 = 21 çağrıdır. x = 20'de durum farklıdır. 20'ye yapılan çağrı ikinci satırda eşitliği bulur ve tek çağrıda ağırlığı (1) döndürür. Kökte birinci if, 10 için 5, 20 için 1 çağrı yapar; 0 > 1 yanlıştır. İkinci if yine 1 + 5 çağrı yapar ve 1 > 0 doğrudur. Koşulun içindeki AgirlikBul(L->sagcocuk, x) bir çağrı daha yapar. Toplam 1 + 6 + 6 + 1 = 14'tür. Bütün bu emeğe karşın yordam her iki durumda da 0 döndürür. Koşulların içindeki çağrıların sonucu kullanılmaz ve son satır her zaman 0'dır. Kod hem yavaş hem yanlıştır: yalnız x kökteyse doğru cevap verir.

En kötü durumda x ağaçta yoktur ve bütün ağaç gezilir. Her çağrı her alt ağacını iki kez çağırır. Çarpık bir ağaçta bir alt ağaç n − 1 düğümlü, öteki boştur. Bağıntı T(n) = 2T(n − 1) + c olur. Açılırsa T(n) = 2ⁿT(0) + c(2ⁿ − 1) bulunur, yani Θ(2ⁿ). Dengeli bir ağaçta iki alt ağacın her biri yaklaşık n/2 düğümlüdür ve dördü de çağrılır: T(n) = 4T(n/2) + c. Ana teorem ya da açma yöntemiyle çözüm Θ(n²)'dir. Her düzeyde çağrı sayısı dört katına çıkarken problem yarıya iner ve 4^{lg n} = n²'dir.

Ölçümler bağıntıları doğrular. Zincirde çağrı sayısı tam 2ⁿ⁺² − 3'tür ve oran 4'e yaklaşır. Dolu ağaçta oran 4/3'e yaklaşır. Doğru tasarım ise önceki kesimdeki çözümdür ve O(n) sürer. 20 düğümlük bir zincirde kötü yordam dört milyondan fazla çağrı yapar. Doğru yordam aynı ağaçta 20 düğüme bakmak için birkaç düzine çağrıyla yetinir.

Sorunun dersi, bir özyinelemeli çağrının sonucunu iki kez hesaplamanın bedelidir. Her düzeyde iş ikiye katlanır ve katlar birbiriyle çarpılır. Bir alt çağrının sonucu birden çok kez gerekiyorsa bir yerel değişkende saklanmalıdır. Derinlik yordamındaki sol ve sag değişkenleri tam bu işi görür.

11.7.3İki çağrının arasında SWAP

Üçüncü soru bir yordamın ağaç üzerindeki etkisini sorar. SWAP(x, y, t) makrosu t yardımıyla x ile y'nin değerlerini değiştirir: ((t) = (x), (x) = (y), (y) = (t)).

void yordam(agac_gost L) {
  agac_gost p;
  if (L) {
    yordam(L->solcocuk);
    SWAP(L->solcocuk, L->sagcocuk, p);
    yordam(L->sagcocuk);
  }
}

Soru şudur: {44, 30, 15, 18, 86, 97, 65, 113, 74, 129} değerleriyle kurulan ikili arama ağacı için yordam işletilsin. SWAP satırından her geçişte ağacın görünümü değişmişse ağaç yeniden çizilsin ve son hâli yorumlansın.

Başlangıç ağacında kök 44'tür. Solunda 30 vardır; 30'un solunda 15, 15'in sağında 18 durur. Kökün sağında 86 vardır. 86'nın solunda 65 ve onun sağında 74; sağında 97, 113 ve 129'dan oluşan sağa uzanan bir zincir bulunur.

Yordam bir düğümde önce sol alt ağacı işler, sonra iki çocuğu değiştirir, sonra yeni sağ çocuğu işler. Ama yeni sağ çocuk, az önce işlenmiş olan eski sol çocuktur. Eski sağ çocuk ise sola geçmiştir ve hiç işlenmez. Adımlar şöyledir.

1. yordam(44) → yordam(30) → yordam(15). 15'in solu boştur. SWAP 15: 18 sola geçer.
2. 15'in yeni sağı boştur. 30'a dönülür. SWAP 30: 15 alt ağacı sağa geçer.
3. 30'un yeni sağı olan 15 yeniden işlenir. Önce solu (18) işlenir; 18'de SWAP yapılır ama iki çocuk da boş olduğu için görünüm değişmez. SWAP 15: 18 yeniden sağa geçer. Sağdaki 18 bir kez daha işlenir; görünüm yine değişmez.
4. 44'e dönülür. SWAP 44: 86 alt ağacı sola, 30 alt ağacı sağa geçer.
5. 44'ün yeni sağı olan 30 yeniden işlenir. Solu boştur. SWAP 30: 15 alt ağacı sola döner. Yeni sağ boştur ve yordam biter.

Görünümün değiştiği SWAP'lar sırasıyla 15, 30, 15, 44 ve 30'dadır. 18'deki iki SWAP görünümü değiştirmez. Son ağaç 44(86(65(−, 74), 97(−, 113(−, 129))), 30(15(−, 18), −)) biçimindedir. Yalnız kökün iki alt ağacı yer değiştirmiştir. 30 alt ağacı iki kez işlenmiş, her değişiklik ikinci işlemde geri alınmıştır. 86 alt ağacı ise hiç işlenmemiştir. Sonuç ne ağacın kendisi ne de aynasıdır, artık bir ikili arama ağacı da değildir. Sürücü program SWAP satırına bir izleme çağrısı ekleyerek her adımı yazdırdı; sıra ve son ağaç yukarıdaki gibidir.

SWAP iki özyinelemeli çağrının önüne ya da arkasına yazılsaydı ağacın tam aynası elde edilirdi. Önce yazıldığında çocuklar değiştirilir, sonra iki alt ağaç ayrı ayrı aynalanır. Sona yazıldığında önce iki alt ağaç aynalanır, sonra yerleri değiştirilir. Her iki durumda da her alt ağaç tam bir kez işlenir. Aynalanmış ikili arama ağacında kök ortada gezinme değerleri azalan sırada verir.

11.8Karmaşıklık özeti

Tablo 11.12 bu notta yazılan bütün yordamların maliyetini bir arada verir. h ağacın derinliğidir; dengeli ağaçta O(lg n), çarpık ağaçta n olur.

Tablonun özü şudur: ikili arama ağacında arama, ekleme ve silme yolu izler ve O(h) sürer. Ağacın her düğümüne bakması gereken işlemler (derinlik, genel ağaçta arama) O(n)'dir. Dengeli ağaçlar h'yi O(lg n)'de tutarak yol izleyen işlemlerin en kötü durumunu da logaritmik yapar. Ekleme satırındaki Ω(lg n), eklemenin hiçbir ağaçta lg n'den hızlı olamayacağını anlatır.

11.9Sık yapılan hatalar

1. Kök işaretçisini güncelleyememek. Ekleme yordamı agac_gost L alırsa boş ağaca yapılan ilk ekleme çağıranın kökünü değiştirmez. Ağaç boş kalır, düğüm sızar. Ya agac_gost *L ile adres gönderilmeli ya da yeni kök döndürülüp atanmalıdır.
2. Arka işaretçiyi tutmamak. Döngüsel eklemede p NULL'a ulaştığında yeni düğümün bağlanacağı ebeveyn artık bilinmez. Bir adım geriden gelen q ya da işaretçinin işaretçisi kullanılmalıdır.
3. Alt çağrının sonucunu döndürmemek. Özyinelemeli aramada return ara(...) yerine yalnız ara(...) yazılırsa bulunan adres kaybolur.
4. Taşınan öğenin çocuğunu unutmak. İki çocuklu silmede sol alt ağacın en büyüğünün sol çocuğu (örnekte 56) ebeveynine bağlanmazsa ağaçtan kopar.
5. Küresel değişken ve gereksiz ek parametre. Derinlik için küresel bir sayaç ya da “ilk çağrıda 0 geçirilmeli” türünden bir parametre, yordamı kırılgan ve yeniden kullanılamaz yapar.
6. Makroya özyinelemeli çağrı vermek. MAX(derinlik(...), derinlik(...)) çağrılardan birini iki kez işletir ve süreyi üstele çıkarır.
7. Serbest bıraktıktan sonra kullanmak. Silmede bağ güncellenmeden önce düğüm free edilirse, sonraki satır serbest bırakılmış belleği okur.
8. Denetimi yalnız çocuklarla yapmak. Bir ağacın ikili arama ağacı olup olmadığı yalnız ebeveyn–çocuk karşılaştırmasıyla anlaşılmaz; her düğüme kökten gelen aralık uygulanmalıdır.

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

Bu kesim sunumdaki altı alıştırmayı çözer. Kodlu çözümler sürücü programlarla derlenip çalıştırıldı.

1. Ekleme ve kök önde sıra. Boş bir ağaca sırasıyla 50, 30, 70, 20, 40, 60, 80, 35 eklensin. 50 kök olur. 30 ve 70 onun çocuklarıdır. 20 ile 40, 30'un; 60 ile 80, 70'in çocuklarıdır. 35, 50 → 30 → 40 yolunu izleyip 40'ın soluna girer. Ağaç 50(30(20, 40(35, −)), 70(60, 80)) biçimindedir ve derinliği 4'tür. Kök önde sıra 50 30 20 40 35 70 60 80'dir.

2. Aynı ağaçtan 30'u iki yöntemle silmek. 30'un iki çocuğu vardır. Birinci yöntemde sol alt ağacın en büyüğü aranır. 30'un sol alt ağacı tek düğümdür (20); en büyük 20'dir. 30'un yerine 20 yazılır ve eski 20 düğümü silinir. Ağaç 50(20(−, 40(35, −)), 70(60, 80)) olur. 50 → 20 → 40 → 35 yolu kaldığı için derinlik 4'tür. İkinci yöntemde sağ alt ağacın en küçüğü aranır: 40'tan sola, 35'e gidilir. 30'un yerine 35 yazılır ve 40'ın solu NULL olur. Ağaç 50(35(20, 40), 70(60, 80)) biçimindedir ve derinliği 3'e iner. Bu örnekte ikinci yöntem daha dengeli bir ağaç verir.

3. En küçük ve en büyük değer. En küçük değer, kökten sürekli sola gidilerek bulunur; sol çocuğu olmayan ilk düğümdedir. En büyük değer de sürekli sağa gidilerek bulunur.

agac_gost en_kucuk(agac_gost L) {
  if (L)
    while (L->solcocuk) L = L->solcocuk;
  return L;                 /* boş ağaçta NULL */
}
agac_gost en_buyuk(agac_gost L) {
  if (L)
    while (L->sagcocuk) L = L->sagcocuk;
  return L;
}

İki yordam da yalnız bir yol izler ve O(h) sürer. Boş ağaçta NULL döndürür. Silme örneklerindeki ağaçta en küçük değer 10, en büyük değer 73 çıktı.

4. İkili arama ağacı denetimi. Her düğüme izin verilen (alt, üst) aralığı parametre olarak geçirilir. Sola inerken üst sınır, sağa inerken alt sınır düğümün değeri olur.

#include <limits.h>
/* L'deki her değer alt < değer < ust olmalı */
boolean aralikta(agac_gost L, long long alt, long long ust) {
  if (!L) return TRUE;
  if (L->veri <= alt || L->veri >= ust) return FALSE;
  return aralikta(L->solcocuk, alt, L->veri) &&
         aralikta(L->sagcocuk, L->veri, ust);
}
boolean bst_mi(agac_gost L) {
  return aralikta(L, (long long)INT_MIN - 1, (long long)INT_MAX + 1);
}

Sınırlar long long tipindedir. Böylece INT_MIN ve INT_MAX değerleri de ağaçta bulunabilir; başlangıç sınırları bunların bir dışındadır. long kullanılsaydı, long'un 32 bit olduğu Windows'ta INT_MAX + 1 taşardı. Her düğüme bir kez bakıldığı için süre O(n), özyineleme derinliği O(h)'dir. Yordam silme örneklerindeki ağacı ve onun dört silme sonucunu geçerli buldu. Kökü 15, çocukları 10 ve 18 olan bir ağaçta 18'in soluna 12 konduğunda ise FALSE döndürdü. 12, 18'den küçüktür; yalnız çocuklarla karşılaştırma bu ağacı geçerli sayardı. Ama 12, 15'in sağ alt ağacındadır ve 15'ten küçük olamaz.

5. AVL ağacına 10, 20, 30, 25, 28. 10 ve 20 eklenince 10'un faktörü −1 olur. 30 eklenince 10'un faktörü −2'dir ve yeni değer sağın sağındadır (RR). 10 sola döndürülür ve 20 kök olur: 20(10, 30). 25, 30'un soluna girer; faktörler −1..+1 aralığındadır. 28, 25'in sağına girer. 30'un faktörü +2 olur ve yeni değer solun sağındadır (LR). Önce 25 sola döndürülür: 28, 25'in yerine çıkar. Sonra 30 sağa döndürülür: 28, 25 ile 30'un ebeveyni olur. Son ağaç 20(10, 28(25, 30))'dur. Sürücü program aynı iki döndürmeyi raporladı: 30'da sol_dondur(10), 28'de sol_dondur(25) ve sag_dondur(30).

6. x'ten küçük anahtar sayısı. En basit çözüm ağacı kök ortada gezmek ve x'e ulaşana kadar saymaktır; süre O(n)'dir. İkili arama ağacının düzeni kullanılarak bazı alt ağaçlar atlanabilir. Kök x'ten küçük değilse sağ alt ağaç tümüyle büyüktür ve sayım yalnız solda sürer. Kök x'ten küçükse kökün kendisi ve bütün sol alt ağacı küçüktür. Bunlar sayılır ve sayım sağda sürer.

int dugum_say(agac_gost L) {
  return L ? 1 + dugum_say(L->solcocuk) + dugum_say(L->sagcocuk) : 0;
}
/* x'ten küçük değerlerin sayısı */
int kucuk_say(agac_gost L, int x) {
  if (!L) return 0;
  if (L->veri >= x)                 /* kök ve sağı büyük */
    return kucuk_say(L->solcocuk, x);
  return 1 + dugum_say(L->solcocuk) /* kök ve solu küçük */
           + kucuk_say(L->sagcocuk, x);
}

Bu sürümde dugum_say hâlâ sol alt ağaçları baştan sona gezer. Bu yüzden en kötü durum yine O(n)'dir. Her düğümde alt ağacının boyutu bir alanda saklanırsa dugum_say O(1)'e iner ve sayım tek bir yol boyunca, yani O(h)'de yapılır. Bu alan her ekleme ve silmede yol üzerindeki düğümlerde güncellenmelidir. Örnek ağaçta 55'ten küçük 7, 41'den küçük 4 değer bulundu.

11.11Özet

• İkili arama ağacında değerler tektir; her düğümün sol alt ağacındaki bütün değerler ondan küçük, sağ alt ağacındakiler büyüktür ve alt ağaçlar da ikili arama ağacıdır. Kök ortada gezinme değerleri artan sırada verir.
• Ekleme, değeri kökten başlayarak arar ve ilk NULL'ın yerine koyar. Döngüsel sürüm bir adım geriden gelen q işaretçisini, boş ağaç için agac_gost *L parametresini kullanır. Ekleme sırası ağacın biçimini belirler; sıralı veri çarpık ağaç kurar.
• Arama her karşılaştırmada bir alt ağacı eler ve O(h) sürer. Özyinelemeli sürüm kuyruk özyinelemesidir ve alt çağrının sonucunu aynen döndürür. Sıralı olmayan ağaçta iki yana da bakmak gerekir ve arama O(n) olur.
• Derinlik MAX(sol, sağ) + 1 ile özyinelemeli hesaplanır; 2n + 1 çağrı yapar ve Θ(n)'dir. Küresel değişken ve gizli başlangıç değeri taşıyan parametre kullanılmaz. Makroya özyinelemeli çağrı verilirse süre üstel olur.
• Silmede yaprak ve tek çocuklu düğüm kolaydır. İki çocuklu düğümde öncülün (ya da ardılın) değeri kopyalanır ve onun düğümü silinir; bağ işaretçinin işaretçisiyle tek satırda güncellenir. Silme yöntemi ağacın derinliğini değiştirebilir.
• Denge. Rastgele veride ortalama derinlik Θ(lg n)'dir, ama sıralı veride n'ye çıkar. AVL ağacı her düğümde denge faktörünü −1..+1 aralığında tutar; yüksekliği en çok yaklaşık 1,44 lg(n + 2)'dir.
• AVL eklemesinde dengesizlik LL ve RR durumlarında tek, LR ve RL durumlarında çift döndürmeyle düzeltilir. Bir döndürme yalnız iki işaretçiyi değiştirir ve O(1)'dir; eklemede en çok bir döndürme yeter.
• Kırmızı-siyah ağaç daha gevşek bir dengeyle az döndürme yapar ve kütüphanelerin eşleme yapılarında kullanılır. B-ağacı çok anahtarlı düğümleriyle disk erişimini azaltır ve veritabanlarında kullanılır.

11.12Kavram listesi

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

• ikili arama ağacı binary search tree (BST)
• anahtar key
• alt ağaç subtree
• yaprak leaf
• derinlik depth
• düzey level
• kök önde preorder
• kök ortada inorder
• kök sonda postorder
• düzey sırası level-order
• çarpık ağaç skewed tree
• dengeli ağaç balanced tree
• kendini dengeleyen ağaç self-balancing tree
• adresle çağrı call by reference
• işaretçiye işaretçi pointer to pointer
• küresel değişken global variable
• makro macro
• öncül predecessor
• ardıl successor
• bellek sızıntısı memory leak
• AVL ağacı AVL tree
• denge faktörü balance factor
• döndürme rotation
• çift döndürme double rotation
• kırmızı-siyah ağaç red-black tree
• B-ağacı B-tree
• splay ağacı splay tree
• yineleme bağıntısı recurrence relation
• amortize analiz amortized analysis

11.13Kendini Dene

1. Boş bir ikili arama ağacına sırasıyla 8, 3, 10, 1, 6, 14, 4, 7, 13 ekleniyor. Ağacın derinliği nedir? Kök önde ve kök ortada gezinme sıraları nelerdir?

   Cevap

   Ağaç 8(3(1, 6(4, 7)), 10(−, 14(13, −))) biçimindedir. En uzun yollar 8 → 3 → 6 → 4 ile 8 → 10 → 14 → 13'tür; derinlik 4'tür. Kök önde sıra 8 3 1 6 4 7 10 14 13, kök ortada sıra 1 3 4 6 7 8 10 13 14'tür.

2. Aynı ağaçta arama_agacinda_ara ile 7 ve 5 aranıyor. Her aramada hangi düğümlere bakılır ve sonuç ne olur?

   Cevap

   7 için 8, 3, 6, 7 düğümlerine bakılır ve 7'nin adresi döner. 5 için 8, 3, 6, 4 düğümlerine bakılır; 4'ün sağ çocuğu NULL olduğu için arama NULL döndürür.

3. Aynı ağaca sunumdaki sil yordamı uygulanıyor: önce yalnız 3 siliniyor (ayrı bir denemede de yalnız kök 8). Her durumda ağaç nasıl değişir?

   Cevap

   3'ün iki çocuğu vardır. Sol alt ağacının en büyüğü 1'dir (1'in sağı yok). 3'ün yerine 1 yazılır, eski 1 düğümü silinir: 8(1(−, 6(4, 7)), 10(−, 14(13, −))). Kök 8 silinirse sol alt ağacın en büyüğü 3 → 6 → 7 yoluyla 7 bulunur. Kökün veri alanına 7 yazılır, 6'nın sağı NULL olur: 7(3(1, 6(4, −)), 10(−, 14(13, −))).

4. Bir ikili arama ağacının kök önde gezinmesi 30 20 10 25 40 35 50'dir. Kök sonda gezinmesi nedir?

   Cevap

   Ağaç 30(20(10, 25), 40(35, 50))'dir. Kök sonda gezinme 10 25 20 35 50 40 30'dur.

5. Boş bir AVL ağacına 1, 2, 3, 4, 5, 6, 7 sırayla ekleniyor. Hangi eklemelerde döndürme gerekir ve son ağaç nedir?

   Cevap

   Bütün dengesizlikler RR durumudur ve tek sola döndürmeyle düzelir. 3 eklenince 1'de, 5 eklenince 3'te, 6 eklenince kök 2'de, 7 eklenince 5'te sola döndürme yapılır; toplam dört döndürme. Son ağaç tam dengelidir: 4(2(1, 3), 6(5, 7)) ve yüksekliği 3'tür.

6. Yüksekliği 5 olan bir AVL ağacında en az kaç düğüm bulunur?

   Cevap

   N(h) = N(h − 1) + N(h − 2) + 1, N(1) = 1, N(2) = 2 bağıntısından N(3) = 4, N(4) = 7, N(5) = 12 bulunur. En az 12 düğüm gerekir.

7. Tek satırlık derinlik yordamı MAX makrosuyla yazılmıştır. Üç düğümlük sağa uzanan bir zincirde yordam toplam kaç kez çağrılır? Yerel değişkenli sürüm kaç kez çağrılır?

   Cevap

   Makrolu sürümde T(0) = 1 ve T(n) = 2T(n − 1) + 2'dir: T(1) = 4, T(2) = 10, T(3) = 22. Yerel değişkenli sürüm 2n + 1 = 7 çağrı yapar. İki değer de sayaçla ölçüldü.

8. arama_agacina_ekle yordamının parametresi agac_gost *L yerine agac_gost L yapılır ve son satırlar buna göre düzeltilirse, boş ağaca 5 ve 7 eklemenin sonucu ne olur?

   Cevap

   İlk eklemede yeni düğüm yalnız yordamın yerel L kopyasına atanır. Çağıranın kökü NULL kalır ve düğüm hiçbir yerden gösterilmediği için sızar. İkinci ekleme de ağacı boş bulur ve aynı şey olur. Ağaç boş kalır, iki düğüm sızar.

9. SWAP satırı yordam'da iki özyinelemeli çağrının önüne alınırsa, kökü 2, sol çocuğu 1, 1'in sol çocuğu 0, sağ çocuğu 3 olan ağaç nasıl değişir?

   Cevap

   Önce kökte çocuklar değişir: 2(3, 1(0, −)). Sonra sol alt ağaç (3) ve sağ alt ağaç (1) ayrı ayrı işlenir; 1'de 0 sağa geçer. Son ağaç 2(3, 1(−, 0))'dır ve ilk ağacın tam aynasıdır. Kök ortada gezinme 3 2 1 0, yani azalan sıradır.

11.14İleri okuma

• E. Horowitz, S. Sahni ve S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Kesim 5.7 ve 10.2: bu notun izlediği ikili arama ağacı yordamlarının ve AVL ağacının kaynağıdır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı), Bölüm 12, 13 ve 18: ikili arama ağacını, rastgele kurulan ağacın ortalama derinliğini, kırmızı-siyah ağacı ve B-ağacını kanıtlarıyla verir.
• M. A. Weiss, Data Structures and Algorithm Analysis in C (2. baskı), Kesim 4.4: notta kullanılan AVL ekleme örneğini ve döndürme kodlarını içerir; splay ağacını da tanıtır.
• R. Sedgewick, Algorithms in C, Kısım 1–4, Bölüm 12–13: ikili arama ağacının ortalama durum analizini ve dengeli ağaçların farklı türlerini karşılaştırır.

11.15Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Kesim 5.7 (ikili arama ağacı) ve 10.2 (AVL ağacı).
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, Bölüm 12 (ikili arama ağaçları), 13 (kırmızı-siyah ağaçlar), 18 (B-ağaçları).
3. M. A. Weiss, Data Structures and Algorithm Analysis in C, Kesim 4.4 (AVL ağaçları).
4. R. Sedgewick, Algorithms in C, Kısım 1–4, Bölüm 12–13.

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