Bölüm 13: Kümeler ve Ayrık Kümeler

13.1Küme ADT'si

Bir veri yapısını anlatmanın iki düzeyi vardır. Birinci düzey yapının ne yaptığını söyler: hangi işlemler vardır ve her işlem neyi değiştirir. İkinci düzey bunun nasıl yapıldığını anlatır: veriler bellekte nasıl dizilir, işlemler hangi adımlarla yürür. Birinci düzeydeki tarife soyut veri tipi (abstract data type, kısaca ADT) denir. Bu kesim kümeyi soyut düzeyde ele alır; hash tablosu, ağaç ve bit vektörü gibi somut gerçeklemeler 13.2'nin konusudur.

13.1.1Küme nedir?

Bir sınıfın yoklama listesini düşünelim. Bir öğrencinin adı listeye bir kez yazılır; aynı adı ikinci kez yazmak listeye bilgi katmaz. Adların hangi sırayla yazıldığı da önemli değildir. Önemli olan tek soru şudur: “Ayşe bu sınıfta mı?” Matematikteki küme kavramı tam olarak bu düşünceyi taşır. Veri yapıları da aynı kavramı bilgisayara taşır.

Tanımda iki kural öne çıkar. Birincisi tekrar yasağıdır. Kümede zaten bulunan bir öğe yeniden eklenirse küme değişmez. Bu kural, sıradan bir listeyle küme arasındaki en belirgin farktır. Listeye aynı değer istendiği kadar eklenebilir; kümeye eklenemez. İkinci kural sırasızlıktır. Kümenin “ilk öğesi” ya da “3. öğesi” diye bir kavramı yoktur; bu yüzden küme ADT'sinde indisle erişim işlemi bulunmaz. Bazı gerçeklemeler öğeleri belli bir sırayla gezer, ama bu sıra gerçeklemenin bir yan ürünüdür, kümenin tanımına ait değildir.

Kümeden beklenen en önemli yetenek üyelik testini hızlı yanıtlamaktır. Bir dizide aynı soruyu yanıtlamak için öğeler baştan sona taranır; n öğede bu O(n) sürer. İyi bir küme gerçeklemesi aynı soruyu ortalama sabit sürede ya da O(log n) sürede yanıtlar. Bölümün büyük kısmı bu hızın nasıl elde edildiğini anlatır.

Şekil 13.1 bu iki kuralı birlikte gösterir. S = {7, 2, 9, 5} kümesine add(2) uygulandığında 2 zaten kümededir; öğe sayısı 4 olarak kalır. Şekilde öğelerin dağınık çizilmesi de bilinçli bir seçimdir: kümede “önce” ya da “sonra” yoktur.

Kümeler gündelik programlamada üç tür işte karşımıza çıkar:

• Tekrar ayıklama. Bir metindeki farklı kelimeleri bulmak için kelimeler bir kümeye eklenir; tekrarlar kendiliğinden düşer. Java'da bir listeden kümeye geçmek tek satırdır: new HashSet<>(liste).
• Üyelik. Yasaklı kullanıcılar, daha önce ziyaret edilmiş düğümler, sözlükteki geçerli kelimeler birer kümedir. Her yeni istekte “bu öğe kümede mi?” diye sorulur.
• Küme cebri. İki kişinin ortak arkadaşları iki arkadaş kümesinin kesişimidir. Bir sitedeki bütün etiketler, yazıların etiket kümelerinin birleşimidir.

13.1.2Küme işlemleri

Kümeler üzerinde dört temel işlem tanımlanır. Bunlara küme işleçleri de denir. A ve B iki küme olsun.

• Birleşim (union), A ∪ B: A'da ya da B'de (ya da ikisinde birden) bulunan öğelerin kümesi.
• Kesişim (intersection), A ∩ B: hem A'da hem B'de bulunan öğelerin kümesi.
• Fark (difference), A − B: A'da bulunup B'de bulunmayan öğelerin kümesi.
• Alt küme (subset), A ⊆ B: A'nın her öğesi B'de de bulunuyorsa A, B'nin alt kümesidir. Bu bir işlem değil, doğru ya da yanlış yanıtı olan bir sorudur.

Şekil 13.2 bu işlemleri Venn şemalarıyla gösterir. Venn şemasında her küme bir daire, öğeler dairenin içindeki noktalardır. Birleşimde iki daire de tümüyle taranır. Kesişimde yalnız iki dairenin örtüştüğü mercek biçimli bölge kalır. Farkta A'nın daireden B'ye taşan kısmı oyulur. Alt küme ilişkisinde A dairesi B'nin tamamen içindedir.

Farkın iki yönü olduğuna dikkat etmek gerekir. Birleşim ve kesişim değişmelidir: A ∪ B = B ∪ A ve A ∩ B = B ∩ A. Fark ise değişmeli değildir; A − B ile B − A genellikle farklı kümelerdir.

Örnekteki son adım, birleşimin boyutunu denetlemek için kullanışlı bir eşitliği gösterir: |A ∪ B| = |A| + |B| − |A ∩ B|. Ortak öğeler iki kümenin boyutunda da sayıldığı için bir kez çıkarılır. Bu eşitliğe içerme–dışlama ilkesi denir.

13.1.3Java'da Set arayüzü

Java koleksiyon kütüphanesinde küme ADT'sinin karşılığı java.util.Set<E> arayüzüdür. Arayüz yalnız işlemleri tanımlar; işlemleri yapan sınıflar HashSet, LinkedHashSet ve TreeSet'tir. Set, Collection arayüzünü genişletir ve ona tek bir sözleşme ekler: kümede birbirine eşit iki öğe bulunamaz. Eşitlik equals metoduyla (sıralı kümede compare ile) belirlenir.

add metodunun dönüş değeri küçük ama değerli bir ayrıntıdır. Metot yalnız öğeyi eklemekle kalmaz, ekleyip eklemediğini de bildirir. Öğe yeniyse true, zaten varsa false döner. Bu tek bit bilgi, 13.1.4'teki tekrar bulma algoritmasının temelidir. remove da benzer biçimde öğeyi gerçekten çıkardıysa true döndürür.

Küme işlemlerinin Java karşılıkları addAll, retainAll ve removeAll'dur. Aşağıdaki kod Örnek 13.1'deki hesabı Java ile yapar:

Set<Integer> a = new HashSet<>(List.of(1,2,3,4,5));
Set<Integer> b = new HashSet<>(List.of(3,4,5,6,7));
Set<Integer> bir = new HashSet<>(a);
bir.addAll(b);     // [1..7]
Set<Integer> kes = new HashSet<>(a);
kes.retainAll(b);  // [3, 4, 5]
Set<Integer> fark = new HashSet<>(a);
fark.removeAll(b); // [1, 2]
a.containsAll(b);  // false

Kodu satır satır okuyalım. İlk iki satır List.of ile verilen değerlerden iki HashSet kurar. Üçüncü satır a'nın bir kopyasını bir adıyla oluşturur; bir.addAll(b) bu kopyaya B'nin öğelerini ekler. Kopyada zaten bulunan 3, 4, 5 yeniden eklenmez; 6 ve 7 eklenir. Sonuç 1'den 7'ye kadar olan sayılardır. Kesişim için yine a'nın kopyası alınır ve retainAll(b) çağrılır. Bu metot, B'de bulunmayan her öğeyi siler; geriye [3, 4, 5] kalır. Fark için kopyaya removeAll(b) uygulanır; B'de bulunan her öğe silinir, geriye [1, 2] kalır. Son satırdaki a.containsAll(b), “B'nin her öğesi A'da mı?” sorusunu, yani B ⊆ A sorusunu sorar. 6, A'da olmadığı için yanıt false'tur.

Üç toplu metodun maliyeti, gerçeklemeye göre değişir. HashSet'te bir.addAll(b), B'nin her öğesi için bir add yapar. Her add ortalama O(1) olduğundan toplam O(|B|) sürer; kopyalama da O(|A|) ekler. retainAll ve removeAll ise kopyadaki her öğe için öteki kümede contains sorar; bu da ortalama O(|A|) sürer. Kısacası hash kümelerle iki kümenin birleşimi, kesişimi ve farkı ortalama O(n + m) sürede bulunur.

13.1.4Kod izleme: add dönüşüyle ilk tekrar

Bir dizide ilk tekrar eden öğeyi bulmak isteyelim: soldan sağa okurken daha önce görülmüş ilk değer hangisidir? Kümesiz çözüm her öğeyi kendinden önceki bütün öğelerle karşılaştırır. Bu iç içe iki döngü demektir ve en kötü durumda n(n − 1)/2 karşılaştırma, yani O(n²) yapar. Kümeyle çözüm, görülen öğeleri bir kümede biriktirir ve her yeni öğeyi tek bir add çağrısıyla denetler:

int ilkTekrar(int[] a) {
  Set<Integer> gorulen = new HashSet<>();
  for (int x : a) {
    if (!gorulen.add(x))   // eklenemedi mi?
      return x;            // zaten vardı: tekrar
  }
  return -1;               // tekrar yok
}

Metot boş bir HashSet ile başlar ve dizinin öğelerini sırayla dolaşır. Döngünün gövdesindeki tek satır iki işi birden yapar. gorulen.add(x) öğeyi eklemeyi dener; öğe yeniyse ekler ve true döndürür. Başına konan ! bu değeri tersine çevirir: !true yanlıştır, koşul sağlanmaz ve döngü sürer. Öğe daha önce eklenmişse add kümeyi değiştirmeden false döndürür; !false doğrudur ve metot o öğeyi döndürür. Dizide hiç tekrar yoksa döngü biter ve -1 döner.

Bu kalıp, önce contains ile sorup sonra add çağırmaktan daha kısadır. Üstelik kümeye bir kez erişir: contains + add çifti aynı kovayı iki kez arardı.

Metodu a = [4, 7, 2, 7, 4] dizisiyle izleyelim. HashSet içeride 16 kovalı bir tablo kullanır. Bir öğenin kovası, hash kodunun son dört biti alınarak bulunur: hash(x) & 15. Integer için hash kodu sayının kendisidir; bu yüzden 4 kova 4'e, 7 kova 7'ye, 2 kova 2'ye düşer.

İlk üç turda kovalar boştur; her öğe tek bir kova bakışıyla eklenir ve add true döndürür. Dördüncü turda 7 gelir. Kova 7'de zaten 7 vardır; küme değişmez ve add false döndürür. Koşul sağlanır, metot 7'yi döndürür. Dizinin son öğesi olan 4'e hiç bakılmaz: metot ilk tekrarı bulduğu anda durur.

Maliyet hesabı kısadır. Her öğe için bir add yapılır ve her add ortalama O(1)'dir. n öğeli dizide toplam süre ortalama O(n)'dir; iç içe döngü yoktur. Bu hızın bedeli bellektir: küme en çok n öğe tutar, ek alan O(n)'dir. Zaman ile bellek arasındaki bu takas, kümelerin en tipik kullanımıdır.

13.2Küme gerçeklemeleri

Küme ADT'si yalnız “ne” sorusunu yanıtlar. Aynı ADT birçok farklı biçimde gerçeklenebilir ve her gerçekleme bazı işlemleri hızlı, bazılarını yavaş yapar. Bu kesim dört gerçeklemeyi inceler: hash tablosu, dengeli ikili arama ağacı, sıralı dizi ve bit vektörü. Sonunda hangisinin hangi durumda seçileceği bir tabloda toplanır.

13.2.1Java'daki Set sınıfları

Java, Set arayüzünü üç hazır sınıfla gerçekler. Üçü de aynı sözleşmeye uyar: tekrar tutmaz, add, remove ve contains işlemlerini sunar. Aralarındaki fark iç yapıda ve bu yapının getirdiği gezinme sırasındadır.

Üç sınıfın farkını görmek için aynı dört kelimeyi üçüne de ekleyelim:

for (String s : List.of("elma", "kiraz", "armut", "elma")) {
    hash.add(s);  linked.add(s);  tree.add(s);
}
// HashSet       → [elma, armut, kiraz]   (kova sırası: hash'e bağlı)
// LinkedHashSet → [elma, kiraz, armut]   (eklenme sırası)
// TreeSet       → [armut, elma, kiraz]   (alfabetik)

“elma” iki kez eklenmiştir, ama üç kümede de bir kez bulunur: ikinci add("elma") üçünde de false döndürür. Yazdırılan sıralar ise farklıdır. HashSet öğeleri kovalarının sırasıyla verir. “elma”nın hash kodu 16 kovalı tabloda 4. kovaya, “armut”unki 7. kovaya, “kiraz”ınki 8. kovaya düşer. Bu yüzden çıktı [elma, armut, kiraz]'dır. Bu sıra ne ekleme sırasıdır ne alfabetik; tablonun boyutu değişirse o da değişebilir. LinkedHashSet her öğeyi ayrıca bir çift bağlı listenin sonuna ekler ve gezinmeyi bu listeden yapar; sonuç ekleme sırasıdır: [elma, kiraz, armut]. TreeSet öğeleri bir arama ağacında tutar ve kök ortada gezinmeyle sıralı verir: [armut, elma, kiraz].

Seçim kuralı buradan çıkar. Sıra önemsizse HashSet, ekleme sırası gerekiyorsa LinkedHashSet, sıralı erişim gerekiyorsa TreeSet kullanılır. LinkedHashSet sıranın bedelini bellekle öder: her öğe için iki ek referans tutar. TreeSet ise zamanla öder: işlemleri O(1) yerine O(log n)'dir.

13.2.2Hash tabanlı küme

Hash tabanlı küme, öğeleri bir hash tablosunda (hash table) saklar. Hash tablosu, m hücreli bir dizidir; her hücreye kova (bucket) denir. Bir öğenin hangi kovaya gideceği, öğenin hash kodundan (hash code) hesaplanır. Hash kodu, öğeden üretilen bir tamsayıdır; eşit öğelerin hash kodları da eşittir. Kova numarası çoğu zaman hash kodunun m'ye bölümünden kalandır: i = hashCode(x) mod m.

Eşlemeler için kullanılan hash tablosu her kovada bir anahtar–değer çifti tutar. Kümede değere gerek yoktur; tabloda yalnız anahtarlar, yani küme öğeleri saklanır. Java'nın HashSet sınıfı da içeride bir HashMap kullanır: öğeyi anahtar olarak koyar, değer yerine hep aynı boş nesneyi yazar.

İki farklı öğe aynı kovaya düşebilir; buna çakışma (collision) denir. 7 kovalı bir tabloda 12 ile 19'un ikisi de 5'e düşer, çünkü 12 mod 7 = 5 ve 19 mod 7 = 5'tir. Çakışmayı çözmenin en basit yolu ayrı zincirlemedir (separate chaining): her kova bir liste tutar ve aynı kovaya düşen öğeler bu listeye (zincire) sıralanır.

Şekil 13.4 boş bir 7 kovalı tabloya sırasıyla 12, 25, 7, 19 ve yeniden 12 eklendiğinde olanları gösterir. add(12): 12 mod 7 = 5, kova 5 boştur, 12 eklenir. add(25): 25 mod 7 = 4, 25 kova 4'e gider. add(7): 7 mod 7 = 0, 7 kova 0'a gider. add(19): 19 mod 7 = 5; kova 5'te 12 vardır. Bu bir çakışmadır; 19, 12'den farklı olduğu için zincirin sonuna eklenir. İkinci add(12)'de kova 5 taranır ve 12 bulunur; öğe eklenmez, metot false döndürür. Kümeyi küme yapan işte bu denetimdir.

Son adım hash tablosunun neden hızlı olduğunu açıklar. contains(26) için yalnız 26 mod 7 = 5 numaralı kovaya bakılır. Kovadaki iki öğe (12 ve 19) 26 ile karşılaştırılır, ikisi de farklıdır, yanıt false'tur. Kova 0 ve kova 4'teki öğelere hiç dokunulmaz. Tablo ne kadar büyük olursa olsun arama tek bir kovanın zinciriyle sınırlıdır.

Bu zincirlerin uzunluğu ne kadardır? n öğe m kovaya düzgün dağılırsa bir zincirin ortalama uzunluğu n / m'dir. Bu orana yük faktörü (load factor) denir ve genellikle λ ile gösterilir. Örnekteki tabloda 4 öğe ve 7 kova vardır: λ = 4/7 ≈ 0,57. Hash tablosu yük faktörü belli bir eşiği aşınca (Java'da 0,75) kova sayısını yaklaşık iki katına çıkarır ve öğeleri yeni kovalarına dağıtır. Böylece λ sabit bir sınırın altında kalır. Ortalama zincir boyu sabit olduğundan add, contains ve remove ortalama O(1) sürer.

Bu ortalama, hash fonksiyonunun öğeleri kovalara iyi dağıttığı varsayımına dayanır. Kötü bir hash fonksiyonu bütün öğeleri aynı kovaya gönderirse tablo tek bir uzun zincire dönüşür. O durumda her işlem bütün zinciri tarar ve en kötü durum maliyeti O(n) olur.

13.2.3Kod izleme: add ve contains

Zincirlemeli hash kümesinin iki temel metodu kısa bir kodla yazılabilir. Alanlar şunlardır: m kova sayısı, kova her biri bir tamsayı listesi olan dizi, n kümedeki öğe sayısı. Kod, öğelerin negatif olmadığını varsayar; böylece kova numarası doğrudan x % m ile bulunur.

// alanlar: List<Integer>[] kova; n; m = 7
boolean add(int x) {          // x ≥ 0
  int i = x % m;               // kova no
  for (int y : kova[i])
    if (y == x) return false;  // zaten var
  kova[i].add(x);
  n++;
  return true;
}
boolean contains(int x) {
  int i = x % m;
  for (int y : kova[i])
    if (y == x) return true;
  return false;
}

add(x) önce kova numarasını hesaplar: i = x % m. Ardından o kovanın zincirini baştan sona dolaşır. Zincirde x'e eşit bir y bulursa öğe zaten kümededir; metot hiçbir şey eklemeden false döndürür. Zincir biterse x yenidir: zincirin sonuna eklenir, n bir artar ve metot true döndürür. contains(x) aynı taramayı yapar; eşit öğe bulursa true, zincir biterse false döndürür. İki metot da yalnız tek bir kovanın zincirine bakar.

İzlemede dikkat edilecek üç an vardır. İlk üç add'de kovalar boştur; döngü hiç dönmez ve öğe hemen eklenir. add(19)'da kova 5'te 12 bulunur. Döngü bir kez döner: 12 ≠ 19, zincirde ilerlenir. Zincir bitince 19 sona eklenir ve kova 5'te artık iki öğe vardır. İkinci add(12)'de döngünün ilk adımı y = 12 == 12 sonucunu verir; metot oradan false ile döner ve n 4'te kalır.

İki contains çağrısı başarılı ve başarısız aramanın farkını gösterir. contains(26) zincirin tamamını (iki öğe) tarar ve bulamaz. contains(19) de iki öğeye bakar, ama ikincisinde eşitliği bulur ve true döndürür. Her iki çağrıda da yalnız kova 5'e bakılmıştır.

Maliyet. Kova numarasını hesaplamak sabit süredir. Zincir taraması zincirin uzunluğu kadar sürer; ortalama zincir uzunluğu yük faktörüne, yani n / m'ye eşittir. Yük faktörü sabit tutulduğu sürece iki metot da ortalama O(1)'dir. Bellek, m kova ile n zincir düğümü için O(n + m)'dir.

13.2.4Ağaç tabanlı (sıralı) küme

Hash tablosu hızlıdır, ama öğelerin sırası hakkında hiçbir şey bilmez. “Kümedeki en küçük öğe hangisi?” ya da “17'den küçük en büyük öğe hangisi?” sorularını hash kümesi ancak bütün öğeleri tarayarak yanıtlar. Bu sorular sık soruluyorsa küme bir dengeli ikili arama ağacıyla gerçeklenir.

İkili arama ağacında her düğümün sol alt ağacındaki öğeler düğümden küçük, sağ alt ağacındakiler büyüktür. Bu düzen sayesinde arama kökten başlar ve her adımda sola ya da sağa inerek ağacın yarısını eler. Ağaç dengeli tutulursa yüksekliği O(log n) olur ve arama, ekleme, silme O(log n) sürer. Java'nın TreeSet sınıfı dengeyi kırmızı-siyah ağaçla (red-black tree) korur.

Ağaçtaki öğelerin sıralı saklanması, iki önemli sonuç doğurur. Birincisi, kök ortada (inorder) gezinme (önce sol alt ağaç, sonra düğüm, sonra sağ alt ağaç) öğeleri küçükten büyüğe verir. Şekil 13.6'daki ağaçta bu sıra 5, 10, 15, 20, 25, 30, 40'tır. İkincisi, sıraya dayalı sorgular da O(log n) sürede yanıtlanır. TreeSet bu sorguları NavigableSet arayüzü üzerinden sunar.

floor(17)'nin ağaçta nasıl bulunduğunu izleyelim. Kökte 20 vardır; 20 > 17 olduğu için cevap 20 olamaz, sola inilir. 10'da 10 ≤ 17'dir; 10 bir aday olur ve daha büyük bir aday için sağa inilir. 15'te 15 ≤ 17'dir; aday 15 olur, yine sağa inilir. 15'in sağ çocuğu yoktur; arama biter ve son aday 15 döner. Yol kökten yaprağa tek bir iniştir; ağacın yüksekliği kadar adım sürer. ceiling(17) aynı yolu ters kuralla yürür ve 20'yi bulur. Bir değer kümede varsa iki metot da onun kendisini döndürür; eşitlik dahildir.

subSet(10, 30)'da alt sınır dahil, üst sınır hariçtir; 30 sonuca girmez. Bu, Java'nın aralıklarda genel olarak izlediği yarı açık aralık kuralıdır. Aralık sorgusunun maliyeti, başlangıç noktasını bulmak için O(log n) ile çıktıdaki k öğe için O(k)'nin toplamıdır.

Ağaç tabanlı kümenin bir ön koşulu vardır: öğeler karşılaştırılabilir olmalıdır. Ya öğe sınıfı Comparable arayüzünü gerçekler ya da kümeye bir Comparator verilir. TreeSet iki öğenin eşit olup olmadığına equals ile değil, compare(a, b) == 0 sonucuyla karar verir.

13.2.5Sıralı dizilerle birleşim ve kesişim

Kümenin en sade gerçeklemesi, öğelerini küçükten büyüğe sıralı bir dizide tutmaktır. Üyelik testi ikili aramayla O(log n) sürer. Ekleme ve silme yavaştır, çünkü sırayı korumak için öğeler kaydırılır: O(n). Buna karşılık iki sıralı küme arasında birleşim ve kesişim çok verimli hesaplanır. Yöntem, birleştirme sıralamasındaki birleştirme (merge) adımının aynısıdır: iki dizide birer imleç tutulur ve iki imleç tek geçişte ilerler. Goodrich, Tamassia ve Goldwasser bu yöntemi genel birleştirme (generic merge) adıyla anlatır.

void birlesimKesisim(int[] a, int[] b,
    List<Integer> bir, List<Integer> kes) {
  int i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] < b[j]) bir.add(a[i++]);
    else if (a[i] > b[j]) bir.add(b[j++]);
    else {                     // ortak öğe
      bir.add(a[i]);  kes.add(a[i]);
      i++;  j++;
    }
  }
  while (i < a.length) bir.add(a[i++]);
  while (j < b.length) bir.add(b[j++]);
}

Metot iki imleçle başlar: i dizi a'da, j dizi b'de, ikisi de 0'da. Ana döngü iki dizide de öğe kaldığı sürece döner ve her turda a[i] ile b[j]'yi karşılaştırır:

• a[i] < b[j] ise a[i] yalnız a'dadır. Neden? b sıralıdır ve b[j]'den sonraki öğeler daha büyüktür; a[i]'ye eşit bir öğe b'nin geri kalanında bulunamaz. a[i] birleşime eklenir ve i ilerler.
• a[i] > b[j] ise aynı gerekçeyle b[j] yalnız b'dedir; birleşime eklenir, j ilerler.
• İkisi eşitse öğe ortaktır. Birleşime bir kez ve kesişime eklenir; iki imleç birlikte ilerler.

Dizilerden biri bitince ana döngü durur. Artık ortak öğe olamaz, bu yüzden kesişim tamamlanmıştır. Öteki dizide kalan öğeler yalnız o dizide bulunduğu için doğrudan birleşime eklenir. Son iki while döngüsünden en çok biri iş yapar.

Metodu a = [1, 3, 5, 7, 9] ve b = [3, 4, 5, 8] ile izleyelim.

Ana döngü altı tur döner. 7. adımda b tükenmiştir; kesişim [3, 5] olarak kesinleşir. a'da kalan tek öğe 9'dur ve ilk ek döngü onu birleşime ekler. b'de kalan olmadığı için ikinci ek döngü hiç dönmez. Sonuç: birleşim [1, 3, 4, 5, 7, 8, 9], kesişim [3, 5]. İki çıktı da kendiliğinden sıralıdır; böylece yeni kümeler de sıralı dizi olarak kullanılabilir.

Maliyet. Her turda en az bir imleç bir adım ilerler ve hiçbir imleç geri gitmez. |a| = n ve |b| = m ise toplam adım sayısı en çok n + m'dir; süre O(n + m)'dir. Sıralı olmayan iki listede aynı iş, her öğe için öteki listeyi taramayı gerektirir ve O(n · m) sürer. Fark (A − B) da aynı iskeletle bulunur: yalnız a[i] < b[j] durumundaki öğeler ve a'da kalanlar sonuca eklenir.

13.2.6Gerçeklemelerin karşılaştırması

Dört gerçeklemenin maliyetleri Tablo 13.8'de yan yana verilmiştir. |A| = n, |B| = m'dir.

Tablonun satırlarını tek tek gerekçelendirelim. Sırasız listede üyelik için bütün liste taranır. Ekleme de tekrar denetimi gerektirdiği için önce bir arama yapar; bu yüzden O(n)'dir. Birleşimde B'nin her öğesi A'da aranır: O(n · m). Sıralı dizide arama ikili aramayla O(log n)'dir, ama ekleme ve silme öğe kaydırdığı için O(n)'dir. Küme işlemleri iki imleçle O(n + m)'dir. Hash tablosunda tek öğe işlemleri ortalama sabittir. Birleşim için B'nin her öğesine contains + add uygulanır; kopyalamayla birlikte ortalama O(n + m) tutar. Hash tablosu sıra bilmediği için sıralı gezinme önce bir sıralama ister (O(n log n)). En küçük öğe ya da floor sorgusu bütün öğeleri tarar (O(n)). Dengeli ağaçta her tek öğe işlemi O(log n)'dir. Birleşimde B'nin m öğesi, en çok n + m öğeli ağaca tek tek eklenir: O(m log(n + m)). Kök ortada gezinme sıralı çıktıyı O(n)'de verir.

Pratikteki seçim iki cümleyle özetlenebilir. Varsayılan seçim hash tablosudur: sıra gerekmiyorsa en hızlı üyelik testini o verir. Sıra gerekiyorsa ağaç seçilir: her işlem O(log n)'dir ve sıralı sorgular ek bir bedel istemez. Sıralı dizi ise küme bir kez kurulup sonra yalnız sorgulanıyorsa ve sık sık birleşim ya da kesişim gerekiyorsa iyi bir seçimdir.

13.2.7Bit vektörü ile küme

Kümenin öğeleri küçük bir tamsayı aralığından geliyorsa çok daha sıkı bir gösterim kullanılabilir. Bütün olası öğelerin oluşturduğu kümeye evren denir. Evren {0, 1, …, U − 1} ise küme U bitlik bir dizi olarak saklanır: i. bit 1 ise i kümededir, 0 ise değildir. Bu gösterime bit vektörü (bit vector) denir.

Evren en çok 32 öğeliyse bütün küme tek bir int'e sığar. Bu durumda her küme işlemi tek bir makine komutudur:

• Ekleme: a |= 1 << x. 1 << x, yalnız x. biti 1 olan bir maske üretir; VEYA işlemi o biti 1 yapar, ötekilere dokunmaz.
• Üyelik: (a >> x & 1) == 1. Sağa kaydırma x. biti en sağa getirir, & 1 yalnız o biti bırakır.
• Silme: a &= ~(1 << x). Maskenin tersi x. bit dışında her yerde 1'dir; VE işlemi yalnız o biti sıfırlar.
• Birleşim, kesişim, fark: a | b, a & b, a & ~b. Bitlerin her biri ayrı bir öğeyi temsil ettiği için bit düzeyindeki VEYA, VE ve DEĞİL işlemleri küme işlemlerine birebir karşılık gelir.
• Öğe sayısı: Integer.bitCount(a), 1 olan bitleri sayar.

Evren 32'den büyükse java.util.BitSet kullanılır. Bu sınıf bitleri bir long dizisinde tutar ve 64'er bitlik kelimeler üzerinde çalışır. Tek öğe işlemleri yine O(1)'dir; ilgili kelime ve bit doğrudan hesaplanır. Küme işlemleri kelime kelime yapılır ve O(U / 64) sürer.

Bit vektörünün belleği evrenin boyutuna bağlıdır, kümedeki öğe sayısına değil: U bit. Bir milyon öğelik evren 10⁶ / 8 = 125.000 bayt, yani yaklaşık 122 KB tutar. Bu, bir milyon Integer nesnesi tutan bir HashSet'in kullanacağı birkaç on megabayta göre çok küçüktür. Ama evren büyük ve küme seyrekse hesap tersine döner. U = 10⁹ evreninden yalnız 3 öğe tutmak için bit vektörü yaklaşık 119 MB ayırır; hash tabanlı küme ise birkaç yüz bayt kullanır. Bu durumda hash tabanlı küme seçilir.

13.2.8Kod izleme: bit işlemleriyle küme cebri

Aşağıdaki kod a = {1, 3, 4} ve b = {3, 5} kümelerini bit vektörü olarak kurar, sonra birleşim, kesişim ve farkı hesaplar ve 3'ün a'da olup olmadığını sorar.

int a = 0, b = 0;
for (int x : new int[]{1, 3, 4})
  a |= 1 << x;          // x. biti yak
for (int x : new int[]{3, 5})
  b |= 1 << x;
int bir = a | b;        // birleşim
int kes = a & b;        // kesişim
int fark = a & ~b;      // fark
boolean var3 = (a >> 3 & 1) == 1;

İzlemenin ilk altı satırı küme kurmaktır. Her turda 1 << x yalnız x. biti yanık bir maske üretir: 1 << 1 = 2, 1 << 3 = 8, 1 << 4 = 16. VEYA ile bu bitler a'ya eklenir; a'nın değeri 2, 10, 26 olur. Aynı yolla b = 8 + 32 = 40 olur.

Birleşimde bitler tek tek VEYA'lanır: herhangi birinde 1 olan bit sonuçta 1'dir. 1., 3., 4. ve 5. bitler yanar; değer 58, küme {1, 3, 4, 5}'tir. Kesişimde VE kullanılır: yalnız iki sayıda da 1 olan bit kalır. Bu tek bit 3. bittir; değer 8, küme {3}'tür. Fark iki adımdır. ~b, b'nin bütün bitlerini tersine çevirir; artık 3. ve 5. bitler 0, ötekilerin hepsi 1'dir. a & ~b, a'nın bitlerinden yalnız b'de olmayanları bırakır: 1. ve 4. bitler. Değer 18, küme {1, 4}'tür.

Son satır üyelik testidir. a = 0001 1010 üç kez sağa kaydırılınca 0000 0011 olur; 3. bit en sağa gelmiştir. & 1 bu biti ayırır ve sonuç 1'dir: 3 kümededir. Bütün bu işlemler döngüsüz, tek komutluk işlemlerdir; her biri O(1)'dir.

13.3Çoklu küme ve çoklu eşleme

Kümenin tekrar yasağı çoğu problemde işe yarar, ama bazı problemlerde tam olarak tekrarlar önemlidir. Bir metinde “ve” kelimesinin kaç kez geçtiği, bir sepette kaç elma olduğu, bir seçimde bir adayın kaç oy aldığı birer sayma sorusudur. Bu sorular için kümenin bir uzantısı kullanılır.

13.3.1Çoklu küme

Çoklu küme M = {a, a, b, c, c, c} düşünelim. Burada a'nın çokluğu 2, b'ninki 1, c'ninki 3'tür. Öğeleri tek tek saklamak yerine her farklı öğeyi bir kez yazıp yanına çokluğunu koymak aynı bilgiyi taşır: {a:2, b:1, c:3}. Bu, çoklu kümenin doğal gerçeklemesidir: öğe → sayaç eşlemesi. Eşleme bir hash tablosu olduğunda her işlem tek bir anahtar erişimine iner.

Tablodaki size()'ın anlamına dikkat etmek gerekir. M'nin farklı öğe sayısı 3'tür, ama size() tekrarları da sayar ve 6 döndürür. Bu değeri her seferinde sayaçları toplayarak bulmak O(farklı öğe sayısı) sürerdi. Bunun yerine gerçekleme ayrı bir n sayacı tutar; her ekleme onu artırır, her silme azaltır. Böylece size() O(1) olur.

Çoklu küme pek çok yerde işe yarar. Metindeki kelime sıklıkları, alışveriş sepetindeki ürünler ve oy sayımı bunların en bilinenleridir. İki kelimenin aynı harflerden oluşup oluşmadığı da çoklu kümeyle sınanır: iki kelimenin harf sayaçları karşılaştırılır.

13.3.2Java ile çoklu küme

Java'nın standart kütüphanesinde hazır bir çoklu küme sınıfı yoktur. Bir HashMap<E, Integer> ile kolayca kurulur:

class CokluKume<E> {
    private final Map<E, Integer> say = new HashMap<>();
    private int n = 0;                                   // tekrarlar dahil öğe sayısı
    void add(E e) { say.merge(e, 1, Integer::sum); n++; }  // yoksa 1, varsa +1
    int count(E e) { return say.getOrDefault(e, 0); }
    boolean remove(E e) {
        Integer c = say.get(e);
        if (c == null) return false;                     // e yok
        if (c == 1) say.remove(e);                          // sayaç 0 olacak: girdiyi sil
        else say.put(e, c - 1);
        n--;
        return true;
    }
    int size() { return n; }
}

Sınıfın iki alanı vardır. say, her farklı öğeyi sayacına eşler; n, tekrarlar dahil öğe sayısıdır. Metotları sırayla okuyalım.

• add(e) tek satırdır: say.merge(e, 1, Integer::sum). merge metodu şöyle çalışır: e eşlemede yoksa onu verilen değerle (1) ekler. Varsa eski değerle yeni değeri verilen fonksiyonla birleştirir; burada fonksiyon toplamadır ve sayaç bir artar. Ardından n artırılır.
• count(e), getOrDefault(e, 0) ile sayacı okur. Öğe eşlemede yoksa null yerine 0 döner. Bu, çoklu kümenin anlamına uygundur: bulunmayan öğe 0 kez vardır.
• remove(e) önce sayacı okur. null ise öğe yoktur; metot false döndürür ve hiçbir şey değişmez. Sayaç 1 ise silme sonrası 0 olacaktır; girdi eşlemeden tamamen silinir. Sayaç 1'den büyükse bir azaltılır. Her iki durumda n azalır ve metot true döndürür.
• size() doğrudan n'yi döndürür.

Kümeyle farkı tek bir örnek açıkça gösterir. add("a"); add("a"); çağrılarından sonra count("a") 2 döndürür. Aynı iki çağrı bir Set'e yapılsaydı ikinci add etkisiz kalırdı; küme yalnız “a var” bilgisini tutardı. Sıralı gezinme gerekiyorsa HashMap yerine TreeMap<E, Integer> kullanılır; işlemler O(log n)'e çıkar, ama öğeler sıralı gezilir.

13.3.3Kod izleme: CokluKume sayaçları

Boş bir CokluKume<String> üzerinde şu çağrıları izleyelim: add("a"), add("b"), add("a"), add("c"), count("a"), remove("a"), remove("b"), remove("x"), count("b"). İzlemede kullanılan metot gövdeleri şunlardır:

void add(E e) {
  say.merge(e, 1, Integer::sum);  n++;
}
int count(E e) {
  return say.getOrDefault(e, 0);
}
boolean remove(E e) {
  Integer c = say.get(e);
  if (c == null) return false;
  if (c == 1) say.remove(e);
  else say.put(e, c - 1);
  n--;
  return true;
}

İzlemenin üçüncü satırı kümeyle farkı gösterir. "a" ikinci kez eklendiğinde merge eski sayaç 1 ile yeni değer 1'i toplar; sayaç 2 olur ve n 3'e çıkar. Bir Set'te bu çağrı kümeyi değiştirmezdi. İki remove çağrısı ise iki dalı ayrı ayrı çalıştırır. "a"nın sayacı 2'dir; else dalı onu 1'e indirir ve girdi eşlemede kalır. "b"nin sayacı 1'dir; if (c == 1) dalı girdiyi tamamen siler. Var olmayan "x" için say.get null döndürür ve metot ilk denetimde false ile çıkar; n değişmez. Son olarak count("b") 0 döndürür: silinmiş öğe ile hiç eklenmemiş öğe aynı sonucu verir. Sonuçta M = {a, c}, n = 2'dir.

Maliyet. Her metot eşlemeye bir kez (remove'da en çok iki kez) erişir. Hash tabanlı eşlemede bu erişimler ortalama O(1)'dir; bu yüzden bütün işlemler ortalama sabit süredir. Bellek, farklı öğe sayısı d ile orantılıdır: O(d). Tekrarlar ayrı ayrı saklanmadığı için milyonlarca kez geçen bir kelime de tek bir girdi tutar.

13.3.4Çoklu eşleme

Çoklu küme bir öğenin kaç kez geçtiğini tutar. Bazen sayı yetmez; tekrarların kendisi de gerekir. Bir dersi alan öğrencilerin kimler olduğunu bilmek istiyorsak her ders anahtarına bir öğrenci listesi bağlanmalıdır.

Java'da hazır bir çoklu eşleme sınıfı yoktur. Yapı, her anahtarı bir değer listesine eşleyen bir Map<K, List<V>> ile kurulur:

Map<String, List<String>> m = new HashMap<>();
void put(String k, String v) {   // yoksa boş liste aç
  m.computeIfAbsent(k, x -> new ArrayList<>()).add(v);
}
List<String> get(String k) {
  return m.getOrDefault(k, List.of());
}

put metodundaki computeIfAbsent(k, x -> new ArrayList<>()) çağrısı iki durumu tek satırda çözer. Anahtar eşlemede yoksa yeni bir boş liste oluşturur, eşlemeye koyar ve onu döndürür. Anahtar varsa mevcut listeyi döndürür. Her iki durumda dönen listeye add(v) uygulanır. get ise anahtar yoksa null yerine değiştirilemez boş bir liste (List.of()) döndürür; çağıran kod null denetimi yapmak zorunda kalmaz.

Şekil 13.11'deki eşleme altı put çağrısıyla kurulur: (BIL201, Ali), (BIL201, Ece), (BIL201, Can), (BIL203, Ece), (MAT101, Can), (MAT101, Zeynep). get("BIL201") [Ali, Ece, Can] döndürür; get("FIZ101") boş liste döndürür. Çoklu eşlemenin boyutu çift sayısıdır: 6. Anahtar sayısı ise 3'tür.

Maliyet. Hash tabanlı eşlemede put ve get ortalama O(1)'dir; get listeyi kopyalamadan döndürür. remove(k, v) önce listeyi bulur (O(1)), sonra listede v'yi arar; bu, liste boyu kadar sürer: O(1 + liste boyu). Çoklu kümeyle farkı özetlersek: çoklu küme yalnız kaç kez geçtiğini, çoklu eşleme değerlerin kendisini tutar.

13.4Ayrık kümeler ve Union-Find

Şimdiye kadar tek bir kümeyle ya da iki kümenin birleşimiyle çalıştık. Bazı problemlerde ise elimizde çok sayıda küme vardır ve bu kümeler zamanla birleşir. Bir sosyal ağda arkadaş grupları, bir haritada birbirine yolla bağlı şehirler, bir resimde aynı renkteki bitişik pikseller böyle problemlerdir. Hepsinde iki soru sorulur: “Şu iki öğe aynı grupta mı?” ve “Şu iki grubu birleştir.” Bu kesim, bu iki soruyu çok hızlı yanıtlayan yapıyı kurar.

13.4.1Ayrık kümeler

Temsilci, kümenin “adı” gibidir. Kümenin hangi öğesinin temsilci seçildiği önemli değildir. Önemli olan, aynı kümedeki bütün öğeler için find'ın aynı temsilciyi döndürmesidir. Böylece “x ile y aynı kümede mi?” sorusu iki find çağrısı ve bir karşılaştırmayla yanıtlanır.

Union-Find yapısı her kümeyi bir ağaç olarak saklar. Ağaçtaki her düğüm yalnız kendi ebeveynini (parent) gösterir; oklar çocuktan ataya doğrudur. Kök kendini gösterir ve kümenin temsilcisidir. Birden çok ağaçtan oluşan bu yapıya orman denir.

Şekil 13.12 bu gösterimi somutlaştırır. find(6), 6'dan başlayıp okları izler: 6 → 5 → 2 → 1. 1 kendini gösterdiği için köktür ve sonuç 1'dir. find(8) ise 8 → 4 → 3 yolunu izler ve 3'ü döndürür. 1 ≠ 3 olduğu için 6 ile 8 farklı kümelerdedir. Bu iki kümeyi birleştirmek için tek bir ok eklemek yeter: köklerden biri ötekini gösterecek biçimde değiştirilir, örneğin 1'in ebeveyni 3 yapılır.

Ağaçlar burada arama ağacı değildir. Düğümler arasında “küçük–büyük” düzeni yoktur, bir düğümün kaç çocuğu olacağı da sınırlı değildir. Ağacın tek görevi, aynı kümedeki öğeleri ortak bir köke bağlamaktır.

13.4.2Mıknatıs örneği

Masanın üzerine dağılmış 14 güçlü mıknatıs düşünelim. İki mıknatıs birbirine değdiğinde yapışır ve bir daha ayrılmaz. Birbirine yapışmış mıknatıslar bir grup oluşturur; bir mıknatıs başka bir grubun herhangi bir üyesine değerse iki grup bütünüyle birleşir. Birleşmeler sürerken her an şu soruyu yanıtlamak istiyoruz: “Şu iki mıknatıs aynı grupta mı?”

Önce her mıknatısa 1'den 14'e bir numara verilir. Başlangıçta her mıknatıs kendi grubundadır; 14 ayrık küme vardır ve her x için find(x) = x'tir. İki mıknatısın değmesi bir union, “aynı grupta mı?” sorusu iki find çağrısının karşılaştırılmasıdır.

Her başarılı birleşme grup sayısını tam olarak bir azaltır. İlk birleşmede 6 ile 8 yapışır; 13 grup kalır. union(2, 3)'te 2 tek başınadır, 3 ise {3, 4} grubundadır; 2 bu gruba katılır ve grup {2, 3, 4} olur. Üç birleşmeden sonra {9, 10, 13, 14}, üç birleşme daha sonra {5, 7, 11, 12} oluşur. Artık beş grup vardır: dört çok üyeli grup ve tek başına kalan 1.

Ardından soru sorulur: 4 ile 10 aynı grupta mı? find(4), {2, 3, 4} grubunun temsilcisini; find(10), {9, 10, 13, 14} grubunun temsilcisini döndürür. İkisi farklıdır, yanıt “hayır”dır. union(4, 10) bu iki grubu tek grupta birleştirir. Birleşmeler sürerse sonunda bütün mıknatıslar tek grupta toplanır ve find herkes için aynı kökü verir.

Örneğin önemli bir dersi vardır: Union-Find, grupların nasıl oluştuğunu (kimin kime değdiğini) hatırlamaz; yalnız kimin hangi grupta olduğunu bilir. 2'nin 3'e mi 4'e mi değdiği sonradan sorulamaz. Bu bilgiyi atmak, yapının bu kadar hızlı olmasının nedenlerinden biridir.

13.4.3find ve union işlemleri

İki işlemi biraz daha kesin tanımlayalım.

find(x), x'i içeren kümenin adını, yani ağacının kökünü döndürür. Bunun için ebeveyn bağlantıları kök bulunana kadar izlenir. Bu işlem arama ağaçlarındaki aramayla karıştırılmamalıdır. Arama ağacında bir değer aranır ve kökten aşağı inilir. find'da hiçbir değer aranmaz; düğüm zaten bellidir ve yukarı doğru köke çıkılır.

union(x, y), iki kümenin yerine ikisinin birleşimi olan tek bir küme koyar. Bunu yapmak için iki kökten biri ötekinin altına bağlanır. Kümeler baştan ayrık olduğu için birleşimde tekrar denetimi gerekmez; hiçbir öğe kopyalanmaz. Yalnız tek bir ebeveyn bağlantısı değişir. 13.1'deki küme birleşimiyle bu fark dikkat çekicidir: orada birleşim O(n + m) sürüyordu, burada (kökler bulunduktan sonra) O(1)'dir.

İki işlemin sözde kodu şöyledir:

find(x):
  if x.ebeveyn != x:
    x.ebeveyn = find(x.ebeveyn)  // yol kısaltma
  return x.ebeveyn

union(x, y):
  kök1 = find(x)
  kök2 = find(y)
  if kök1 != kök2:
    // bir kümenin kökünü diğer
    // kümenin köküne ebeveyn
    kök1.ebeveyn = kök2

find özyinelemelidir. Düğüm kendi ebeveyni değilse kök değildir; ebeveyninin kökü bulunur. Sözde koddaki atama (x.ebeveyn = find(x.ebeveyn)) yalnız kökü bulmakla kalmaz, bulunan kökü x'in yeni ebeveyni yapar. Bu ek işe yol kısaltma denir ve 13.5.4'te ayrıntısıyla ele alınır. union önce iki öğenin köklerini bulur. Kökler farklıysa birinci kökün ebeveyni ikinci kök yapılır; aynıysa öğeler zaten aynı kümededir ve hiçbir şey yapılmaz.

13.4.4Nesneleri indislere eşleme

Union-Find en verimli hâliyle bir tamsayı dizisi üzerinde çalışır. Öğeler 0..n − 1 arasındaki tamsayılardır ve ebeveyn[i], i öğesinin ebeveyninin indisini tutar. Dizi erişimi sabit süreli olduğundan ebeveyne çıkmak tek bir okumadır.

Gerçek problemlerde öğeler çoğu zaman harf, şehir ya da kişidir. Bu durumda her nesneye önce bir indis verilir. İndisler rastgele seçilebilir, ama bir kez verildikten sonra değişmemelidir. Nesne → indis eşlemesi bir hash tablosunda saklanır. Ardından her öğe için ebeveyn[i] = i yazılır; her öğe kendi tek öğeli kümesinin kökü olarak başlar. Bu başlangıç işlemine makeSet denir.

Map<Character, Integer> indis = new HashMap<>();   // 'E'→0, 'F'→1, …
int[] ebeveyn = new int[12];
for (int i = 0; i < 12; i++) ebeveyn[i] = i;             // 12 tekil küme

Bu kodun ilk satırı harf → indis eşlemesini tutar. İkinci ve üçüncü satır 12 hücreli ebeveyn dizisini kurar ve her hücreye kendi indisini yazar: 12 tekil küme. Harflerle çalışan bir union('C', 'K') çağrısı önce eşlemeden indisleri bulur (4 ve 9), sonra diziyle çalışır. Eşleme ortalama O(1) olduğu için bu çeviri işlemlerin maliyetini değiştirmez. Başlangıç O(n) sürer.

13.4.5union işlemi adım adım

Tablo 13.14'teki 12 harf üzerinde bir dizi union çağrısını izleyelim. Bu izlemede yol kısaltma kullanılmaz. Birleştirme kuralı şudur: küçük ağacın kökü büyük ağacın köküne bağlanır; boyutlar eşitse ikinci kök birincinin altına bağlanır. Ağacın boyutu, içindeki öğe sayısıdır. Bu kuralın neden seçildiği 13.5.2'de açıklanır; burada yalnız uygulayacağız. Her kökte ağacının boyutu tutulur.

İzlemenin bazı satırları özellikle öğreticidir. union(D, I)'da D kök değildir; ebeveyni C'dir. find(D) bu yüzden C'yi döndürür ve birleşme C'nin ağacıyla yapılır. Boyut 3 olan C ağacına tekil I bağlanır. union(C, A)'da iki büyük ağaç birleşir: C'nin ağacında {C, K, D, I} (boyut 4), A'nınkinde {A, J, B} (boyut 3) vardır. Küçük olan A'nın ağacı, kökü A ile C'nin altına girer; yeni boyut 7'dir.

İkinci union(A, B)'da iki find de C'yi döndürür: A'nın ebeveyni C'dir; B'nin yolu B → A → C'dir. Kökler aynıdır, hiçbir şey değişmez. Bu satır, aynı kümedeki iki öğeyi birleştirmeye çalışmanın zararsız olduğunu gösterir. Son çağrı union(H, B)'da H'nin kökü F (H → F), B'nin kökü C'dir. F'nin ağacı {F, E, L, H, G} (boyut 5), C'ninki 7 öğelidir; F, C'nin altına bağlanır. Artık 12 öğenin hepsi tek kümededir ve kök C'dir.

Son durumda “H ile B aynı kümede mi?” sorusunu yanıtlayalım. find(H): H → F → C, iki adım. find(B): B → A → C, iki adım. Kökler aynıdır; yanıt evettir ve toplam 4 adım sürmüştür. Ağacın yüksekliği 3'tür: en derin düğüm G'dir (G → H → F → C). 12 öğelik bir kümede yüksekliğin bu kadar küçük kalması tesadüf değildir; boyuta göre birleştirmenin sonucudur.

13.4.6Başka bir fikir: Quick-Find

Ağaçları hiç kullanmayan daha basit bir gösterim de düşünülebilir. Sedgewick ve Wayne'in Quick-Find (hızlı bul) adını verdiği bu yöntemde düz bir id dizisi tutulur: id[i], i öğesinin küme adıdır. Aynı kümedeki öğelerin id'leri aynıdır. Bu durumda find(p) tek bir dizi okumasıdır: id[p]. Süre O(1)'dir.

Bedeli union öder. union(p, q)'da p'nin kümesindeki bütün öğelerin adı q'nun küme adıyla değiştirilmelidir. Bu öğelerin nerede olduğu bilinmediği için bütün dizi taranır: O(n).

Tablo, bu kesimin ve bir sonrakinin yol haritasıdır. Quick-Find find'ı hızlı yapar ama her union diziyi tarar; n öğeyi tek kümede toplamak için gereken n − 1 birleşme O(n²) sürer. Ebeveyn ağacının naif hâli (Quick-Union) union'ı ucuzlatır, ama ağaç uzayabilir ve find yüksekliğe bağlı kalır. En iyi sonuç, ağaçları basık tutan iki iyileştirmenin birlikte kullanılmasıyla elde edilir; tablodaki α(n) 13.5.5'te tanıtılır ve pratikte 4'ten büyük olmaz.

13.4.7Kod izleme: Quick-Find union

int find(int p) { return id[p]; }  // O(1)
void union(int p, int q) {
  int pid = id[p], qid = id[q];
  if (pid == qid) return;
  for (int i = 0; i < id.length; i++)
    if (id[i] == pid)
      id[i] = qid;           // O(n) tarama
}

find tek satırdır. union önce iki küme adını okur: pid = id[p], qid = id[q]. Adlar eşitse öğeler zaten aynı kümededir ve metot hemen döner. Değilse dizinin her hücresine bakılır; küme adı pid olan her hücreye qid yazılır.

Kodu Şekil 13.15'teki durumdan başlayarak izleyelim: id = [1, 1, 3, 3, 4, 5]. Önce union(1, 3), sonra union(4, 3) çağrılıyor.

union(1, 3)'te pid = 1'dir; 0 ve 1 numaralı hücrelerin adı 3 olur. 2–5 numaralı hücrelere de bakılır, ama hiçbiri değişmez. union(4, 3)'te yalnız 4 numaralı hücre değişir. Buna karşın döngü yine altı hücrenin altısına da bakar. Değişen hücre sayısı 2 ya da 1 olsa da bakılan hücre sayısı her seferinde 6'dır.

Maliyet. Her union n hücreye bakar: O(n). Bütün öğeleri tek kümede toplamak n − 1 birleşme gerektirir; toplam (n − 1) · n hücre bakışı, yani O(n²). 8 öğe için bu 7 · 8 = 56 bakıştır; bir milyon öğe için yaklaşık 10¹²'dir ve pratikte kullanılamaz. Quick-Find'ın asıl dersi, find'ı sabit yapmanın union'ı pahalılaştırdığıdır. Ebeveyn ağacı bu dengeyi tersine çevirir.

13.5Union-Find'ı hızlandırmak

Ebeveyn ağacıyla union, kökler bulunduktan sonra tek bir atamadır. Bütün maliyet find'dadır ve find, düğümün kökten uzaklığı kadar adım atar. Bu yüzden Union-Find'ı hızlandırmanın yolu ağaçları basık tutmaktan geçer. Bu kesim iki basit fikri ve bunların birlikte verdiği şaşırtıcı sonucu anlatır.

13.5.1Neden iyileştirme gerekir?

Naif union(x, y) her zaman x'in kökünü y'nin kökünün altına bağlasın. Beş tekil kümede sırasıyla union(1, 2), union(2, 3), union(3, 4), union(4, 5) yapılırsa ne olur? İlk çağrıda 1, 2'nin altına girer. İkincide 2'nin iki öğeli ağacı tekil 3'ün altına girer; zincir 1 → 2 → 3 olur. Her yeni çağrıda büyüyen ağaç tek bir düğümün altına girer ve zincir bir kat uzar. Sonunda ağaç 1 → 2 → 3 → 4 → 5 zinciridir. Yüksekliği n − 1 = 4'tür ve find(1) dört bağlantı izler.

Aynı çağrılar “küçük ağacı büyük ağacın altına bağla” kuralıyla yapılsaydı sonuç bambaşka olurdu. İlk çağrıda iki tekil düğüm vardır; 1 yine 2'nin altına girer. Sonraki her çağrıda tekil düğüm (3, sonra 4, sonra 5) büyük ağacın kökü 2'ye eklenir. Ağaç bir yıldızdır; yüksekliği 1'dir ve her find en çok bir adım sürer.

Zincir oluştuğunda her find O(n) sürer. Kötü sıralı bir işlem dizisinde m find O(m · n) tutar; bu, Quick-Find'dan bile kötü olabilir. İki basit fikir ağaçları basık tutar: (1) boyuta ya da rütbeye göre birleştirme ve (2) yol kısaltma. Birlikte kullanıldıklarında işlem başına süre neredeyse sabittir: O(α(n)).

13.5.2Boyuta göre birleştirme

Kuralın gerekçesi şöyle düşünülebilir. Bir ağaç başka bir kökün altına bağlandığında o ağaçtaki her düğümün derinliği bir artar. Derinliği artan düğüm sayısını az tutmak için küçük ağaç taşınmalıdır. Büyük ağaç yerinde kalır ve onun düğümlerinin derinliği değişmez.

Şekil 13.18 bunu bir örnekle gösterir. Naif yöntem büyük ağacı küçüğün altına koyarsa 2, 3, 6 ve 9'un derinliği birer artar. 9'un derinliği 2'den 3'e çıkar ve find(9) uzar. Boyuta göre yöntem küçük ağacı taşır. 1, 4 ve 7'nin derinliği bir artar, ama bunlar sığ düğümlerdir: 4 ve 7 derinlik 2'ye iner, en derin düğüm yine 9'dur. Yükseklik 2'de kalır.

Teorem, 13.4.5'teki izlemeyle uyumludur: 12 öğe için ⌊log₂ 12⌋ = 3'tür ve ağacın yüksekliği gerçekten 3 olmuştu. Sınıra eşitlik de ulaşılabilir. 8 öğeyi önce ikişerli, sonra dörderli, sonra sekizli eşit boyutlu ağaçlarda birleştirirsek yüksekliği log₂ 8 = 3 olan bir ağaç elde ederiz. Teorem bundan daha kötüsünün olamayacağını söyler.

13.5.3Rütbeye göre birleştirme

Boyut yerine ağacın yüksekliğini izlemek de aynı işi görür. Ama yol kısaltma kullanıldığında gerçek yüksekliği güncel tutmak pahalıdır: bir find ağacın yüksekliğini değiştirebilir ve bunu anlamak için bütün ağacı dolaşmak gerekir. Bu yüzden yüksekliğin yerine onun bir üst sınırı tutulur.

CLRS'deki sözde kod, işlemi üç parçaya ayırır:

makeSet(x):
  ebeveyn[x] = x
  sira[x] = 0

find(x):   // yol kısaltmalı
  if x != ebeveyn[x]:
    ebeveyn[x] = find(ebeveyn[x])
  return ebeveyn[x]

link(x, y):   // x, y kök
  if sira[x] > sira[y]:
    ebeveyn[y] = x
  else:
    ebeveyn[x] = y
    if sira[x] == sira[y]:
      sira[y] = sira[y] + 1

union(x, y):
  link(find(x), find(y))

makeSet(x) tek öğeli bir küme kurar: x kendinin ebeveynidir, rütbesi 0'dır. find(x) yol kısaltmalıdır. link(x, y) iki kökü bağlar. x'in rütbesi büyükse y, x'in altına girer. Değilse x, y'nin altına girer; rütbeler eşitse y'nin rütbesi bir artar. union(x, y) önce iki kökü bulur, sonra onları link ile bağlar. Kodda sira dizisi rütbeyi tutar.

Eşit rütbede neden artırma yapılır? Rütbesi r olan iki ağaç birleşince birinin kökü ötekinin çocuğu olur. O ağacın en derin düğümü bir kat aşağı iner ve yeni ağacın yüksekliği r + 1'e çıkabilir. Rütbeler farklıysa alçak ağaç bağlanır; onun derinleşen düğümleri yüksek ağacın yüksekliğini aşamaz ve rütbe değişmez.

Bu sınıra da ulaşılabilir. 16 öğe önce ikişer ikişer, sonra dörder dörder, sonra sekizer sekizer birleştirilsin. En son iki sekizli ağaç birleşince kökün rütbesi 4 = log₂ 16 olur.

Yol kısaltma devreye girdiğinde rütbe ile gerçek yükseklik birbirinden ayrılabilir. Yol kısaltma ağacı basıklaştırır, ama rütbeyi güncellemez. Bu yüzden rütbe yalnız bir üst sınırdır; gerçek yükseklik rütbeden küçük olabilir. Bu bir hata değildir. Rütbe, karar vermek için yeterince iyi bir ölçüdür ve onu güncel tutmak hiçbir ek maliyet gerektirmez.

13.5.4Yol kısaltma

İkinci fikir find'ın kendisini kullanır. find(x) kökü bulmak için x'ten köke kadar bir yol yürür. Bu yoldaki her düğümün kökü de aynıdır. Yürüyüş bitince bu düğümlerin hepsini doğrudan köke bağlamak, sonraki find'ları tek adıma indirir.

Özyinelemeli find'da bu iş kendiliğinden olur: ebeveyn[x] = find(ebeveyn[x]). Özyineleme köke kadar iner; dönüşte her çağrı, kendisine dönen kökü düğümünün yeni ebeveyni yapar.

Şekil 13.19 üzerinde find(3)'ü izleyelim. Özyineleme 3'ten başlar: ebeveyn[3] = 6, kök değildir, find(6) çağrılır. 6'nın ebeveyni 5'tir, find(5) çağrılır. 5'in ebeveyni 7'dir, find(7) çağrılır. 7 kendini gösterir; köktür ve 7 döner. Dönüşte find(5), ebeveyn[5] = 7 yazar; değer zaten 7'dir. find(6), ebeveyn[6] = 7 yazar; 6 artık doğrudan köke bağlıdır. find(3), ebeveyn[3] = 7 yazar. Sonuç olarak 3'ün yolu üç adımdan bir adıma iner. 6'nın çocuğu olan 10 bu yolda değildi, ebeveyni değişmedi. Buna karşın 10'un yolu da kısaldı: 10 → 6 → 7, yani iki adım.

Yol kısaltma tek bir find'ı hızlandırmaz; aksine o find biraz daha çok iş yapar (her düğüme bir yazma). Kazanç sonraki işlemlerdedir. Bir kez uzun bir yol yürüyen find, o yolu ortadan kaldırır ve aynı düğümlere yapılan sonraki sorgular ucuzlar. Bu, maliyetin tek tek işlemlere göre değil, işlem dizisi üzerinden ortalandığı amortize analizin tipik bir örneğidir.

13.5.5Karmaşıklık ve ters Ackermann fonksiyonu

Tablonun ilk iki satırı önceki kesimlerden bellidir. union'ın maliyeti iki find'ın maliyetidir; bağlama sabit süredir. Üçüncü satır, yalnız yol kısaltma kullanıldığında da işlem başına ortalama maliyetin logaritmik olduğunu söyler. Tek bir find uzun sürebilir, ama uzun yollar bir kez yüründükten sonra kısaldığı için dizinin toplamı sınırlı kalır.

Son satır bölümün en çarpıcı sonucudur. Burada α(n), ters Ackermann fonksiyonudur. Ackermann fonksiyonu A_k(j) akıl almaz bir hızla büyür: k bir arttığında yeni fonksiyon, bir öncekinin kendini art arda uygulamasıyla elde edilir. Ters fonksiyon α(n), A_k(1) ≥ n olan en küçük k'dir ve tam tersine son derece yavaş büyür. CLRS'deki tanımla A₄(1), 10⁸⁰'den (gözlenebilir evrendeki atom sayısının kestirimi) kat kat büyüktür. Bu yüzden evrendeki atom sayısı kadar öğe için bile α(n) ≤ 4'tür. Pratikte α(n) bir sabit gibi davranır.

Teoremin ispatı bu notun kapsamını aşar; CLRS'de ayrı bir kesim olarak verilir. Sonucu üç noktayla yorumlamak yeterlidir. Birincisi, sınır amortizedir: tek bir find yine O(log n) sürebilir, ama dizinin toplamı O(m · α(n))'yi aşmaz. İkincisi, sınır sıkıdır: Tarjan aynı makalede bu algoritmanın m · α ile orantılı süre harcadığı işlem dizileri bulunduğunu da göstermiştir. Yani algoritma tam doğrusal süreye inmez; makalenin başlığındaki “iyi ama doğrusal olmayan” nitelemesi buradan gelir. Üçüncüsü, bellek gereksinimi küçüktür: iki tamsayı dizisi, ebeveyn[n] ve sira[n] (ya da boyut[n]), yani O(n).

Union-Find'ın kullanıldığı yerler çeşitlidir. Kruskal'ın minimum kapsayan ağaç algoritması bir kenarın döngü oluşturup oluşturmadığını find ile sorar. Bir çizgenin bağlantılı bileşenleri kenarlar geldikçe birleştirilerek bulunur (13.5.10). Resim işlemede aynı renkteki bitişik pikseller bölgelere ayrılır (bölge etiketleme). Bir bilgisayar ağında iki makinenin birbirine ulaşıp ulaşamayacağı sorgulanır.

13.5.6Java: düğüm tabanlı Union-Find

Union-Find, öğeleri nesne olarak da tutabilir. Her düğüm, verisini, rütbesini ve ebeveyninin referansını saklar:

class SetDugum {
  int veri;
  int sira;   // rütbe
  SetDugum ebeveyn;

  SetDugum(int veri) {
    this.veri = veri;
    this.ebeveyn = this;
    this.sira = 0;
  }
}

SetDugum find(SetDugum d) {
  if (d != d.ebeveyn)
    d.ebeveyn = find(d.ebeveyn); // kısaltma
  return d.ebeveyn;
}

Yapıcı, düğümü kendi ebeveyni yapar ve rütbesini 0'a ayarlar; bu, makeSet'in nesne karşılığıdır. find, sözde kodun Java çevirisidir: düğüm kendi ebeveyni değilse ebeveyninin kökü bulunur, bu kök düğümün yeni ebeveyni yapılır (yol kısaltma) ve döndürülür. Karşılaştırma d != d.ebeveyn referans karşılaştırmasıdır; burada doğru olan da budur, çünkü sorulan, iki referansın aynı nesneyi gösterip göstermediğidir.

void union(SetDugum x, SetDugum y) {
  SetDugum kokX = find(x);
  SetDugum kokY = find(y);
  if (kokX == kokY) return;
  // rütbeye göre birleştirme
  if (kokX.sira < kokY.sira) {
    kokX.ebeveyn = kokY;
  } else if (kokX.sira > kokY.sira) {
    kokY.ebeveyn = kokX;
  } else { // eşit: birini seç
    kokX.ebeveyn = kokY;
    kokY.sira++;
  }
}

union iki kökü bulur. Kökler aynı nesneyse öğeler zaten aynı kümededir. Değilse rütbeler karşılaştırılır: küçük rütbeli kök büyük rütbelinin altına girer. Rütbeler eşitse kokX, kokY'nin altına girer ve kokY'nin rütbesi bir artar. Bu yaklaşımın üstünlüğü, öğelerin doğrudan nesne olarak kullanılmasıdır; indis eşlemesine gerek kalmaz. Bedeli bellek ve hızdır: her düğüm ayrı bir nesnedir ve referans izlemek, dizi okumaktan yavaştır.

13.5.7Java: dizi tabanlı Union-Find

Öğeler 0..n − 1 indisleriyse aynı yapı iki tamsayı dizisiyle yazılır. Bu, pratikte en çok kullanılan biçimdir:

class UnionFind {
  private final int[] ebeveyn, sira;
  UnionFind(int n) {
    ebeveyn = new int[n];  sira = new int[n];
    for (int i = 0; i < n; i++) ebeveyn[i] = i;
  }
  int find(int x) {
    if (ebeveyn[x] != x) ebeveyn[x] = find(ebeveyn[x]);
    return ebeveyn[x];
  }
  boolean union(int x, int y) {
    int kx = find(x), ky = find(y);
    if (kx == ky) return false;
    if (sira[kx] < sira[ky]) ebeveyn[kx] = ky;
    else if (sira[kx] > sira[ky]) ebeveyn[ky] = kx;
    else { ebeveyn[kx] = ky; sira[ky]++; }
    return true;
  }
}

Yapıcı iki diziyi ayırır. Her öğe kendi ebeveynidir; sira dizisi Java'nın varsayılanıyla sıfırlarla başlar. find, özyinelemeli yol kısaltmayı tek satırda yapar. union, iki kökü bulur ve aynılarsa false döndürür. Değilse rütbeye göre bağlar ve true döndürür.

union'ın boolean döndürmesi bilinçli bir tasarım kararıdır. Dönüş değeri, “bu çağrı iki farklı kümeyi gerçekten birleştirdi mi?” sorusunun yanıtıdır. Kruskal algoritması bir kenarı eklemeden önce tam olarak bunu sorar: kenarın iki ucu zaten aynı kümedeyse kenar bir döngü kapatır ve atlanır. Bağlantılı bileşen sayma da (13.5.10) aynı bilgiyle çalışır.

Kısa bir kullanım örneği: UnionFind uf = new UnionFind(5); uf.union(0, 1); uf.union(3, 4); çağrılarından sonra uf.find(1) == uf.find(0) true, uf.find(1) == uf.find(3) false verir. İlk birleşmede rütbeler eşittir; 0, 1'in altına girer ve sira[1] = 1 olur. İkincide 3, 4'ün altına girer.

13.5.8Kod izleme: find ve union

Dizi tabanlı yapıyı 6 öğe üzerinde izleyelim. Çağrı dizisi şudur: union(0, 1), union(2, 3), union(0, 2), union(4, 0), union(1, 4). İzlemede kullanılan metotlar şunlardır:

int find(int x) {
  if (ebeveyn[x] != x) ebeveyn[x] = find(ebeveyn[x]);
  return ebeveyn[x];
}
boolean union(int x, int y) {
  int kx = find(x), ky = find(y);
  if (kx == ky) return false;
  if (sira[kx] < sira[ky]) ebeveyn[kx] = ky;
  else if (sira[kx] > sira[ky]) ebeveyn[ky] = kx;
  else { ebeveyn[kx] = ky; sira[ky]++; }
  return true;
}

İlk iki çağrıda bütün öğeler köktür; her find ilk denetimde kendini döndürür. Rütbeler eşit olduğu için else dalı çalışır: ebeveyn[kx] = ky ve sira[ky]++. Böylece {0, 1} kümesinin kökü 1, {2, 3} kümesinin kökü 3 olur; ikisinin de rütbesi 1'dir.

Üçüncü çağrı union(0, 2)'de öğeler artık kök değildir. find(0): ebeveyn[0] = 1 ≠ 0, find(1) çağrılır; 1 köktür ve döner. Dönüşte ebeveyn[0] = 1 yazılır; 0 zaten kökün çocuğudur, bir şey değişmez. Aynı biçimde find(2) = 3'tür. Kökler 1 ve 3'tür, rütbeleri eşittir (1). 1, 3'ün altına girer ve sira[3] = 2 olur. Bu çağrıdan sonra ağaç şöyledir: kök 3; çocukları 2 ve 1; 1'in çocuğu 0. Yükseklik 2'dir ve rütbe 2 bunu doğru gösterir.

Dördüncü çağrı union(4, 0) yol kısaltmanın etkisini gösterir. find(4) hemen 4'ü döndürür. find(0) ise iki katlı bir özyinelemedir: 0 → 1 → 3. find(3) 3'ü döndürür. Dönüşte find(1), ebeveyn[1] = 3 yazar (zaten 3'tür). find(0), ebeveyn[0] = 3 yazar; 0'ın ebeveyni 1'den 3'e değişir. 0 artık doğrudan köke bağlıdır. Kökler 4 ve 3'tür. sira[4] = 0 < sira[3] = 2 olduğu için alçak ağacın kökü 4, 3'e bağlanır; rütbe değişmez ve yükseklik artmaz.

Son çağrı union(1, 4)'te iki find de 3'ü döndürür: 1 ve 4 doğrudan 3'ün çocuklarıdır. kx == ky olduğu için metot false döndürür. Kruskal algoritmasının diliyle bu kenar bir döngü kapatırdı ve atlanırdı.

İzlemenin sonunda rütbe ile yükseklik arasındaki fark da görülür. sira[3] = 2'dir, ama yol kısaltma 0'ı köke taşıdığı için gerçek yükseklik 1'dir. Rütbe bir üst sınır olarak doğru kalır. Rütbe ve yol kısaltma birlikte işlem başına yaklaşık O(α(n)) maliyet verir.

13.5.9Döngüyle find ve yol kısaltma

Özyineleme yığın taşması riski taşıdığından find iki döngüyle de yazılabilir. Birinci döngü kökü bulur. İkinci döngü aynı yolu yeniden yürür ve yoldaki her düğümü köke bağlar:

int find(int x) {
  int kok = x;
  while (ebeveyn[kok] != kok) kok = ebeveyn[kok];
  while (ebeveyn[x] != kok) {    // yol kısaltma
    int sonraki = ebeveyn[x];
    ebeveyn[x] = kok;
    x = sonraki;
  }
  return kok;
}

Birinci döngüde kok değişkeni x'ten başlar ve ebeveyn bağlantılarını izleyerek kendini gösteren düğüme, yani köke ulaşır. İkinci döngüde x yine baştan başlar. Her adımda önce eski ebeveyn sonraki değişkenine saklanır; sonra ebeveyn[x] = kok yazılır ve x = sonraki ile bir yukarı çıkılır. Eski ebeveyni önce saklamak zorunludur: ebeveyn[x] değiştirildikten sonra yolun devamı kaybolurdu. Döngü, ebeveyn[x] zaten köke eşit olduğunda durur.

Kötü birleştirmeler sonucu oluşmuş ebeveyn = [0, 0, 1, 2, 3] zincirinde (4 → 3 → 2 → 1 → 0) find(4)'ü izleyelim.

Birinci döngü dört adımda köke ulaşır: 4 → 3 → 2 → 1 → 0. İkinci döngü üç düğümü kısaltır: 4, 3 ve 2'nin ebeveyni 0 olur. 1 zaten köke bağlıdır; döngü onda durur. Metot 0'ı döndürür. İşlemden sonra bütün düğümler doğrudan köke bağlıdır ve sonraki her find tek adım sürer. Özyineleme kullanılmadığı için zincir ne kadar uzun olursa olsun yığın taşması riski yoktur.

Maliyet. İki döngü aynı yolu birer kez yürür; süre yol uzunluğunun iki katıdır, yani yine O(yol uzunluğu). Özyinelemeli sürümle aynı kısaltmayı yapar, ek bellek ise O(1)'dir; özyinelemeli sürüm yol uzunluğu kadar çağrı çerçevesi kullanır.

13.5.10Uygulama: bağlantılı bileşen sayma

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. n düğümlü ve kenarları verilmiş bir çizgede kaç bileşen vardır? Union-Find bu soruyu doğal biçimde yanıtlar: her düğüm başta kendi bileşenindedir ve her kenar, iki ucunun bileşenlerini birleştirir.

int bilesenSay(int n, int[][] kenar) {
  UnionFind uf = new UnionFind(n);
  int say = n;          // n tekil küme
  for (int[] e : kenar)
    if (uf.union(e[0], e[1]))
      say--;            // iki bileşen birleşti
  return say;
}

Sayaç say, n ile başlar: kenar yokken her düğüm ayrı bir bileşendir. Her kenar için union çağrılır. union true döndürürse iki farklı bileşen birleşmiştir ve bileşen sayısı bir azalır. false döndürürse kenarın iki ucu zaten aynı bileşendedir; kenar bir döngü kapatır ve sayaç değişmez. union'ın dönüş değeri burada da işin kalbidir.

Metodu 7 düğüm ve 5 kenarla izleyelim: (0, 1), (1, 2), (3, 4), (0, 2), (5, 6).

Kenar (1, 2)'de 1'in rütbesi 1, 2'ninki 0'dır; 2, 1'in altına girer ve rütbe değişmez. Kenar (0, 2)'de iki ucun kökü de 1'dir: 0 ile 2, 1 üzerinden zaten bağlıdır. union false döndürür ve say 4'te kalır. Bu kenar 0–1–2 üçgenini kapatan döngü kenarıdır. Son kenardan sonra üç bileşen kalır: {0, 1, 2}, {3, 4}, {5, 6}. Metot 3 döndürür.

Maliyet. Yapıyı kurmak O(n)'dir. m kenarın her biri için bir union, yani iki find yapılır. Toplam süre O(n + m · α(n))'dir. Aynı soru derinlik öncelikli aramayla da O(n + m)'de yanıtlanabilir. Union-Find'ın üstünlüğü dinamik bağlılıktadır: kenarlar teker teker geldiğinde sayaç her kenardan sonra anında günceldir. Derinlik öncelikli arama ise her yeni kenarda baştan çalıştırılmak zorundadır. “Her kenardan sonra çizge bağlı mı?” sorusu da aynı sayaçla yanıtlanır: say == 1 ise çizge bağlıdır.

13.6Sık yapılan hatalar

Bölüm boyunca yeri geldikçe değinilen hatalar, iki gruba ayrılır. İlk üçü Java kümeleriyle, son üçü Union-Find ve sıralı kümelerle ilgilidir.

İlk hata özellikle sinsidir, çünkü program hata vermez; yalnız yanlış sonuç üretir. x ve y alanlarından hash kodu hesaplanan bir Nokta nesnesi (1, 2) iken kümeye eklensin. Nesne, (1, 2)'nin hash kodunun gösterdiği kovaya yerleşir. Ardından p.x = 5 yazılırsa nesnenin hash kodu değişir, ama nesne eski kovasında durur. set.contains(p) yeni hash kodunun kovasına bakar ve nesneyi bulamaz. Kümenin boyutu yine 1'dir; nesne kümededir, ama ona ulaşılamaz. Bu yüzden kümelerde ve eşlemelerde anahtar olarak değiştirilemez nesneler (String, Integer, record) tercih edilir.

Üçüncü hatanın nedeni, yineleyicinin kümenin yapısal değişikliklerini izlemesidir. For-each döngüsü arka planda bir yineleyici kullanır. Döngü sürerken küme başka bir yoldan değişirse yineleyici bunu bir sonraki adımda fark eder ve istisna fırlatır. removeIf silme işini yineleyicinin kendi remove metoduyla yaptığı için güvenlidir.

13.7Özet

• Küme, tekil öğelerden oluşan sırasız bir koleksiyondur. Temel işlemleri ekleme, çıkarma ve üyelik testidir. Küme işlemleri birleşim (∪), kesişim (∩), fark (−) ve alt küme (⊆) sorusudur; fark değişmeli değildir.
• Java'da küme ADT'si Set arayüzüdür. add öğe zaten varsa false döndürür; bu, tekrarı tek çağrıda bulmayı sağlar. addAll, retainAll, removeAll birleşim, kesişim ve farkı yerinde hesaplar; asıl kümeyi korumak için önce kopya alınır.
• Hash tabanlı kümede öğe, hash kodundan hesaplanan kovaya yerleşir; aynı kovaya düşen öğeler bir zincirde tutulur. Yük faktörü sabit tutulduğu sürece add, contains, remove ortalama O(1)'dir; kötü hash fonksiyonuyla en kötü O(n)'dir. equals ile hashCode birlikte ezilir.
• Ağaç tabanlı küme (TreeSet, kırmızı-siyah ağaç) her işlemi O(log n)'de yapar ve first, floor, ceiling, subSet gibi sıralı sorguları da aynı sürede yanıtlar. Eşitlik compare ile belirlenir.
• Sıralı dizilerde birleşim ve kesişim iki imleçle tek geçişte, O(n + m)'de hesaplanır. Ortak öğede iki imleç birlikte ilerler.
• Bit vektörü, evren küçükken kümeyi U bitle tutar. Tek öğe işlemleri ve (U ≤ 32 için) küme işlemleri tek makine komutudur; BitSet ile küme işlemleri O(U / 64)'tür. Seyrek kümelerde hash tabanlı küme daha az bellek kullanır.
• Çoklu küme her öğenin çokluğunu tutar; doğal gerçeklemesi öğe → sayaç eşlemesidir. Sayacı 0'a inen girdi silinir; size() tekrarları da sayar. Çoklu eşleme bir anahtarı bir değer listesine bağlar (Map<K, List<V>>).
• Ayrık kümeler öğeleri ortak öğesi olmayan gruplara ayırır. Union-Find her grubu bir ağaçla tutar; kök kümenin temsilcisidir. find köke çıkar, union iki kökü bağlar. Nesneler önce indislere eşlenir.
• Quick-Find find'ı O(1) yapar, ama her union bütün diziyi tarar: n − 1 birleşme O(n²). Naif ebeveyn ağacı zincire dönüşebilir ve find O(n) olur.
• Boyuta ya da rütbeye göre birleştirme yüksekliği ⌊log₂ n⌋ ile sınırlar; rütbesi r olan ağaçta en az 2^r öğe vardır. Yol kısaltma, find'ın yürüdüğü yoldaki düğümleri doğrudan köke bağlar. İkisi birlikte m işlemi O(m · α(n))'de bitirir (Tarjan, 1975); α(n) ≤ 4.
• union'ın boolean dönüşü “gerçekten birleştirdi mi?” sorusunun yanıtıdır. Bağlantılı bileşen sayımında başarılı her union sayacı bir azaltır; Kruskal algoritmasında false dönüşü döngü kuran kenarı gösterir.

13.8Kavram listesi

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

• küme set
• soyut veri tipi abstract data type (ADT)
• birleşim union
• kesişim intersection
• fark difference
• alt küme subset
• hash tablosu hash table
• hash kodu hash code
• kova bucket
• çakışma collision
• ayrı zincirleme separate chaining
• yük faktörü load factor
• ikili arama ağacı binary search tree (BST)
• kırmızı-siyah ağaç red-black tree
• kök ortada inorder
• birleştirme sıralaması merge sort
• bit vektörü bit vector
• çoklu küme multiset
• çoklu eşleme multimap
• eşleme map
• ayrık kümeler disjoint sets (union-find)
• ebeveyn parent
• kök root
• yükseklik height
• boyuta göre birleştirme union by size
• rütbe rank
• rütbeye göre birleştirme union by rank
• yol kısaltma path compression
• amortize analiz amortized analysis
• bağlantılı bileşen connected component
• Kruskal algoritması Kruskal's algorithm
• yineleyici iterator

13.9Kendini Dene

1. A = {1, 3, 5, 7, 9} ve B = {3, 6, 9} için A ∪ B, A ∩ B, A − B ve B − A nedir? {3, 9} ⊆ B ve B ⊆ A doğru mu?

   Cevap

   A ∪ B = {1, 3, 5, 6, 7, 9}, A ∩ B = {3, 9}, A − B = {1, 5, 7}, B − A = {6}. {3, 9} ⊆ B doğrudur. B ⊆ A yanlıştır, çünkü 6 ∉ A. Denetim: |A ∪ B| = 5 + 3 − 2 = 6.

2. ilkTekrar(new int[]{5, 1, 9, 1, 5}) ne döndürür? Metot dönene kadar kaç kez add çağrılır?

   Cevap

   1 döner. İlk üç add (5, 1, 9) true döndürür ve küme {1, 5, 9} olur. Dördüncü add(1) false döndürür; metot 1'i verir. Toplam 4 add yapılır; son öğe 5'e hiç bakılmaz. 5 de tekrar eder, ama 1'in tekrarı daha önce görülür.

3. 7 kovalı zincirlemeli bir hash kümesine (kova = x % 7) sırasıyla 14, 3, 21, 10, 3 ekleniyor. Her add ne döndürür, kovaların son durumu nedir? Ardından contains(17) kaç karşılaştırma yapar?

   Cevap

   Kovalar: 14 → 0, 3 → 3, 21 → 0, 10 → 3, 3 → 3. Dönüşler true, true, true, true, false'tur. Son durum: kova 0: 14 → 21, kova 3: 3 → 10, öteki kovalar boş, n = 4. contains(17): 17 mod 7 = 3; kova 3'teki 3 ve 10 ile karşılaştırılır (2 karşılaştırma) ve false döner.

4. birlesimKesisim metodu a = [2, 5, 8, 11] ve b = [1, 5, 11, 12, 15] ile çağrılıyor. bir ve kes ne olur? Ana döngü kaç tur döner?

   Cevap

   Turlar: 2 > 1 → 1 eklenir; 2 < 5 → 2 eklenir; 5 = 5 → ortak; 8 < 11 → 8 eklenir; 11 = 11 → ortak. Beşinci turdan sonra i = 4 = a.length olur ve ana döngü biter (5 tur). b'de kalan 12 ve 15 birleşime eklenir. Sonuç: bir = [1, 2, 5, 8, 11, 12, 15], kes = [5, 11].

5. a kümesi {0, 4, 6}, b kümesi {4, 5} bitleriyle kuruluyor. a, b, a | b, a & b ve a & ~b'nin sayı değerleri ve temsil ettikleri kümeler nedir?

   Cevap

   a = 1 + 16 + 64 = 81 (0101 0001), b = 16 + 32 = 48 (0011 0000). a | b = 113 (0111 0001) → {0, 4, 5, 6}. a & b = 16 → {4}. a & ~b = 65 (0100 0001) → {0, 6}. Birleşimde dört bit yanıktır: Integer.bitCount(a | b) = 4.

6. “kelebek” kelimesinin harfleri bir CokluKume<Character>'e ekleniyor. Ardından iki kez remove('e') ve bir kez remove('l') çağrılıyor. count('e'), count('l'), size() ne döndürür? Eşlemede kaç girdi kalır?

   Cevap

   Eklemelerden sonra eşleme {k:2, e:3, l:1, b:1}, n = 7'dir. İki remove('e') sayacı 3 → 2 → 1'e indirir. remove('l')'de sayaç 1 olduğu için girdi silinir. count('e') = 1, count('l') = 0, size() = 4. Eşlemede üç girdi kalır: {k:2, e:1, b:1}.

7. TreeSet S = {4, 9, 13, 18, 22, 30} için floor(20), ceiling(20), subSet(9, 22) ve floor(3) ne döndürür?

   Cevap

   floor(20) = 18 (≤ 20 olan en büyük), ceiling(20) = 22 (≥ 20 olan en küçük), subSet(9, 22) = [9, 13, 18] (9 dahil, 22 hariç). floor(3) null döndürür: 3'ten küçük ya da eşit öğe yoktur. Sonucu int'e atayan kod burada NullPointerException alır.

8. Dizi tabanlı UnionFind(6) üzerinde sırasıyla union(0, 1), union(1, 2), union(3, 4), union(4, 5), union(2, 5), union(0, 3) çağrılıyor. Son çağrı ne döndürür? ebeveyn ve sira dizilerinin son hâli nedir?

   Cevap

   (0, 1): eşit rütbe, 0 → 1, sira[1] = 1. (1, 2): rütbe 1 > 0, 2 → 1. (3, 4): 3 → 4, sira[4] = 1. (4, 5): 5 → 4. (2, 5): kökler 1 ve 4, rütbeler eşit (1); 1 → 4, sira[4] = 2. (0, 3): find(0) 0 → 1 → 4 yolunu yürür ve yol kısaltma 0'ı 4'e bağlar; find(3) = 4. Kökler aynıdır, çağrı false döndürür. Son hâl: ebeveyn = [4, 4, 1, 4, 4, 4], sira = [0, 1, 0, 0, 2, 0]. 2 hâlâ 1'e bağlıdır, çünkü hiçbir find 2'den geçmemiştir.

9. ebeveyn = [0, 0, 1, 2, 2, 4] iken döngüyle yazılmış find(5) çağrılıyor. Kök kaç adımda bulunur, dizinin son hâli nedir? 3'ün ebeveyni neden değişmez?

   Cevap

   Yol 5 → 4 → 2 → 1 → 0'dır; kök 4 adımda bulunur. İkinci döngü 5, 4 ve 2'yi doğrudan 0'a bağlar; 1 zaten köke bağlıdır. Son hâl [0, 0, 0, 2, 0, 0]'dır. 3, 2'nin çocuğudur, ama 5'ten köke giden yolda değildir; yol kısaltma yalnız yürünen yoldaki düğümleri değiştirir. 3'ün yolu yine de kısalmıştır: 3 → 2 → 0.

10. Boyuta göre birleştirmede (eşitlikte ikinci kök birincinin altına) 8 öğeli bir ağacın yüksekliği en çok kaç olabilir? Bu yüksekliği üreten bir union dizisi verin.

    Cevap

    Teoreme göre en çok ⌊log₂ 8⌋ = 3. Dizi: union(0,1), union(2,3), union(4,5), union(6,7) dört ikili ağaç; union(0,2) ve union(4,6) iki dörtlü ağaç; union(0,4) tek ağaç. Sonuçta ebeveyn = [0, 0, 0, 2, 0, 4, 4, 6]'dır ve 7'nin yolu 7 → 6 → 4 → 0, yani 3 adımdır. Her birleşme eşit boyutlu iki ağacı birleştirdiği için yükseklik her seferinde bir artmıştır.

13.10İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Kesim 10.5 ve 14.7: küme, çoklu küme ve çoklu eşleme ADT'lerini, genel birleştirme yöntemini ve Kruskal algoritması içinde Union-Find yapısını bu nottakine yakın bir Java diliyle anlatır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.5: Quick-Find'dan başlayıp Quick-Union, ağırlıklı birleştirme ve yol kısaltmaya giden adımları deneysel ölçümlerle karşılaştırır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 19: ayrık küme ormanlarını, rütbeye göre birleştirmeyi, yol kısaltmayı ve O(m · α(n)) sınırının ispatını biçimsel olarak verir.
• R. E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm” (1975): rütbe ve yol kısaltmanın birlikte ters Ackermann sınırını verdiğini ve bu sınırın sıkı olduğunu gösteren özgün makale.

13.11Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. B. A. Galler, M. J. Fischer, “An improved equivalence algorithm”, Communications of the ACM, 7(5), 301–303, 1964.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
4. Oracle, Java SE 17 API Specification: java.util.Set, HashSet, TreeSet ve BitSet belgeleri.
5. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.
6. R. E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM, 22(2), 215–225, 1975.

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