Bölüm 16: Kümeler ve Union-Find

16.1Ayrık kümeler

Bir sosyal ağda kim kimin arkadaşı, bir şehir ağında hangi kavşaklar birbirine yolla bağlı, bir devrede hangi uçlar aynı iletkene lehimli? Bu soruların hepsinde öğeler gruplara ayrılır ve her öğe tek bir gruptadır. Gruplar zamanla birleşir: iki kavşak arasına yol yapılınca iki bölge tek bölge olur. Grupların bölündüğü görülmez. Bu tür problemler için gereken yapı çok sadedir. Yalnız iki işlemi destekler, ama bu iki işlemi son derece hızlı yapar. Az sayıda satırla yazılan bu yapı, çizge algoritmalarının birçoğunda bir alt yapı olarak karşımıza çıkar. Önce iyi öğrenilmelidir ki gerektiğinde akla gelsin ve kullanılabilsin.

Programlamaya geçmeden önce problemi programlama bilmeyen biri gibi, matematiğin diliyle doğru ifade etmek gerekir. Doğru kurulmuş bir tanım, hangi işlemlerin gerektiğini ve hangilerinin gereksiz olduğunu baştan gösterir.

16.1.1Ayrık küme ve orman gösterimi

Öğeler 0, 1, …, n − 1 sayılarıyla adlandırılır. Bu sayılar bir öğrencinin numarası, bir bilgisayarın ağdaki sırası ya da bir kavşağın kodu olabilir. Öğelerin asıl verisi başka bir dizide tutulur; union-find yalnız numaralarla çalışır.

Tanımdaki koşul, hiçbir öğenin iki kümede birden bulunmadığını söyler. Her öğenin kümesi tektir; bu yüzden “öğe hangi kümede?” sorusunun her zaman tek bir cevabı vardır.

Kümeleri bilgisayarda nasıl göstermeli? Seçilen yol, her kümeyi bir ağaçla göstermektir. Kümenin öğelerinden biri kök olur, ötekiler onun altına yerleşir. Sıradan ağaçlardan önemli bir farkı vardır: bağlar çocuktan ebeveyne doğrudur. Her düğüm yalnız kendi ebeveynini bilir; çocuklarını bilmez. Şekil 16.1'deki oklar bu yüzden yukarı bakar. Birbirinden ayrık ağaçların oluşturduğu topluluğa orman (forest) denir. Ayrık kümelerin gösterimi de bir ormandır.

Ağaçlardaki yerleşimin bir anlamı yoktur. 6, 7 ve 8'in 0'ın altında durması, 0'ın bu kümede “özel” olduğunu göstermez. Aynı küme, 7'nin kök olduğu ve ötekilerin ona bağlandığı bir ağaçla da gösterilebilirdi. Ağacın görevi yalnız “bu öğeler bir aradadır” bilgisini taşımaktır. Bu serbestlik daha sonra çok işe yarar: ağacın biçimini maliyeti düşürecek yönde istediğimiz gibi seçebiliriz.

Bağların neden yukarı doğru olduğu da işlemlerden anlaşılır. Union-find hiçbir zaman “bu kümenin öğelerini listele” diye sormaz. Sorulan hep “bu öğe hangi kümede?” sorusudur. Bu soruya bir öğeden başlayıp köke kadar tırmanarak cevap verilir. Tırmanmak için her düğümün ebeveynini bilmesi yeter. Çocuk listesi tutmak hem bellek harcar hem de hiçbir işlemde kullanılmaz.

16.1.2Birleşim ve küme bulma

Yapının desteklediği iki işlem şunlardır:

1. Ayrık küme birleşimi (union). S_i ve S_j ayrık iki kümeyse birleşimleri S_i ∪ S_j = {x : x ∈ S_i ∨ x ∈ S_j} kümesidir. Birleşimden sonra S_i ile S_j artık ayrı ayrı bulunmaz; yerlerini tek bir küme alır. Örneğin S₁ ∪ S₂ = {0, 6, 7, 8, 1, 4, 9} olur.
2. Küme bulma (find). Küme_bul(i), i öğesini içeren kümeyi bulur. Kümenin adı olarak ağacın kökü döndürülür.

Birleşim ağaçlarla çok kolay yapılır. İki ağacın köklerinden biri, ötekinin çocuğu yapılır. Bunun için tek bir bağ yazmak yeter: köklerden birinin ebeveyn bilgisi öteki kökü gösterecek biçimde günlenir. Şekil 16.2 aynı birleşimin iki biçimini gösterir. Ortadaki şekilde 4'ün ebeveyni 0 yapılmış, S₂ ağacı 0'ın alt ağacı olmuştur. Sağdaki şekilde ise 0'ın ebeveyni 4 yapılmıştır. İki sonuç da aynı kümeyi gösterir ve ikisi de doğrudur. Ama ağaçların biçimi farklıdır. Hangisinin seçileceği, sonraki küme bulma işlemlerinin maliyetini belirler. Bu notun büyük kısmı bu seçimin nasıl yapılacağı üzerinedir.

Sağdaki biçimde 6, 7 ve 8 öğelerinin köke uzaklığı 1'den 2'ye çıkmıştır. Ortadaki biçimde ise yalnız 1, 4 ve 9'un uzaklığı birer artmıştır. Bir öğenin kümesini bulmak, o öğeden köke kadar yürümek demektir. Köke uzaklık arttıkça bulma pahalılaşır. Ağırlıklı kural bu küçük gözleme dayanır.

16.1.3Kümenin adı: kök

Kümelerin S₁, S₂ gibi adları insanlar içindir. Algoritmalar her küme adını ağacın kökü ile ilişkilendirir. “S₁ kümesi” yerine “0 nolu küme” denir. Böylece Küme_bul yordamının döndürdüğü kök numarası kümenin adı olur.

Kökün ad olarak kullanılması önemli bir sonuç doğurur. İki öğenin aynı kümede olup olmadığı, köklerinin karşılaştırılmasıyla anlaşılır. Küme_bul(8) == Küme_bul(6) sorusu “8 ile 6 aynı kümede mi?” demektir. İki çağrı da 0 döndürdüğü için cevap evettir. Küme_bul(8) == Küme_bul(9) ise 0 ile 4'ü karşılaştırır; cevap hayırdır.

Kümenin adı birleşimle değişebilir. Şekil 16.2'nin sağındaki birleşimden sonra 8'in kümesi artık 0 değil, 4'tür. Bu yüzden bir öğenin kümesi bir değişkende saklanıp sonra kullanılmamalıdır. Her soru, o anki ağaçlar üzerinde yeniden Küme_bul çağrılarak cevaplanır.

16.2Dizi ile gerçekleme

Model hazır: her küme bir ağaç, her ağacın kökü kümenin adı, bağlar çocuktan ebeveyne. Şimdi bu modelin C'de nasıl saklanacağına karar vermek gerekir.

16.2.1Gerçekleme seçenekleri

Akla ilk gelen yol, her kümeyi bir bağlı liste olarak tutmaktır. İki listeyi uç uca eklemek, son düğümün işaretçisini değiştirmekle biter; birleşim O(1)'dir. Ama bir öğenin hangi listede olduğunu bulmak için listeleri baştan sona taramak gerekir. Küme bulma O(n) olur. Kümeleri sıralı dizilerde tutmak aramayı hızlandırır, ama her birleşimde iki sıralı diziyi birleştirmek ya da yeniden sıralamak gerekir. Bunun maliyeti O(n lg n)'ye kadar çıkar.

Üçüncü satır en umut vericisidir. Birleşim yine tek bağ yazmaktır. Küme bulmanın maliyeti ise ağacın derinliği kadardır. Derinlik küçük tutulabilirse küme bulma da hızlanır.

Ağaçlar genellikle düğüm yapıları ve işaretçilerle kurulur. Burada buna gerek yoktur. Öğeler zaten 0'dan n − 1'e numaralıdır; numara doğrudan dizi indisi olarak kullanılabilir. Her düğüm yalnız tek bir bilgiye gereksinim duyar: ebeveyninin numarası. Öyleyse bütün orman, n elemanlı tek bir tamsayı dizisine sığar. En güvenilir, en sağlam ve en hızlı veri yapısı olan diziyle gerçekleme yapmak mümkündür. Dizide bir öğeye erişim O(1)'dir, işaretçi kovalamak gerekmez, malloc çağrısı tek seferdir ve bellek ardışık olduğu için önbellek de iyi kullanılır.

16.2.2Ebeveyn dizisi

Bir düğümün hemen üstündeki düğüme ebeveyn denir; koddaki ata dizisi bu ebeveyn bağlarını tutar. Kökün bir ebeveyni olmadığı için onun hücresine geçerli bir indis yazılamaz. Düğüm numaraları 0 ya da pozitif olduğundan negatif bir değer hiçbir düğümle karışmaz ve “burası kök” işareti olarak güvenle kullanılır. Şekil 16.3 örnek ormanın ebeveyn dizisini gösterir.

Diziyi okumak kolaydır. 1 ve 9'un ebeveyni 4'tür; ata[1] ve ata[9] hücrelerinde 4 yazar. 3 ve 5'in ebeveyni 2'dir. 6, 7 ve 8'in ebeveyni 0'dır. 0, 2 ve 4 kümelerin kökleridir: ata[0] = ata[2] = ata[4] = −1. C'de bu dizi şöyle tanımlanır:

#define N 10
int ata[N] = { -1, 4, -1, 2, -1, 2, 0, 0, 0, 4 };

Bellekte bu dizi 10 ardışık int hücresidir. 64 bitlik bir Windows ya da Linux makinesinde int 4 bayttır ve dizi 40 bayt yer tutar. Dizi 0x1000 adresinde başlıyorsa ata[i] hücresi 0x1000 + 4i adresindedir. Tablo 16.3 bu görünümü verir. İşaretçili bir ağaçta her düğüm ayrı bir malloc bloğu olur ve en az bir işaretçi (8 bayt) taşır. Burada ise düğüm başına 4 bayt yeter ve bütün ağaçlar tek bir blokta durur.

Ebeveyn dizisi bir ağacı tek başına tam olarak tanımlar. Dizi verilince ağaç çizilebilir: her i için i'den ata[i]'ye bir ok çizmek yeter. Ters yön de doğrudur: her ağaç tek bir ebeveyn dizisi verir. Ancak dizi bir düğümün çocuklarını doğrudan söylemez. 0'ın çocuklarını bulmak için bütün diziyi tarayıp değeri 0 olan hücreleri toplamak gerekir. Union-find bu soruyu hiç sormadığı için bu eksiklik sorun olmaz.

16.2.3Ebeveyn dizisini dinamik bellekte kurmak

Sunumdaki kodlar ata dizisini #define N 10 boyutlu küresel bir dizi olarak tanımlar. Bu, yordamları kısa tutar ve örnekler için yeterlidir. Gerçek bir programda öğe sayısı ise çoğunlukla çalışma anında belli olur: bir dosyadan okunan çizgenin düğüm sayısı derleme anında bilinmez. Bu durumda dizi malloc ile ayrılır. Aşağıdaki kod öğe sayısını ve diziyi tek bir yapıda toplar:

typedef struct {
  int  n;      /* öğe sayısı */
  int *ata;    /* ata[i]: i'nin ebeveyni; kökte -(düğüm sayısı) */
} kumeler;

kumeler *kumeler_olustur(int n) {
  kumeler *k = malloc(sizeof *k);
  if (k == NULL) return NULL;            /* bellek yok */
  k->ata = malloc(n * sizeof *k->ata);
  if (k->ata == NULL) {                  /* dizi alınamadı */
    free(k);                             /* yarım yapıyı geri ver */
    return NULL;
  }
  k->n = n;
  for (int i = 0; i < n; i++)
    k->ata[i] = -1;                      /* her öğe tek öğeli küme */
  return k;
}

void kumeler_sil(kumeler **kp) {
  if (*kp == NULL) return;
  free((*kp)->ata);                      /* önce iç dizi */
  free(*kp);                             /* sonra yapının kendisi */
  *kp = NULL;                            /* çağıranın işaretçisi boşalır */
}

kumeler_olustur iki ayrı blok ayırır. Birincisi yapının kendisidir: bir int ve bir işaretçi. 64 bitlik makinede sizeof(kumeler) 16 bayttır: 4 bayt n, 4 bayt hizalama boşluğu ve 8 bayt işaretçi. İkinci blok n tamsayılık ebeveyn dizisidir. malloc(n * sizeof *k->ata) ifadesindeki sizeof *k->ata, dizinin öğe tipinin boyutunu verir. Tip sonradan long'a çevrilse bile bu satırın değişmesi gerekmez.

Her malloc çağrısından sonra NULL denetimi yapılır. İlk blok alınamazsa yapılacak bir şey yoktur; yordam NULL döndürür. İkinci blok alınamazsa durum daha incedir. Bu noktada yapı için ayrılmış bir blok vardır. Yordam doğrudan NULL döndürse o blok kimsenin elinde kalmaz ve bir daha geri verilemez. Bu bir bellek sızıntısıdır (memory leak). Kod bu yüzden önce free(k) ile yarım kurulmuş yapıyı geri verir, sonra NULL döndürür. Son döngü her öğeyi tek öğeli bir küme yapar: başlangıçta bütün hücreler −1'dir.

kumeler_sil blokları ayrılma sırasının tersiyle geri verir. Önce iç dizi, sonra yapı serbest bırakılır. Sıra ters olsaydı, yani önce free(*kp) çağrılsaydı, (*kp)->ata ifadesi geri verilmiş bir bloğu okurdu. Bu tanımsız davranıştır. Yordam parametre olarak işaretçiye işaretçi (pointer to pointer) alır: kumeler **kp. Böylece son satırda çağıranın kendi değişkenine NULL yazabilir. Çağıran kumeler_sil(&k) dedikten sonra k artık NULL'dır. Yanlışlıkla ikinci kez kumeler_sil(&k) çağrılırsa ilk satırdaki denetim yüzünden hiçbir şey olmaz. Parametre yalnız kumeler *k olsaydı yordam kendi kopyasını NULL yapabilirdi, çağıranın k'sı ise geri verilmiş bloğu göstermeye devam ederdi. Böyle bir işaretçiye sarkan işaretçi (dangling pointer) denir.

Bu iki yordam sayaçlı bir malloc/free sarmalayıcısıyla denendi: oluşturma ve silme sonunda 2 ayırma ve 2 geri verme sayıldı, sızıntı görülmedi. Notun geri kalanında, sunumla aynı kalmak için yordamlar küresel ata dizisini kullanır. Dinamik yapıya geçmek için her yordama kumeler *k parametresi eklenir ve ata[i] yerine k->ata[i] yazılır; mantık hiç değişmez.

16.2.4İlk sürüm: Kume_Bul_1 ve Birlesim_1

İlk sürüm, modelin en doğrudan C karşılığıdır:

int Kume_Bul_1(int i) {
  for (; ata[i] >= 0; i = ata[i])
    ;                /* negatife dek ilerle */
  return i;
}
void Birlesim_1(int i, int j) {
  ata[i] = j;        /* i kümesini j'ye bağla */
}

Kume_Bul_1 tek bir for döngüsüdür. Döngünün başlatma kısmı boştur, çünkü başlangıç düğümü zaten i parametresidir. Koşul ata[i] >= 0, “i bir kök değil” demektir. Koşul doğru oldukça i = ata[i] ile bir üst düğüme çıkılır. Döngünün gövdesi boştur; tek başına duran noktalı virgül bunu gösterir. Bütün iş koşul ve güncelleme kısımlarında yapılır. Döngü ebeveyn bilgisi negatif olan ilk düğümde, yani kökte durur. Yordam bu kökü döndürür.

Boş gövdeli döngü C'de yaygın bir kalıptır, ama okuması kolay değildir. Noktalı virgülün ayrı bir satıra yazılması ve yanına açıklama konması bilinçli bir seçimdir. Noktalı virgül for satırının sonuna bitişik yazılsaydı, okuyan biri onu bir yazım hatası sanabilirdi.

Birlesim_1 tek bir atamadır: ata[i] = j. i kökünün ebeveyni artık j'dir; i'nin ağacı bütünüyle j'nin altına girer. Yordamın bir ön koşulu vardır: i ve j farklı kümelerin kökleri olmalıdır. Kök olmayan bir öğe verilirse önce Kume_Bul_1 ile kökü bulunur. Koşul bozulursa ya bir ağaç ikiye bölünür ya da kök kendini gösterir ve bulma yordamı sonsuz döngüye girer.

Maliyetler açıktır. Birlesim_1 tek atama yapar: Θ(1). Kume_Bul_1(i), i'den köke giden yoldaki her kenar için döngüyü bir kez döner. i'nin köke uzaklığı d ise d ilerleme ve d + 1 karşılaştırma yapar: Θ(d + 1). Bu notta “ilerleme” sözcüğü i = ata[i] atamasının bir kez yapılması anlamında kullanılır. En kötü durumda d, ağacın en derin düğümünün köke uzaklığıdır. Ek bellek her iki yordamda da O(1)'dir: yalnız i değişkeni kullanılır.

16.2.5Kod izleme

Örnek ormanda sırasıyla Kume_Bul_1(9), Birlesim_1(4, 0) ve yeniden Kume_Bul_1(9) çağrılsın. Tablo 16.4 her adımda i'nin ve dizinin durumunu verir. Şekil 16.4'te üç önemli an çizilmiştir.

İlk çağrı tek ilerlemeyle 4'e ulaşır: 9, 4 nolu kümededir. Birleşim yalnız bir hücreyi değiştirir. Ama bu tek atama, 4'ün altındaki bütün düğümlerin köke uzaklığını bir artırır. İkinci bulma çağrısı bu yüzden iki ilerleme yapar ve 0'ı döndürür: artık 9, 0 nolu kümededir. Bulmanın maliyeti, aranan düğümün derinliğine eşittir. Birleşim ucuzdur, ama bedeli sonraki bulma işlemlerine yansır.

Tablodaki değerler sunumdaki kodla derlenen bir sürücüyle doğrulandı: ilk çağrı 4'ü, ikinci çağrı 0'ı döndürdü. Aynı sürücüde Kume_Bul_1(8) == Kume_Bul_1(6) karşılaştırması da 1 (doğru) verdi.

16.3İlk sürümün analizi

Bir algoritmanın doğru olması yetmez. Etkili olmalı ve yazılım mühendisliğinin kurallarına göre yazılmalıdır. Bunlar da yetmez: hangi verinin algoritmayı en çok zorlayacağı sorulmalıdır. Arka planda ne olursa olsun kod en fazla ne kadar çalışır? Bu soruyu sormak ve cevaplamak, bir programlama dilini bilen biriyle bilgisayar mühendisini ayıran şeydir. İşveren “hepiniz C biliyorsunuz, aynı maaşı alın” derse mühendisin cevabı hazırdır: bir problem verilsin, nasıl çözüldüğüne ve çözümün en kötü durumda ne kadar sürdüğüne bakılsın.

16.3.1Kötü işlem dizisi

Tek öğeli n kümeyle başlayalım: S_i = {i}, her i için ata[i] = −1. Ardından şu işlem dizisi uygulansın:

/* n tek öğeli kümeyle başla */
Birlesim_1(0, 1);
Birlesim_1(1, 2);
...
Birlesim_1(n-2, n-1);
Kume_Bul_1(0);
Kume_Bul_1(1);
...
Kume_Bul_1(n-1);

Her birleşim, bir önceki adımda oluşan ağacın kökünü yeni bir tek öğeli kümenin altına bağlar. Birlesim_1(0, 1) 0'ı 1'in altına koyar. Birlesim_1(1, 2) 1'i, dolayısıyla 0 ile 1'den oluşan ağacı, 2'nin altına koyar. Her birleşimin iki parametresi de gerçekten köktür; ön koşul bozulmaz. Ama ağaç her adımda bir düzey uzar. Şekil 16.5 n = 5 için sonucu gösterir.

Birleşimlerin her biri sabit sürer. Sorun bulma işlemlerinde ortaya çıkar. Tablo 16.5, zincir üzerinde Kume_Bul_1(0)'dan Kume_Bul_1(4)'e kadar her çağrının kaç ilerleme yaptığını verir.

16.3.2Toplam maliyet

Tablodaki örüntü her n için aynıdır. Zincirde i düğümü (n − i). düzeydedir. Kökten n − 1 − i kenar uzaktadır.

Tek bir Kume_Bul_1 en kötü durumda O(n) sürer; n tanesi toplamda O(n²)'ye çıkar. Bu, union-find'ın kullanıldığı milyonlarca öğeli problemlerde kabul edilemez. Tablo 16.6'daki ölçüm büyümeyi somutlaştırır. n iki katına çıkınca ilerleme sayısı ve süre yaklaşık dört katına çıkar; bu karesel büyümenin belirtisidir.

Bu işlem dizisi ağacın yapısını bozar. Ama suçlu birleşim işleminin kendisi değildir. Asıl sorun, birleşimde hangi ağacın hangisinin altına bağlandığıdır. Her adımda büyük ağaç (zincir) tek düğümlü küçük ağacın altına bağlanmıştır. Sıra ters olsaydı, yani her yeni düğüm büyük ağacın köküne bağlansaydı, ağaç hep iki düzeyli kalırdı. Tablonun son sütunu bunu gösterir: aynı birleşim istekleri ağırlıklı kuralla yapılınca ağaç iki düzeyde kalır ve n bulmanın toplamı yalnız n − 1 ilerlemedir. Ağırlıklı kural tam olarak bu fikre dayanır.

16.3.3En kötü durumu test etmek

En kötü durum analizinde kod, çakılacağı ya da işletiminin en uzun süreceği verilerle sınanmalıdır. Bu verileri saptamak zordur. Zincir üreten birleşim sırası Kume_Bul_1 için tam da böyle bir girdidir. Rastgele testler onu kolayca kaçırır. Rastgele seçilen iki öğenin kökleri birleştirildiğinde ağaçlar zincir gibi uzamaz. Ölçümde n = 100.000 öğe üzerinde 200.000 rastgele işlem yapıldı; her işlemde iki bulma, işlemlerin yarısında da birleşim vardı. İlk sürüm bulma başına ortalama 1.108 ilerleme yaptı ve en derin düğüm 10.130. düzeydeydi. Bu kötü bir sonuçtur, ama zincirin n düzeyinden yine de çok uzaktır. Programı yalnız rastgele verilerle deneyen biri gerçek en kötü durumu hiç görmeyebilir.

Yazılım dünyasında “beta sürümü” denen şey bu zorluğun açık bir kabulüdür. Üretici kullanıcıya şunu söyler: gözden kaçırdığımız hatalar olabilir, bulursanız bildirin ki düzeltelim. Yazılım testi (software testing) başlı başına bir alandır ve üzerine çok sayıda makale yazılmıştır. Bu bölümün dersi daha basittir: bir yordam yazılınca onu en çok zorlayacak girdi düşünülmeli ve o girdiyle de denenmelidir.

16.4Ağırlıklı kural

16.4.1Kural

Birleşimde bir ağacın kökü ötekinin altına girer. Altına giren ağacın bütün düğümlerinin köke uzaklığı 1 artar. Öteki ağacın düğümleri ise yerinde kalır. Maliyeti düşük tutmak için uzaklığı artan düğüm sayısı az olmalıdır. Öyleyse az düğümlü ağaç, çok düğümlü ağacın altına bağlanmalıdır.

Şekil 16.6 kuralın etkisini gösterir. 0 kökünde beş düğümlü bir ağaç ve 5 kökünde iki düğümlü bir ağaç birleştiriliyor. Soldaki birleşimde küçük ağaç büyüğün altına girer; yalnız 5 ile 6'nın köke uzaklığı artar ve ağaç 3 düzeyli kalır. Sağdaki birleşimde büyük ağaç küçüğün altına girer; beş düğümün uzaklığı birden artar ve ağaç 4 düzeye çıkar.

Kuralı uygulamak için her ağacın düğüm sayısını bilmek gerekir. Bunun için ayrı bir dizi mi tutulmalı? Gerek yoktur. Kök dışındaki bütün düğümler için ebeveyn dizisinde 0 ya da pozitif değerler durur. Kökler ise yalnız “ben köküm” demek için negatif bir değer taşır ve bu değerin büyüklüğü şimdiye kadar hiç kullanılmamıştır. Öyleyse kökün düğüm sayısı, ebeveyn dizisinde negatif işaretle saklanabilir. Kökte −1 yerine −(düğüm sayısı) yazılır. İşaret “kök” bilgisini, mutlak değer “boyut” bilgisini taşır.

16.4.2Birlesim_2: kökte eksi düğüm sayısı

void Birlesim_2(int i, int j) {
  /* ağırlıklı kural; i ve j kök olmalı */
  int p = ata[i] + ata[j];  /* -(toplam düğüm) */
  if (ata[i] > ata[j]) {    /* i'de daha az düğüm */
    ata[i] = j;             /* i'yi j'ye bağla */
    ata[j] = p;             /* j'nin sayısını günle */
  } else {                  /* j'de az ya da eşit */
    ata[j] = i;
    ata[i] = p;
  }
}

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

• 3. satır. p = ata[i] + ata[j]. İki kökteki değerler negatif düğüm sayılarıdır. Toplamları, birleşik ağacın düğüm sayısının negatifidir. 3 düğümlü ve 5 düğümlü ağaç için p = −3 + (−5) = −8 olur.
• 4. satır. ata[i] > ata[j] karşılaştırması ilk bakışta ters görünür. Değerler negatif olduğu için büyük olan değer küçük boyutu gösterir: −2 > −4, 2 düğümün 4 düğümden az olduğunu söyler. Koşul doğruysa i'nin ağacında daha az düğüm vardır.
• 5–6. satırlar. i küçük olduğu için j'nin altına bağlanır: ata[i] = j. Yeni kök j'dir ve hücresine birleşik düğüm sayısı yazılır: ata[j] = p.
• 7–10. satırlar. Aksi durumda, yani j'de daha az ya da eşit düğüm varsa, j i'nin altına girer ve i'nin hücresi p olur. Eşitlikte j'nin bağlanması keyfî bir seçimdir; iki seçim de kuralı sağlar.

Atamaların sırası önemlidir. 3. satırda p hesaplanmadan önce iki hücreden biri değiştirilseydi, düğüm sayısı bilgisi kaybolurdu. Örneğin önce ata[i] = j yazılsa, ata[i] artık i'nin düğüm sayısını değil, j'nin numarasını taşırdı. Yordam bu yüzden toplamı en başta bir yerel değişkene alır.

Maliyet hâlâ Θ(1)'dir: bir toplama, bir karşılaştırma ve iki atama. Ek dizi gerekmez; düğüm sayıları zaten kullanılmayan bilgi alanında saklanır. Başlangıçta bütün hücrelerin −1 olması yeni anlama da uyar: tek öğeli bir kümede bir düğüm vardır.

Kume_Bul_1 değişmeden kalır. Onun tek ilgilendiği, değerin negatif olup olmadığıdır; −1 ile −8 arasında bir fark gözetmez. Bu, gösterim seçiminin güzel bir sonucudur: kökte saklanan ek bilgi, bulma yordamını hiç etkilemez.

16.4.3Kod izleme

Sekiz tek öğeli kümeyle başlayalım. Önce komşu çiftler birleştirilsin: Birlesim_2(0, 1), (2, 3), (4, 5), (6, 7). Sonra iki düğümlü ağaçlar ikişer ikişer: (0, 2), (4, 6). En son dört düğümlü iki ağaç: (0, 4). Her birleşimde iki ağaç eşit büyüklüktedir. Tablo 16.7 her adımdaki değerleri verir.

Her satırda koşul yanlıştır, çünkü iki kökteki değerler eşittir: −1 > −1, −2 > −2 ve −4 > −4 ifadelerinin hiçbiri doğru değildir. Bu yüzden her seferinde else dalı çalışır ve j, i'nin altına girer. Düzey sayısı yalnız eşit büyüklükteki iki ağaç birleşince artar: 2, 3 ve 4. Sekiz düğümlü ağacın 4 düzeyi vardır. Bu, Teorem 16.2'nin verdiği sınırın tam değeridir: ⌊lg 8⌋ + 1 = 4.

Son durumda en derin düğüm 7'dir: 7 → 6 → 4 → 0 yolu üç ilerleme ister. Tablodaki bütün diziler sunumdaki Birlesim_2 koduyla derlenen sürücünün çıktısıyla aynıdır.

16.4.4Derinlik lemması

Ağırlıklı kural ağacı ne kadar bozabilir? İzlemedeki işlem dizisi bu kural için en kötü durumdur: her seferinde eşit büyüklükte iki ağaç birleşir. Her birleşimde küçük ağacın bütün düğümlerinin derinliği 1 artar, ama ağaç en az iki katına çıkar. İkinci gözlem birincisini sınırlar.

Kanıtın özü şudur. Bir düğümün derinliği yalnız onun ağacı daha küçük ya da eşit bir ağaca bağlanınca 1 artar. O anda düğümün içinde bulunduğu ağaç en az iki katına çıkar. m düğüme en çok lg m kez iki katına çıkılabilir. Öyleyse hiçbir düğümün derinliği lg m'den fazla artamaz.

Sınır sıkıdır, yani daha iyisi söylenemez. Eşit ikililerle kurulan ağaç onu her m = 2^k için tam olarak yakalar. Ölçümde 16 düğümde 5 düzey, 2²⁰ = 1.048.576 düğümde 21 düzey elde edildi; ikisi de ⌊lg m⌋ + 1'e eşittir. Rastgele birleşimlerde ağaçlar sınırın çok altında kalır: 10⁶ öğede sınır 20 iken en derin düğüm 9. düzeydeydi.

Sonuç büyük bir kazançtır. Tek bir bulmanın en kötü maliyeti O(n)'den O(lg n)'ye düştü. Bir milyon öğede bu, bir milyon ilerleme yerine en çok 19 ilerleme demektir. n − 1 birleşim ve m bulmadan oluşan bir dizinin toplam maliyeti O(n + m lg n) olur. Matematik bölümünde soru burada “kanıtlayınız” diye devam ederdi. Mühendis için asıl önemli olan, karmaşıklığın n'den ⌊lg n⌋ + 1'e inmesidir. Algoritma geliştirmek budur. Ama burada durulmaz; bir adım daha atılabilir.

16.4.5Herhangi iki öğeyi birleştirmek

Birlesim_1 ve Birlesim_2 kök ister. Uygulamada ise “3 ile 8'i aynı kümeye koy” gibi istekler gelir ve 3 ile 8 kök olmayabilir. Bu boşluğu dolduran küçük bir sarmalayıcı yordam yazılabilir:

int birlestir(int x, int y) {   /* x ve y herhangi iki öğe */
  int a = Kume_bul_2(x);         /* x'in kökü */
  int b = Kume_bul_2(y);         /* y'nin kökü */
  if (a == b) return 0;          /* zaten aynı kümede */
  Birlesim_2(a, b);              /* iki kökü birleştir */
  return 1;
}

Yordam önce iki öğenin köklerini bulur. Kökler aynıysa öğeler zaten aynı kümededir ve hiçbir şey yapılmaz; dönüş değeri 0'dır. Farklıysa iki kök Birlesim_2'ye verilir ve 1 döndürülür. Dönüş değeri, çağıranın “bu istek yeni bir birleşim yaptı mı?” sorusunu cevaplar. Bu bilgi bileşen saymada ve Kruskal algoritmasında doğrudan kullanılır. Yordamda kullanılan Kume_bul_2, azaltma kuralını uygulayan bulma sürümüdür (Tanım 16.4); onun yerine Kume_Bul_1 da konabilir. Maliyet iki bulmanın maliyetine eşittir, birleşimin katkısı sabittir.

“Kökler aynı mı?” denetimi bir güvenlik önlemidir. Aynı kökle Birlesim_1(r, r) çağrılırsa ata[r] = r olur: kök kendini gösterir. Ardından gelen her Kume_Bul_1 bu düğümde sonsuza dek döner, çünkü ata[r] ≥ 0 koşulu hiç yanlış olmaz. Denemede döngü bir milyon adımda kesildi. Birlesim_2(r, r) ise başka türlü bozulur: p = 2 · ata[r] hesaplanır, koşul yanlış çıkar, önce ata[r] = r sonra ata[r] = p yazılır. Sonuçta kök kök olarak kalır, ama düğüm sayısı iki katına çıkmış görünür. Üç öğeli bir denemede Birlesim_2(1, 1) sonrası dizi [−1, −2, −1] oldu: tek öğeli küme 2 öğeli sanılıyor. Bu yanlış sayı sonraki birleşimlerde ağırlıklı kuralı yanıltır.

16.5Azaltma kuralı

16.5.1Kural

Ağırlıklı kuralla kurulan sekiz düğümlü ağaçta (Şekil 16.7'nin alt kısmı) Küme_bul(7) köke üç ilerlemede ulaşır. Program Küme_bul(7)'yi tekrar tekrar çağırırsa her çağrı aynı üç adımı yeniden yürür ve maliyet katlanır. Düğüm sayısı az olanı çok olana eklemek derinliği lg n ile sınırlar, ama derinliğin artmasını tamamen engellemez. Derinliği birleşim anında daha fazla denetleyemediğimize göre başka bir fırsat aranır: bulma işlemi zaten yolu baştan sona yürür. Yürürken yolu kısaltabilir.

Kural, ağaçların “anlamsız” yerleşiminden yararlanır. Bir öğenin ağaçtaki yeri hiçbir bilgi taşımaz; önemli olan yalnız hangi köke ulaştığıdır. 7'nin 6'nın altında ya da doğrudan 0'ın altında durması kümeleri değiştirmez. Değişen yalnız sonraki bulmaların maliyetidir. Çizge kuramında aynı düşünce “kapama” (closure) adıyla geçer: dolaylı bir bağlantı, doğrudan bir kenarla kısaltılır. Problemler farklı olsa da alttaki yapı aynıdır ve bu benzerlik çizge problemlerinde sık sık işe yarar.

16.5.2Kume_bul_2

int Kume_bul_2(int i) {
  int r, s;
  for (r = i; ata[r] >= 0; r = ata[r])
    ;                   /* kökü bul */
  while (i != r) {      /* yolu azalt */
    s = ata[i];         /* i'nin ebeveynini sakla */
    ata[i] = r;         /* i'yi doğrudan köke bağla */
    i = s;              /* ebeveynine geç */
  }
  return r;
}

Yordam yolu iki kez geçer.

• Birinci geçiş (2–4. satırlar). for döngüsü Kume_Bul_1'in yaptığını yapar, ama i'yi değiştirmeden ayrı bir r değişkeniyle yürür. Döngü bitince r köktür. i hâlâ başlangıç düğümünü gösterir; ikinci geçiş oradan başlayacaktır.
• İkinci geçiş (5–9. satırlar). while döngüsü i'den köke kadar yeniden yürür. Her turda üç iş yapılır. Önce s = ata[i] ile i'nin eski ebeveyni saklanır. Sonra ata[i] = r ile i doğrudan köke bağlanır. En son i = s ile saklanan ebeveyne geçilir. Döngü i köke ulaşınca biter.
• 10. satır. Kök döndürülür.

s değişkeni yordamın can alıcı parçasıdır. ata[i] = r ataması i'nin eski ebeveynini siler. Eski ebeveyn önceden saklanmazsa yolun devamı kaybolur; döngü bir sonraki düğüme geçemez. Bu tam olarak bağlı listeyi ters çevirirken bir sonraki düğümü saklama zorunluluğuna benzer: bir bağı değiştirmeden önce, o bağın gösterdiği yer bir değişkende tutulmalıdır.

İkinci döngünün bir küçük kusuru vardır. Köke zaten doğrudan bağlı bir düğüm için de bir kez çalışır ve ata[i] = r atamasıyla hücreye aynı değeri yeniden yazar. Bu gereksizdir ama zararsızdır. Yolun son düğümü her zaman köke bağlı olduğu için, kök dışında her çağrıda tam bir “fazladan tur” yapılır.

Maliyet analizi: başlangıç düğümünün köke uzaklığı d ise birinci döngü d, ikinci döngü de d tur döner. Tek çağrının maliyeti Θ(d + 1)'dir; yani tek başına Kume_Bul_1'in yaklaşık iki katıdır. Ağırlıklı kuralla birlikte d ≤ ⌊lg n⌋ olduğundan tek bir çağrı en kötü durumda O(lg n)'dir. Kazanç tek çağrıda değil, çağrı dizisinde görülür: yol üzerindeki bütün düğümler artık köke bir adım uzaklıktadır. Ek bellek O(1)'dir: r ve s.

Kökteki negatif sayı yol kısaltmada bozulmaz. Yalnız kök dışındaki düğümlerin hücreleri değişir ve kökün hücresine hiç yazılmaz. Ağaçtaki düğüm sayısı da değişmez, çünkü hiçbir düğüm ağaçtan çıkmaz. Ağırlıklı kural bu yüzden yol kısaltmayla birlikte sorunsuz çalışır.

16.5.3Kod izleme

Ağırlıklı izlemenin sonundaki ağaçla başlayalım: ata = [−8, 0, 0, 2, 0, 4, 4, 6]. Sırayla Kume_bul_2(7), yine Kume_bul_2(7) ve Kume_bul_2(5) çağrılsın. Tablo 16.8 ilk çağrıyı adım adım verir.

İkinci Kume_bul_2(7) çağrısı kısadır. ata[7] = 0 olduğu için birinci döngü tek ilerlemede kökü bulur. İkinci döngü de tek tur döner; bu tur yine “fazladan” turdur, çünkü 7 zaten köke bağlıdır. Dizi değişmez.

Kume_bul_2(5) ise yeni bir yol açar: 5 → 4 → 0. Birinci döngü iki ilerleme yapar. İkinci döngü 5'i köke bağlar (ata[5]: 4 → 0), sonra 4 için fazladan bir tur döner. Son durum ata = [−8, 0, 0, 2, 0, 0, 0, 0]'dır. Sekiz düğümün altısı artık köke doğrudan bağlıdır; yalnız 3, iki adım uzaktadır. Bütün diziler, sunumdaki kodla derlenen sürücünün çıktısıyla karşılaştırıldı.

16.5.4Bu nasıl iyileştirme?

İlk bakışta itiraz yerindedir: bir for döngüsü vardı, bir de while döngüsü eklendi. Bu nasıl iyileştirme olur? Cevap tek çağrıya değil, çağrı dizisine bakınca görülür. Kume_bul_2(7) ikinci kez çağrılınca ve sonraki her çağrıda kökü bir çırpıda bulur. Tablo 16.9 iki sürümün maliyetini aynı ağaç üzerinde karşılaştırır.

İlk çağrı yaklaşık iki kat pahalıdır: 3 yerine 6 adım. İkinci çağrı ise 3 yerine 2 adım sürer. On çağrıda toplam 30'a karşı 24 olur ve fark çağrı sayısıyla büyür. Bin çağrıda Kume_Bul_1 3.000 ilerleme yapar, Kume_bul_2 ise 6 + 999 · 2 = 2.004 adımda kalır. Yolu kısaltmanın bedeli bir kez ödenir, getirisi her sonraki çağrıda toplanır.

Bu tür bir hesaba amortize analiz (amortized analysis) denir. Tek bir işlemin en kötü maliyeti yerine, uzun bir işlem dizisinin toplam maliyeti işlem sayısına bölünür. Pahalı işlemler arada bir olur ve arkalarından gelen işlemleri ucuzlatır. Maliyet birçok işlem üzerine yayılınca işlem başına neredeyse sabite iner.

Yol kısaltmanın etkisi en açık biçimde ağırlıklı kuralın en kötü ağacında görülür. Eşit ikililerle kurulan 2²⁰ düğümlü ağaçta (21 düzey) 2²⁰ rastgele bulma yapıldı. Yalnız ağırlıklı kuralla bulma başına ortalama 10,00 ilerleme ölçüldü; ağaç değişmediği için bu sayı hiç azalmaz. Yol kısaltmayla ortalama 1,78 ilerlemeye düştü ve ağacın düzey sayısı 21'den 6'ya indi. Süre de 0,18 saniyeden 0,03 saniyeye indi (makineye göre değişir).

16.5.5Özyinelemeli yol kısaltma

Yol kısaltma özyinelemeyle tek satırda da yazılabilir:

int bul(int i) { return ata[i] < 0 ? i : (ata[i] = bul(ata[i])); }

Okuması şöyledir. i kökse (ata[i] < 0) kendisi döndürülür. Değilse önce ebeveyninin kökü özyinelemeyle bulunur: bul(ata[i]). Dönen kök ata[i]'ye yazılır ve aynı değer döndürülür. Atama ifadesinin değeri, atanan değerdir; (ata[i] = bul(ata[i])) bu yüzden hem bağı günler hem de kökü verir.

Özyineleme yolu kökten geriye doğru kısaltır. Çağrılar köke kadar iner, dönüşte her çerçeve kendi düğümünü köke bağlar. bul(7) sekiz düğümlü örnek ağaçta bul(6)'yı, o bul(4)'ü, o da bul(0)'ı çağırır. bul(0) 0 döndürür. Dönüşte sırasıyla ata[4] = 0, ata[6] = 0 ve ata[7] = 0 yazılır. Sonuç Kume_bul_2(7) ile aynıdır: [−8, 0, 0, 2, 0, 4, 0, 0]. bul(5) ardından [−8, 0, 0, 2, 0, 0, 0, 0] verir; bu da aynıdır.

İki sürümün farkı belleğe ilişkindir. Döngülü Kume_bul_2 O(1) ek bellek kullanır. Özyinelemeli bul ise yol uzunluğu kadar çağrı çerçevesi açar: O(d). Ağırlıklı kuralla d ≤ lg n olduğundan bu bir sorun değildir; bir milyar öğede bile en çok 30 çerçeve açılır. Ama ağırlıksız birleşimle kurulmuş bir zincirde d, n'ye ulaşabilir ve çağrı yığını taşabilir.

16.6Tarjan–van Leeuwen sonucu ve Ackermann fonksiyonu

16.6.1Neredeyse sabit maliyet

İki kural birlikte kullanılınca maliyet ne olur? Ağırlıklı kural tek bir bulmayı O(lg n) ile sınırlar. Azaltma kuralı ise yolları kısalttığı için tekrarlanan bulmaları ucuzlatır. Bu ikisinin birleşik etkisini kesin olarak hesaplamak kolay değildir. Soruyu R. E. Tarjan ile J. van Leeuwen 1984'te kapattı.

Teorem iki şey söyler. Üst sınır, işlemlerin toplam maliyetinin n + f · α ile orantılı olduğunu gösterir. Alt sınır ise bundan daha iyisinin bu iki kuralla mümkün olmadığını söyler; analiz sıkıdır. Teoremin kanıtı bu notun kapsamını aşar. Ama sonucu yorumlamak için yalnız α'nın ne kadar yavaş büyüdüğünü bilmek yeter. α o kadar yavaş büyür ki evrendeki atom sayısı kadar öğe için bile değeri 4'ü geçmez. Toplam maliyet işlem sayısına bölününce işlem başına maliyet neredeyse O(1) çıkar.

Bir milyon öğe düşünelim. Bir program bir öğenin kümesini neredeyse sabit sürede buluyor, öteki hâlâ listeleri tek tek tarıyor. İkisi de doğru sonuç verir, ama biri saniyenin küçük bir kesrinde biter, öteki dakikalarca çalışır. Aynı işe başvuran matematikçi ile mühendisin farkı da budur: mühendis doğru sonucun yanında maliyeti de sorgular.

16.6.2Ackermann fonksiyonu

α'yı anlamak için önce tersi alınan fonksiyona bakmak gerekir. Ackermann fonksiyonu iki doğal sayı argümanlı, özyinelemeyle tanımlı ve son derece hızlı büyüyen bir fonksiyondur.

/* Ackermann: çok hızlı büyür */
A(m, n) = n + 1                  m = 0
        = A(m-1, 1)              m > 0, n = 0
        = A(m-1, A(m, n-1))      m > 0, n > 0

Tanım üç durumdan oluşur. m = 0 ise sonuç n + 1'dir; özyineleme burada biter. n = 0 ise birinci argüman bir azalır, ikinci argüman 1 olur. Üçüncü durum en ilginç olanıdır: dış çağrının ikinci argümanı bir iç çağrının sonucudur. İç çağrı A(m, n − 1), dış çağrı A(m − 1, …)'dir. Her adımda ya m küçülür ya da m aynı kalıp n küçülür. Bu yüzden özyineleme her zaman biter; ama ne zaman bittiği başka bir sorudur.

Satırların her biri bir öncekinin yinelenmesidir ve bu yüzden kapalı biçimleri vardır. A(1, n) = n + 2, A(2, n) = 2n + 3 ve A(3, n) = 2ⁿ⁺³ − 3'tür. m = 3 satırında değerler üstel büyür. m = 4 satırında ise üs kulesi başlar: A(4, 1) = 2¹⁶ − 3 = 65533, A(4, 2) = 2⁶⁵⁵³⁶ − 3. İkincisi yaklaşık 19.729 basamaklı bir sayıdır. A(5, 1) ise 65536 tane 2'den oluşan bir üs kulesinin 3 eksiğidir; akıl almaz büyüklükte bir sayıdır.

Ackermann fonksiyonunun birden çok tanımı vardır. Yukarıdaki tanımla A(3, 4) = 125'tir. Horowitz'in kitabında kullanılan ve Tarjan'ın çalışmasından gelen tanımda ise A(1, j) = 2^j ile başlanır ve A(3, 1) = 16 çıkar. Hangi tanım seçilirse seçilsin varılan sonuç değişmez: hepsi aynı ölçüde hızlı büyür ve uygulamada α ≤ 4'tür.

16.6.3Ters Ackermann fonksiyonu

A çok hızlı büyüdüğü için onu belli bir değerin üstüne çıkarmaya yetecek i çok küçüktür. Bu yüzden α çok yavaş büyür. Hesabı yapalım. m ≥ n olduğundan ⌊m/n⌋ ≥ 1'dir ve A(i, ⌊m/n⌋) ≥ A(i, 1) olur. Tablodan A(1, 1) = 3, A(2, 1) = 5, A(3, 1) = 13 ve A(4, 1) = 65533'tür. Öyleyse:

• n ≤ 2³ = 8 için lg n ≤ 3 ve α ≤ 1'dir.
• n ≤ 2⁵ = 32 için α ≤ 2'dir.
• n ≤ 2¹³ = 8192 için α ≤ 3'tür.
• n ≤ 2⁶⁵⁵³³ için α ≤ 4'tür.

Gözlenebilir evrendeki atom sayısının yaklaşık 10⁸⁰, yani kabaca 2²⁶⁶ olduğu tahmin edilir. 2⁶⁵⁵³³ bundan akıl almaz ölçüde büyüktür. Bilgisayarlarda karşılaşılabilecek her n için α ≤ 4'tür. Bir Python betiğiyle tanımdan hesaplanan değerler bu eşikleri doğruladı: n = 8'de 1, n = 9 ve 32'de 2, n = 33 ve 8192'de 3, n = 8193, 10⁶ ve 2⁶⁴'te 4.

Kuramsal olarak α sınırsız büyür; bu yüzden O(α) sabit değildir ve “union-find işlemleri O(1)'dir” demek kesin olarak doğru değildir. Uygulamada ise α en çok 4 olan bir çarpandır. Doğru ifade “neredeyse sabit” ya da “uygulamada doğrusal toplam maliyet”tir.

16.6.4Özyinelemeli Ackermann ve çağrı yığını

Ackermann fonksiyonu, özyinelemenin gücünü ve çağrı yığınının sınırlarını göstermek için sevilen bir sınav sorusudur. Sorulan şudur: fonksiyonu özyinelemeli olarak yazınız; ardından A(1, 2) çağrısının çağrı yığınını adım adım gösteriniz. C karşılığı tanımın doğrudan çevirisidir:

unsigned long ackermann(unsigned long m,
                        unsigned long n) {
  if (m == 0) return n + 1;
  if (n == 0) return ackermann(m - 1, 1);
  return ackermann(m - 1, ackermann(m, n - 1));
}

Tanımın üç durumu üç satıra karşılık gelir. Sonuçlar hızla büyüdüğü için tip olarak unsigned long seçilmiştir; negatif değer hiç oluşmaz. Windows'ta unsigned long 32 bittir, Linux'ta 64 bit. A(4, 1) = 65533 iki tipe de sığar; A(4, 2) ise hiçbir tamsayı tipine sığmaz.

A(1, 2)'nin açılımı şöyledir:

A(1,2) = A(0, A(1,1)) = A(0, A(0, A(1,0))) = A(0, A(0, A(0,1))) = A(0, A(0, 2)) = A(0, 3) = 4

Sayaçlı bir sürümle yapılan ölçüm, A(1, 2)'nin toplam 6 çağrı yaptığını ve yığının en çok 4 çerçeve derinleştiğini gösterdi. Bu, tablodaki altı farklı çağrıyla (A(1,2), A(1,1), A(1,0), A(0,1), A(0,2), A(0,3)) uyumludur. Sayılar hızla büyür: A(2, 2) 27 çağrı ve 8 derinlik, A(3, 3) 2.432 çağrı ve 63 derinlik, A(4, 0) 107 çağrı ve 16 derinlik ister. Aynı sayma kuralıyla Python'da yapılan hesaba göre A(4, 1) 2.862.984.010 çağrı ister ve yığın 65.536 çerçeveye kadar derinleşir. Böyle bir derinlik varsayılan çağrı yığınını kolayca aşabilir. A(4, 2) ise hiçbir bilgisayarda bitmez; sonucun basamakları bile belleğe sığmaz.

16.6.5Ölçümle karşılaştırma

Üç sürüm aynı rastgele işlem dizisiyle karşılaştırıldı. Her işlemde iki rastgele öğenin kökü bulundu; işlemlerin yarısında, kökler farklıysa, iki küme birleştirildi. Tablo 16.12 sonuçları verir.

Rastgele işlemlerde ilk sürüm bile zincirin n düzeyine ulaşmaz, ama bulma başına bin adımı aşar. Ağırlıklı kural bunu bin kattan fazla azaltır. Rastgele girdide ağırlıklı ağaçlar zaten sığ olduğu için yol kısaltmanın katkısı burada küçüktür: ilerleme 0,90'dan 0,61'e iner. Bağlama turları da sayılınca toplam iş biraz artar (100.000 öğede yaklaşık 360 bine karşı 492 bin adım), süre ise hemen hemen aynı kalır. Yol kısaltmanın asıl değeri, aynı derin yolların tekrar tekrar yüründüğü kötü durumlarda görülür. Eşit ikililerle kurulan ağaçtaki ölçüm bunu göstermişti: bulma başına 10,00 ilerleme 1,78'e indi.

16.6.6Bu sonuçlar nereden geliyor?

Tarjan, çizge algoritmaları üzerine birçok temel sonucun sahibi ünlü bir bilgisayar bilimcisidir. Bu teorem onun J. van Leeuwen ile ortak çalışmasından çıkmıştır (1984). Bu tür sonuçlar araştırmanın ürünüdür. Lisans eğitiminde dört yıl okunur ve bir meslek kazanılır. Doktorada ise çoğu zaman yalnız bir problem üzerine dört yıl çalışılır ve dünyada henüz çözülmemiş bir soruya cevap aranır. Böyle bir çalışma tek başına değil, bir grup içinde yürütülür; grupta çalışan kişi sürekli öğrenir.

Bu konuların bir haftada bitmesi beklenmemelidir; hiç çalışılmazsa hiç bitmez. Her gün düzenli olarak iki üç saat çalışmak ve haftanın konusunu aynı hafta tekrar etmek, konuların birikmesini önler. Union-find gibi kısa ama derin bir yapı, bu tekrar sırasında küçük örnekleri elle izleyerek en iyi öğrenilir.

16.7Uygulamalar

16.7.1Bağlantılı bileşen sayma

Yönsüz bir çizgede birbirine bir yolla ulaşılabilen düğümlerin oluşturduğu en büyük gruplara bağlantılı bileşen (connected component) denir. Bileşenler düğüm kümesini ayrık parçalara böler; bu yüzden union-find'ın doğal bir uygulamasıdır. Başlangıçta her düğüm ayrı bir bileşendir. Her kenar, iki ucunun bulunduğu bileşenleri birleştirir. Bütün kenarlar işlenince kalan küme sayısı bileşen sayısıdır.

int bilesen_say(int n, int m, int u[], int v[]) {
  for (int i = 0; i < n; i++) ata[i] = -1;
  int sayi = n;               /* her düğüm ayrı */
  for (int e = 0; e < m; e++) {
    int a = Kume_bul_2(u[e]), b = Kume_bul_2(v[e]);
    if (a != b) {             /* farklı bileşen */
      Birlesim_2(a, b);
      sayi--;
    }
  }
  return sayi;
}

Yordam n düğümlü ve m kenarlı bir çizgeyi iki dizi olarak alır: e. kenar u[e] ile v[e] düğümlerini bağlar. İlk satır ebeveyn dizisini sıfırdan kurar; her düğüm tek öğeli bir kümedir. sayi değişkeni bileşen sayısını tutar ve n ile başlar. Döngü her kenar için iki ucun kökünü bulur. Kökler farklıysa kenar iki ayrı bileşeni birleştirir: kökler Birlesim_2 ile birleştirilir ve bileşen sayısı bir azalır. Kökler aynıysa kenarın iki ucu zaten aynı bileşendedir; kenar bir döngü kapatır ve sayı değişmez.

Örnek çizgede 6 düğüm ve 4 kenar vardır: (0, 1), (2, 3), (1, 4) ve (3, 2). Son kenar, 2 ile 3 arasındaki ikinci bir kenardır. Tablo 16.13 izlemeyi verir.

Üçüncü kenarda ilginç bir an vardır. Kenar (1, 4)'tür, ama 1 kök değildir. Kume_bul_2(1), 1'in kökü olan 0'ı döndürür ve birleşim 0 ile 4 arasında yapılır. 0'ın ağacında iki, 4'ünkünde bir düğüm vardır; −2 > −1 yanlış olduğu için 4, 0'ın altına girer. Dördüncü kenarın iki ucu da 2 köküne ulaşır ve kenar atlanır. Sonuç 3'tür: {0, 1, 4}, {2, 3}, {5}. Yordam sunumdaki kodla derlenip çalıştırıldı; 3 döndürdü ve son dizi [−3, 0, −2, 2, 0, −1] oldu.

Maliyet: ilk döngü Θ(n)'dir. Kenar döngüsü m kez döner; her turda iki bulma ve en çok bir birleşim yapılır. Teorem 16.3'e göre toplam O(n + m · α(m + n, n)) olur; uygulamada bu doğrusaldır. Bellek n tamsayılık ebeveyn dizisidir. Çizgenin bağlantı listesi kurulmaz; kenarlar okunurken işlenebilir. Bu özellik, kenarları bir dosyadan ya da ağdan sırayla gelen çok büyük çizgelerde union-find'ı derinlik öncelikli aramaya göre çekici kılar.

16.7.2Eşdeğerlik sınıfları

Bir bağıntı yansıyan (x ≡ x), simetrik (x ≡ y ise y ≡ x) ve geçişli (x ≡ y ve y ≡ z ise x ≡ z) ise eşdeğerlik bağıntısıdır. Eşdeğerlik bağıntısı, öğeleri eşdeğerlik sınıfları (equivalence classes) denen ayrık kümelere böler. Horowitz'in kitabındaki klasik problem şudur: i ≡ j biçiminde bir dizi bildirim verilmiştir; sınıfları bulunuz. Örneğin derleyicide hangi değişkenlerin aynı bellek alanını paylaştığını belirleyen EQUIVALENCE bildirimleri böyle işlenir.

Geçişlilik yüzünden bildirimler dolaylı sonuçlar doğurur: 7 ≡ 4 ve 0 ≡ 4 ise 7 ≡ 0'dır, bu ayrıca bildirilmese bile. Union-find bu dolaylı sonuçları kendiliğinden toplar. Her bildirim iki öğenin kümelerini birleştirir:

void esdegerlik(int n, int m, int x[], int y[]) {
  for (int i = 0; i < n; i++) ata[i] = -1;
  for (int k = 0; k < m; k++)
    birlestir(x[k], y[k]);          /* x[k] ≡ y[k] bildirimi */
  for (int r = 0; r < n; r++) {     /* her kök bir sınıf */
    if (ata[r] >= 0) continue;
    printf("{");
    for (int i = 0; i < n; i++)
      if (Kume_bul_2(i) == r) printf(" %d", i);
    printf(" }\n");
  }
}

12 öğe ve dokuz bildirimle deneyelim: 0 ≡ 4, 3 ≡ 1, 6 ≡ 10, 8 ≡ 9, 7 ≡ 4, 6 ≡ 8, 3 ≡ 5, 2 ≡ 11, 11 ≡ 0. Tablo 16.14 her bildirimden sonraki köklerini verir.

Beşinci bildirimde 4 artık kök değildir; kökü 0'dır. Son bildirimde ise 11'in kökü 2'dir. 2'nin ağacında iki, 0'ın ağacında üç düğüm olduğu için −2 > −3 doğrudur ve 2, 0'ın altına girer. Program üç sınıf yazdırır: { 0 2 4 7 11 }, { 1 3 5 } ve { 6 8 9 10 }. Bu çıktı C sürücüsüyle alındı.

Sınıfları yazdıran son döngü her kök için bütün öğeleri tarar ve her öğe için bir Kume_bul_2 çağırır. Sınıf sayısı k ise bu kısım O(k · n) bulma yapar; bütün öğeler ayrı sınıftaysa O(n²)'ye çıkar. Daha iyi bir yol, öğeleri bir kez tarayıp her birini kökünün listesine eklemektir: O(n · α). Örnek kısa olsun diye basit yol seçilmiştir. Bildirimlerin işlenmesi ise O(n + m · α)'dır.

16.7.3Kruskal algoritması

Bağlantılı ve ağırlıklı bir çizgenin bütün düğümlerini kapsayan ağaçlar arasında kenar ağırlıklarının toplamı en küçük olana minimum kapsayan ağaç (minimum spanning tree) denir. Kruskal algoritması bu ağacı açgözlü bir yolla kurar. Kenarlar ağırlığa göre küçükten büyüğe sıralanır ve sırayla incelenir. Bir kenarın uçları için Küme_bul farklı kökler veriyorsa kenar ağaca alınır ve iki küme birleştirilir. Aynı kökü veriyorsa kenar bir döngü kapatır ve reddedilir.

Reddetme kuralının gerekçesi şudur. İki uç zaten aynı kümedeyse, aralarında daha önce seçilmiş kenarlardan oluşan bir yol vardır. Yeni kenar bu yolu bir döngüye kapatır. Ağaçta döngü olmayacağı için kenar alınamaz. Union-find “bu iki uç arasında seçilmiş kenarlardan bir yol var mı?” sorusunu neredeyse sabit sürede cevaplar. Çizgede yol aramak gerekmez.

typedef struct { int u, v, w; } kenar;   /* uçlar ve ağırlık */

static int kenar_karsilastir(const void *a, const void *b) {
  const kenar *x = a, *y = b;
  return (x->w > y->w) - (x->w < y->w);  /* küçük ağırlık önce */
}

int kruskal(int n, int m, kenar e[], kenar secilen[]) {
  qsort(e, m, sizeof e[0], kenar_karsilastir);
  for (int i = 0; i < n; i++) ata[i] = -1;
  int k = 0;                             /* seçilen kenar sayısı */
  for (int t = 0; t < m && k < n - 1; t++) {
    int a = Kume_bul_2(e[t].u), b = Kume_bul_2(e[t].v);
    if (a != b) {                        /* döngü kapatmıyor */
      Birlesim_2(a, b);
      secilen[k++] = e[t];
    }                                    /* a == b: kenar reddedilir */
  }
  return k;                              /* n-1 ise çizge bağlantılı */
}

Kenar bir yapı olarak tutulur: iki uç ve ağırlık. qsort standart kütüphanenin sıralama yordamıdır; karşılaştırma fonksiyonu iki kenarın ağırlığına bakar. (x->w > y->w) - (x->w < y->w) ifadesi −1, 0 ya da 1 verir. x->w - y->w yazmak daha kısa olurdu, ama çok büyük ağırlıklarda tamsayı taşmasına yol açabilir. Döngü, n − 1 kenar seçilince erken biter; çünkü n düğümlü bir ağaçta tam n − 1 kenar vardır. Yordam seçilen kenar sayısını döndürür. Bu sayı n − 1'den küçükse çizge bağlantılı değildir ve sonuç bir kapsayan ağaç değil, bir kapsayan ormandır.

5 düğümlü bir örnek çizgenin kenarları (uç, uç, ağırlık) biçiminde şöyle olsun: (0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (3, 4, 3), (2, 4, 9). Sıralanınca 1, 2, 3, 4, 5, 8, 9 ağırlıkları gelir.

Seçilen kenarlar (0, 2), (1, 2), (3, 4) ve (1, 3)'tür; toplam ağırlık 1 + 2 + 3 + 5 = 11. (0, 1, 4) kenarı reddedilir, çünkü 0 ile 1 arasında 0–2–1 yolu zaten seçilmiştir. Program aynı dört kenarı ve 11 toplamını verdi.

Maliyet iki parçadan oluşur. Sıralama O(m lg m)'dir. Union-find kısmı en çok 2m bulma ve n − 1 birleşimdir: O(m · α). Toplamı sıralama belirler: O(m lg m). Union-find'ın neredeyse sabit maliyeti olmasaydı, örneğin ilk sürüm kullanılsaydı, döngü kısmı O(m · n)'ye çıkar ve sıralamayı geçerdi.

16.7.4Öteki kullanım alanları

• Ağ bağlantısı. “Bu iki bilgisayar bağlı mı?” sorularını, bağlantılar eklendikçe çevrimiçi cevaplamak. Sedgewick'in kitabı union-find'ı bu örnekle açar.
• Görüntü işleme. Aynı renkteki komşu pikselleri bölgelere ayırmak. Bu işleme bağlantılı bileşen etiketleme denir; her piksel bir öğe, her komşuluk bir birleşimdir.
• Süzülme (percolation). Rastgele açılan hücrelerden oluşan bir ızgarada üstten alta açık bir yol oluşup oluşmadığını sınamak. Monte Carlo deneylerinin çekirdeği, her yeni açık hücreden sonra sorulan bu sorudur.
• Derleyiciler. Tip çıkarımında iki tip ifadesini eşitleyen birleştirme (unification) ve hangi işaretçilerin aynı belleği gösterebileceğini bulan takma ad (alias) analizi.
• Çevrimdışı en yakın ortak ata. Tarjan'ın algoritması, bir ağaçta önceden bilinen düğüm çiftlerinin en yakın ortak atasını (lowest common ancestor, LCA) tek bir gezinmede union-find ile bulur.

Bu uygulamaların hepsinde problem farklıdır, ama alttaki yapı aynıdır: gruplar yalnız büyür, hiç bölünmez ve sık sık “aynı grupta mı?” diye sorulur. Gruplardan öğe çıkarmak ya da bir grubu ikiye bölmek gerekiyorsa union-find uygun değildir; bu işlemleri desteklemez.

16.8Sınav sorusu: ebeveyn dizisinin içeriği

Bu tür sorular, kodu ezberlemenin değil, elle izleyebilmenin ölçüsüdür. Soru şöyledir:

(i) Birlesim_2 kullanıldığı için köklerde −1 değil, eksi düğüm sayısı durur. Bu, sorunun tuzağıdır: (i)'de köklere −1 yazan öğrencinin (ii) cevabı da yanlış çıkar, çünkü ağırlık karşılaştırmaları yanlış sayılarla yapılır. S₁'de 4, S₂'de 3, S₃'te 3 öğe vardır:

ata = [−4, 4, −3, 2, −3, 2, 0, 0, 0, 4]

(ii) Çağrılar sırasıyla izlenir.

Sonuç [4, 4, 4, 4, −10, 4, 0, 4, 0, 4]'tür. On öğe tek kümede, 4 kökünde toplanmıştır. Yalnız 6 ve 8 hâlâ 0 üzerinden köke ulaşır; onlar için henüz bulma çağrılmamıştır. Bütün ara diziler sunumdaki kodla derlenen sürücüde aynen elde edildi.

İkinci adımdaki “2 zaten bağlı” notu, Kume_bul_2'nin fazladan turudur. Yol 5 → 2 → 4'tür; while döngüsü önce 5'i, sonra 2'yi köke bağlar. 2 zaten 4'e bağlı olduğu için ikinci atama değeri değiştirmez.

16.9Karmaşıklık özeti

Bellek her sürümde aynıdır: yalnız n tamsayılık ebeveyn dizisi. Ağırlıklı kural düğüm sayısını kökteki negatif değerde sakladığı için ek dizi gerektirmez. α ≤ 4 olduğundan son satır uygulamada doğrusaldır.

Tablonun özü tek cümleyle söylenebilir: birleşim tek başına hep O(1)'dir; maliyeti belirleyen ağacın derinliği, yani küme bulmadır. Ağırlıklı kural derinliği sınırlar, azaltma kuralı yolları kısaltır. Birleşimin sabit olması yanıltıcıdır, çünkü Birlesim kök ister ve kökü bulmak bir Küme_bul çağrısıdır. Uygulamada “iki öğeyi birleştir” isteği bu yüzden iki bulma artı bir birleşime mal olur.

16.10Sık yapılan hatalar

1. Birleşime kök yerine rastgele bir düğüm vermek. Birlesim_1(i, j)'de i kök değilse ata[i] = j ataması i'nin eski ebeveyniyle bağını koparır. i ve alt ağacı j'nin kümesine geçer; eski ağacın geri kalanı ise eski kümede kalır. İki küme birleşmemiş, biri bölünmüştür. Örnek ormanda Birlesim_1(9, 2) yalnız 9'u taşır; 1 ve 4 eski kümede kalır. Çözüm, önce Kume_Bul ile kökleri bulmaktır.
2. Aynı kümedeki iki kökü, yani bir kökü kendisiyle birleştirmek (i == j). Birlesim_1(r, r) kökü kendisine bağlar ve sonraki bulmalar sonsuz döngüye girer. Birlesim_2(r, r) düğüm sayısını iki katına çıkarır. Birleştirmeden önce kökler karşılaştırılmalıdır.
3. Ağırlıklı kuralda negatif değerlerin karşılaştırmasını ters yorumlamak. −2 > −4, “daha az düğüm” demektir. Ters karşılaştırma kümeleri bozmaz, ama ağaçları zincirleştirir ve hata yalnız ölçümle fark edilir.
4. Birleşimde kökteki düğüm sayısını (p) günlemeyi unutmak. Yeni kökte eski sayı kalır ve sonraki karşılaştırmalar yanlış ağırlıklarla yapılır. p'yi hücrelerden biri değiştirilmeden önce hesaplamak da aynı ölçüde önemlidir.
5. Kume_bul_2'de ebeveyni s'ye saklamadan bağlamak. Yolun devamı kaybolur; yol kısaltılmadan kalır.
6. Başlangıçta ebeveyn dizisini −1 ile doldurmamak. Küresel diziler sıfırla başlar; malloc ile alınan dizinin içeriği ise belirsizdir. Sıfırla dolu bir dizide her düğümün ebeveyni 0'dır ve 0'ın ebeveyni da 0'dır: Kume_Bul 0'da sonsuz döngüye girer.
7. malloc dönüşünü denetlememek ve free'yi unutmak. Dinamik sürümde ata dizisi geri verilmezse program her çağrıda 4n bayt sızdırır. Yapıyı geri vermeden önce iç diziyi geri vermek gerekir.

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

Alıştırma 1. n = 6, ata tümüyle −1. Birlesim_2(0, 1); Birlesim_2(2, 3); Birlesim_2(0, 2); Birlesim_2(4, 5); çağrılarından sonra ata nedir?

Çözüm. İlk iki çağrı eşit ağaçları birleştirir: ata[1] = 0, ata[0] = −2; ata[3] = 2, ata[2] = −2. Üçüncü çağrıda iki kökte −2 vardır; eşitlikte 2, 0'ın altına girer ve ata[0] = −4 olur. Dördüncü çağrı ata[5] = 4, ata[4] = −2 yazar. Sonuç [−4, 0, 0, 2, −2, 4]'tür: 0 kökünde 4, 4 kökünde 2 düğüm. Sürücüyle doğrulandı.

Alıştırma 2. Ağırlıklı kural kullanılırken 16 düğümlü bir ağacın derinliği en çok kaçtır?

Çözüm. Teorem 16.2'ye göre ⌊lg 16⌋ + 1 = 5 düzey. Sınıra ulaşan ağaç, eşit ikililerle kurulur: 8 ikili, 4 dörtlü, 2 sekizli, 1 on altılı. Ölçümde de 5 düzey çıktı.

Alıştırma 3. Ağırlık yerine yükseklik tutan bir birleşim kuralı yazınız. Ne değişir?

Çözüm. Kökte −(düzey sayısı) tutulur. Alçak ağaç yüksek olanın altına bağlanır; yükseklikler eşitse biri ötekinin altına girer ve düzey sayısı 1 artar. Bu yönteme rütbeye göre birleştirme (union by rank) denir:

void Birlesim_3(int i, int j) {
  /* yükseklik kuralı; i ve j kök; kökte -(düzey sayısı) */
  if (ata[i] > ata[j]) {        /* i'nin ağacı daha alçak */
    ata[i] = j;
  } else if (ata[i] < ata[j]) { /* j'nin ağacı daha alçak */
    ata[j] = i;
  } else {                      /* eşit yükseklik */
    ata[j] = i;
    ata[i]--;                   /* düzey sayısı 1 artar */
  }
}

Karşılaştırma yine negatif değerler arasındadır: büyük değer alçak ağacı gösterir. Farklı yükseklikte iki ağaç birleşince yükseklik değişmez, çünkü alçak ağaç yüksek olanın kökünün altına girer ve en çok onun yüksekliğine ulaşır. Alıştırma 1'in işlem dizisiyle sonuç [−3, 0, 0, 2, −2, 4]'tür: aynı ağaçlar, ama 0 kökünde düğüm sayısı 4 yerine düzey sayısı 3 durur. 16 düğümlük eşit ikililerde yine 5 düzey çıkar. Derinlik yine O(lg n) ile sınırlıdır; kanıtı ağırlıklı kuralınkiyle aynıdır (d düzeyli ağaçta en az 2^d−1 düğüm). Azaltma kuralıyla birlikte kullanıldığında yol kısaltma yüksekliği düşürür ama kök bunu bilmez; saklanan değer artık gerçek yükseklik değil, onun bir üst sınırıdır. Bu yüzden ona yükseklik yerine “rütbe” denir.

Alıştırma 4. Kume_bul_2'yi özyinelemeli yazınız.

Çözüm. Tek satırlık yol kısaltma: int bul(int i) { return ata[i] < 0 ? i : (ata[i] = bul(ata[i])); }. Ayrıntılı anlatımı ve bellek karşılaştırması 16.5.5'tedir.

Alıştırma 5. Kruskal algoritmasında bir kenarın reddedilmesi neden döngü demektir?

Çözüm. Kenar, uçları aynı kümedeyse reddedilir. Aynı kümede olmak, iki uç arasında daha önce seçilmiş kenarlardan oluşan bir yol bulunması demektir; çünkü kümeler yalnız seçilen kenarlarla birleşir. Yeni kenar bu yolun iki ucunu doğrudan bağlar ve yolu bir döngüye kapatır.

Alıştırma 6. n düğümlü, m kenarlı bir çizgede bileşen sayısını bulmanın maliyeti nedir?

Çözüm. Ebeveyn dizisini kurmak O(n), kenar döngüsü 2m bulma ve en çok n − 1 birleşimdir. İki kural birlikte kullanılınca toplam O(n + m · α(m + n, n))'dir; uygulamada doğrusaldır.

16.12Özet

• Model. Ayrık kümeler, kökü küme adı olan ve bağları çocuktan ebeveyne giden ağaçlarla gösterilir. İki işlem vardır: birleşim ve küme bulma. İki öğe, kökleri aynıysa aynı kümededir.
• Gösterim. Bütün orman tek bir int dizisinde durur: ata[i], i'nin ebeveynidir; kökte negatif bir değer bulunur. Dizi malloc ile kurulursa her ayırmadan sonra NULL denetlenir ve bloklar ters sırayla geri verilir.
• İlk sürüm. Birlesim_1 tek atamadır; Kume_Bul_1 köke kadar yürür ve düğümün derinliği kadar sürer.
• Kötü durum. Rastgele bağlama zincir üretebilir: Birlesim_1(i, i+1) dizisinden sonra n bulma tam n(n − 1)/2 ilerleme, yani Θ(n²) sürer. Rastgele testler bu girdiyi kolayca kaçırır.
• Ağırlıklı kural. Küçük ağaç büyüğün altına bağlanır. Düğüm sayısı kökte eksi işaretle saklanır; ek dizi gerekmez. Derinlik ⌊lg m⌋ + 1'i aşmaz ve sınır eşit ikililerle tam olarak yakalanır.
• Azaltma kuralı. Bulma sırasında yol üzerindeki her düğüm doğrudan köke bağlanır. İlk çağrı yaklaşık iki kat pahalıdır, ama sonraki aramalar bir çırpıda biter. Eski ebeveyn bağlamadan önce saklanmalıdır.
• Sonuç. İki kural birlikte işlem başına α ile orantılı maliyet verir (Tarjan–van Leeuwen). Ters Ackermann fonksiyonu n ≤ 2⁶⁵⁵³³ için 4'ü aşmaz; maliyet uygulamada neredeyse O(1)'dir.
• Uygulamalar. Bileşen sayma, eşdeğerlik sınıfları ve Kruskal algoritması aynı kalıbı kullanır: iki ucun kökünü bul, farklıysa birleştir, aynıysa döngü var.

16.13Kavram listesi

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

• ayrık kümeler disjoint sets
• union-find union-find
• birleşim union
• küme bulma find
• orman forest
• kök root
• ebeveyn parent
• ebeveyn dizisi parent array
• ağırlıklı kural weighting rule
• rütbeye göre birleştirme union by rank
• azaltma kuralı collapsing rule
• yol kısaltma path compression
• en kötü durum worst case
• amortize analiz amortized analysis
• Ackermann fonksiyonu Ackermann function
• ters Ackermann fonksiyonu inverse Ackermann function
• çağrı yığını call stack
• yığın taşması stack overflow
• bağlantılı bileşen connected component
• minimum kapsayan ağaç minimum spanning tree
• bellek sızıntısı memory leak
• sarkan işaretçi dangling pointer
• işaretçiye işaretçi pointer to pointer

16.14Kendini Dene

1. ata = [−1, 0, 0, 1, 1, −1, 5] dizisinde kaç küme vardır? Kume_Bul_1(4) neyi döndürür ve kaç ilerleme yapar?

   Cevap

   Negatif değerli iki hücre (0 ve 5) vardır; iki küme: {0, 1, 2, 3, 4} ve {5, 6}. Kume_Bul_1(4) 4 → 1 → 0 yolunu izler, 2 ilerlemeyle 0'ı döndürür.

2. n = 8 tek öğeli kümeye Birlesim_1(i, i+1) çağrıları i = 0, …, 6 için uygulanıyor. Ardından her öğe için bir Kume_Bul_1 çağrılıyor. Toplam kaç ilerleme yapılır?

   Cevap

   n(n − 1)/2 = 8 · 7 / 2 = 28. Kume_Bul_1(0) 7, Kume_Bul_1(1) 6 … Kume_Bul_1(7) 0 ilerleme yapar.

3. ata = [−3, 0, 0, −5, 3, 3, 3, 3] iken Birlesim_2(0, 3) çağrılıyor. Dizi ne olur?

   Cevap

   p = −8. −3 > −5 doğrudur: 0'ın ağacı daha küçüktür ve 3'ün altına girer. Sonuç [3, 0, 0, −8, 3, 3, 3, 3].

4. ata = [−8, 0, 0, 2, 0, 4, 4, 6] iken Kume_bul_2(3) çağrılıyor. Döngüler kaçar tur döner, dizi ne olur?

   Cevap

   Yol 3 → 2 → 0'dır. for döngüsü 2 ilerleme yapar, while döngüsü 2 tur döner: 3 köke bağlanır, 2 için fazladan tur yapılır. Sonuç [−8, 0, 0, 0, 0, 4, 4, 6], dönüş değeri 0.

5. Ağırlıklı kuralla kurulmuş 1024 düğümlü bir ağaçta tek bir Kume_Bul_1 en çok kaç ilerleme yapar?

   Cevap

   Düzey sayısı en çok ⌊lg 1024⌋ + 1 = 11'dir. En derin düğümden köke 10 kenar vardır: en çok 10 ilerleme.

6. n = 1000 için α(n, n) kaçtır? (Tanımdaki A ile.)

   Cevap

   ⌊n/n⌋ = 1, lg 1000 ≈ 9,97. A(1, 1) = 3 ve A(2, 1) = 5 yetmez; A(3, 1) = 13 ≥ 9,97. Cevap 3.

7. ackermann(2, 1) neyi döndürür ve toplam kaç çağrı yapılır?

   Cevap

   A(2, 1) = 2 · 1 + 3 = 5. Sayaçlı çalıştırmada 14 çağrı yapıldı.

8. 5 düğümlü bir çizgenin kenarları (0, 1), (1, 2), (2, 0), (3, 4)'tür. bilesen_say neyi döndürür? Hangi kenar sayıyı değiştirmez?

   Cevap

   2 döndürür: {0, 1, 2} ve {3, 4}. (2, 0) kenarının iki ucu da 0 köküne ulaşır; kenar 0–1–2 döngüsünü kapatır ve sayı değişmez.

9. kumeler_sil parametresini kumeler **kp yerine kumeler *k olarak alsaydı ne kaybedilirdi?

   Cevap

   Yordam blokları yine geri verebilirdi, ama çağıranın işaretçisini NULL yapamazdı. Çağıranın değişkeni geri verilmiş belleği göstermeye devam eder; yani sarkan işaretçi olur. İkinci bir silme çağrısı aynı bloğu iki kez geri vermeye çalışır ve tanımsız davranış doğar.

16.15İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Kesim 5.10 (Set Representation). Ebeveyn dizisi, ağırlıklı kural ve azaltma kuralı bu notla aynı sırada, lemmalarıyla anlatılır.
• T. H. Cormen ve diğerleri, Introduction to Algorithms, “Data Structures for Disjoint Sets” bölümü. Rütbeye göre birleştirme ve yol kısaltmanın α'lı sınırının ayrıntılı kanıtını verir.
• R. Sedgewick, Algorithms in C, Bölüm 1. Union-find'ı ağ bağlantısı örneğiyle adım adım geliştirir ve sürümleri ölçümlerle karşılaştırır.
• R. E. Tarjan, J. van Leeuwen, “Worst-case analysis of set union algorithms”, Journal of the ACM 31(2), 1984. Teorem 16.3'ün kaynağıdır; birçok yol kısaltma çeşidini birlikte inceler.

16.16Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Kesim 5.10 (Set Representation).
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (CLRS), “Data Structures for Disjoint Sets” bölümü.
3. R. Sedgewick, Algorithms in C, Bölüm 1 (union-find ile bağlantılılık).
4. R. E. Tarjan, J. van Leeuwen, “Worst-case analysis of set union algorithms”, J. ACM 31(2), 1984.

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