SEN2212 · 6. hafta · Using other balanced tree structure using Java.

Diğer dengeli ağaçlar: red-black, 2-3, B-ağacı, splay

Red-black ağacın beş kuralı ve ekleme durumları, 2-3 ağacında bölünme, B-ağacının diskteki rolü ve splay fikri. Sınavda renkli ağaç çizme ve bölünme izi sorusu buradan.

red-black treeblack-heightrecoloringuncle2-3 tree2-3-4 treenode splitB-treeorder of a B-treesplay treezig-zigzig-zagamortized cost

AVL tek dengeli ağaç değil. Pratikte en çok kullanılanı red-black ağaçtır: Java’nın TreeMap ve TreeSet sınıfları içeride red-black ağaç tutar. Veritabanları ve dosya sistemleri ise B-ağaçlarını kullanır. Bu hafta dört yapıyı görüyoruz. Sınavda red-black için “sırayla ekle, renkleriyle çiz”, 2-3 / B-ağacı için “bölünmeleri göster” soruları gelir. Splay ağacı genelde kavram sorusu olarak çıkar.

Hepsinin amacı aynı: ağacın yüksekliğini O(log n)‘de tutmak. Yöntemleri farklı:

Yapı	Denge nasıl sağlanır	Yükseklik
AVL	yükseklik farkı en fazla 1, rotasyon	yaklaşık 1.44 log2 n
Red-black	renk kuralları, rotasyon + boyama	en fazla 2 log2(n+1)
2-3 / B-ağacı	düğümde birden çok anahtar, bölünme	bütün yapraklar aynı derinlikte
Splay	erişilen düğümü köke taşı	garanti yok, amortized O(log n)

Red-black ağacın kuralları

Her düğüm kırmızı (red) ya da siyahtır (black). Ağaç bir BST’dir ve şu kurallara uyar:

Kök siyahtır.
Null bağlantılar (boş yapraklar) siyah sayılır.
Kırmızı bir düğümün çocukları kırmızı olamaz (arka arkaya iki kırmızı yok).
Bir düğümden aşağıdaki herhangi bir null’a giden her yolda aynı sayıda siyah düğüm vardır. Bu sayıya siyah yükseklik (black-height) denir.

Neden işe yarıyor? Kural 4’e göre her yolda aynı sayıda siyah var. Kural 3’e göre en uzun yolda kırmızılar ancak siyahların arasına tek tek serpiştirilebilir. Yani en uzun yol en kısa yolun en fazla iki katı. Buradan $height \le 2\log_2(n+1)$ çıkar.

         20B
        /   \
      10B    30B        her yolda 2 siyah
        \                (null'lar haric)
        15R

Ekleme: durumlar

Ekleme önce normal BST eklemesidir. Yeni düğüm hep kırmızı eklenir. Neden kırmızı? Siyah ekleseydin o yoldaki siyah sayısı artardı ve kural 4 her yerde bozulurdu. Kırmızı eklemek en fazla kural 3’ü bozar ve onu yerel olarak düzeltmek kolaydır.

Yeni düğüme x, ebeveynine p, dedesine g, dedenin diğer çocuğuna amca (uncle) u diyelim.

Durum	Ne yapılır
p siyah	Hiçbir şey, bitti.
p kırmızı, u kırmızı	Yeniden boyama: p ve u siyah, g kırmızı. Sonra g’yi yeni x kabul et, yukarıda tekrar kontrol et.
p kırmızı, u siyah, x “içeride” (LR ya da RL)	p’de rotasyon yap, durum düz hale gelir (LL ya da RR). Sonraki satıra geç.
p kırmızı, u siyah, x “dışarıda” (LL ya da RR)	g’de rotasyon (LL ise sağa, RR ise sola). p siyah, g kırmızı olur. Bitti.
Sonda	Kök kırmızı kaldıysa siyaha boya.

Null amca siyah sayılır. Rotasyon içeren durum en fazla bir kez olur ve ekleme orada biter. Yeniden boyama ise köke kadar tekrar edebilir ama her adım O(1), toplam O(log n).

TUZAK · Amcaya bak, kardeşe değil. Karar ebeveynin kardeşinin rengiyle verilir. Yeni düğümün kendi kardeşi hiçbir şeyi belirlemez.

Çözümlü örnek: 30, 20, 10, 25, 27, 5, 1

+30: kök, siyah. +20: ebeveyn siyah, bitti. +10: ebeveyn 20 kırmızı, amca (30’un sağı) null, yani siyah. Yol sol-sol: 30’da sağa rotasyon, 20 siyah, 30 kırmızı.

    30B           20B
    /            /   \
  20R    ==>   10R    30R
  /
10R

+25: 30’un soluna kırmızı. Ebeveyn 30 kırmızı, amca 10 kırmızı: yeniden boyama. 10 ve 30 siyah, 20 kırmızı, sonra kök olduğu için tekrar siyah.

+27: 25’in sağına. Ebeveyn 25 kırmızı, amca (30’un sağı) null: siyah. Dededen (30) yol sol-sağ, x içeride. Önce 25’te sola rotasyon (27 yukarı), sonra 30’da sağa rotasyon. 27 siyah, 30 kırmızı.

+5: 10’un soluna, ebeveyn siyah: bitti. +1: 5’in soluna. Ebeveyn 5 kırmızı, amca (10’un sağı) null: siyah. Yol sol-sol: 10’da sağa rotasyon, 5 siyah, 10 kırmızı.

         20B
       /     \
     5B       27B
    /  \     /   \
  1R   10R  25R   30R

Programın bastığı iz (her eklemeden sonra renkli seviye sırası):

+30 -> 30B
+20 -> 30B 20R
+10 -> 20B 10R 30R
+25 -> 20B 10B 30B 25R
+27 -> 20B 10B 27B 25R 30R
+5 -> 20B 10B 27B 5R 25R 30R
+1 -> 20B 5B 27B 1R 10R 25R 30R

Her kökten-null’a yolda 2 siyah düğüm (null’lar hariç) var, kırmızı-kırmızı yok.

İPUCU · Kitaptaki sürüm. Ders kitabı (Weiss) yukarıdan aşağı (top-down) red-black eklemeyi anlatır: aşağı inerken iki kırmızı çocuklu her düğümü önceden boyar, böylece yukarı geri dönmek gerekmez. Sonuç ağaç bazen farklı çıkabilir. Sınavda hangi sürümün istendiğine bak; bu sayfadaki izler aşağıdan yukarı (bottom-up) sürümle yapıldı.

2-3 ağaçları

2-3 ağacında her iç düğüm ya 2-düğüm (1 anahtar, 2 çocuk) ya da 3-düğümdür (2 anahtar, 3 çocuk). Bütün yapraklar aynı derinliktedir. Rotasyon yok; denge bölünmeyle (split) sağlanır.

Ekleme kuralı:

Anahtarın gideceği yaprağı bul, oraya sıralı ekle.
Yaprakta 3 anahtar olduysa taşma var: ortanca anahtar ebeveyne çıkar, kalan ikisi iki ayrı düğüm olur.
Ebeveyn de taşarsa aynı işlem yukarıda tekrar eder. Kök taşarsa yeni kök oluşur ve ağaç bir seviye uzar.

Ağaç yukarı doğru büyür. Bu yüzden bütün yapraklar hep aynı derinlikte kalır.

+10 +20      +30: [10 20 30] tasar
[10 20]         [20]
               /    \
            [10]    [30]

+40 +50:  [30 40 50] tasar, 40 cikar
          [20 40]
         /   |   \
      [10] [30]  [50]

2-3-4 ağaçları ve red-black bağlantısı

2-3-4 ağacı bir de 4-düğüme (3 anahtar, 4 çocuk) izin verir. Ekleme genelde yukarıdan aşağı yapılır: aşağı inerken rastlanan her 4-düğüm önceden bölünür, böylece yaprağa ulaşınca yer garantidir.

Asıl önemli nokta: her 2-3-4 ağacı bir red-black ağaca birebir karşılık gelir. 2-düğüm tek siyah düğümdür. 3-düğüm siyah + bir kırmızı çocuktur. 4-düğüm siyah + iki kırmızı çocuktur. Red-black’teki “amca kırmızı, yeniden boya” durumu, 2-3-4 ağacında bir 4-düğümün bölünmesidir. Siyah yüksekliğin her yerde aynı olması da 2-3-4 ağacında bütün yaprakların aynı derinlikte olmasının karşılığıdır.

B-ağaçları

B-ağacı, 2-3 fikrinin genellemesidir. Order (derece) m olan bir B-ağacında:

Her düğüm en fazla m - 1 anahtar, m çocuk tutar.
Kök dışındaki her iç düğümün en az $\lceil m/2 \rceil$ çocuğu (yani en az $\lceil m/2 \rceil - 1$ anahtarı) vardır.
Bütün yapraklar aynı derinliktedir.

2-3 ağacı, m = 3 olan B-ağacıdır. Gerçek sistemlerde m yüzlerce olur, çünkü bir düğüm bir disk bloğuna (örneğin 4 KB) denk getirilir. Diskten bir blok okumak, yüzlerce anahtarı bellekte karşılaştırmaktan çok daha yavaştır. Yükseklik $\log_m n$ civarında olduğundan, m = 200 ile milyonlarca kayıt 3-4 seviyeye sığar.

m = 5 ile ekleme izi (bir düğüm en fazla 4 anahtar; 5. anahtar gelince ortanca yukarı çıkar):

+12 +4 +30 +8 -> [4, 8, 12, 30]
+22 -> taşma, 12 çıkar
  L0: [12]
  L1: [4, 8] [22, 30]
+1 +17 +26 +3 ->
  L0: [12]
  L1: [1, 3, 4, 8] [17, 22, 26, 30]
+40 -> sağ yaprak taşar, 26 çıkar
  L0: [12, 26]
  L1: [1, 3, 4, 8] [17, 22] [30, 40]

Veritabanlarında genelde B+ ağacı kullanılır: bütün veriler yapraklarda durur, iç düğümler sadece yol gösterir ve yapraklar birbirine bağlıdır (aralık sorguları hızlanır).

Splay ağaçları

Splay ağacında denge bilgisi (yükseklik, renk) hiç tutulmaz. Bunun yerine her erişimden (arama, ekleme) sonra erişilen düğüm rotasyonlarla köke taşınır (splaying). Fikir: yakın zamanda kullanılan veriye yakında tekrar erişilir, kökte durması işe yarar.

Üç adım tipi var (x erişilen, p ebeveyn, g dede):

Adım	Ne zaman	Ne yapılır
zig	p köktür	x’te tek rotasyon
zig-zig	x ve p aynı yönde (sol-sol ya da sağ-sağ)	önce p’yi g’nin üstüne, sonra x’i p’nin üstüne döndür
zig-zag	farklı yönde	x’i iki kez döndür (AVL çift rotasyonu gibi)

Tek bir işlem O(n) sürebilir (zincirin dibine erişim). Ama zig-zig adımı yolu yaklaşık yarıya katladığı için, art arda m işlemin toplam maliyeti O(m log n) olur. Buna amortize (amortized) O(log n) denir. Önbellek (cache) benzeri kullanımda pratikte çok hızlıdır.

10(5(3,7),15)'te 3'e erisim: zig-zig
       10              3
      /  \              \
     5    15    ==>      5
    / \                   \
   3   7                   10
                          /  \
                         7    15

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
Red-black’te yeni düğüm siyah eklenir	Hep kırmızı eklenir; sonra gerekirse boyanır
Amca kırmızıysa rotasyon yapılır	Amca kırmızıysa sadece boyama, sonra dededen devam
Null amca “yok” sayılır, durum atlanır	Null siyahtır: rotasyon durumu
Boyamadan sonra kök kırmızı kalabilir	Kök her zaman en sonda siyaha boyanır
Red-black ağaç AVL kadar sıkı dengelidir	Daha gevşek (2 log n); karşılığında daha az rotasyon yapar
2-3 ağacı aşağı doğru büyür	Bölünme yukarı yayılır, yeni seviye kökte açılır
2-3 taşmasında en büyük anahtar yukarı çıkar	Ortanca (median) anahtar çıkar
B-ağacında her düğümde en az 1 anahtar yeter	Kök hariç en az ceil(m/2) - 1 anahtar
Splay ağacında her işlem O(log n) garantili	Tek işlem O(n) olabilir; garanti amortizedir

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

Which of the following is NOT a red-black tree property?

The root is black.
A red node cannot have a red child.
Every path from a node to its null descendants has the same number of black nodes.
The heights of the two subtrees of every node differ by at most 1.

Cevabı göster

The heights of the two subtrees of every node differ by at most 1.

Bu AVL kuralı. Red-black ağaç yükseklik farkını doğrudan sınırlamaz; renk kurallarıyla en uzun yolun en kısa yolun iki katını geçmemesini sağlar. Diğer üçü red-black kurallarıdır.

Soru 2kolay

Insert 10, 20, 30 into an empty red-black tree (standard bottom-up insertion). Give the level-order traversal with colors (B = black, R = red).

Cevabı göster

20B 10R 30R

10 kök, siyaha boyanır. 20 kırmızı eklenir, ebeveyn siyah: bitti.
30 kırmızı, ebeveyni 20 kırmızı. Amca (10'un sol çocuğu) null, yani siyah. Yol sağ-sağ: 10'da sola rotasyon, 20 siyah, 10 kırmızı olur.
Sonuç 20B, çocukları 10R ve 30R.

Soru 3orta

Continue the previous tree (20B, 10R, 30R) by inserting 15. Which case applies, and what is the resulting level-order with colors?

Cevabı göster

Uncle red, recolor only; 20B 10B 30B 15R

15 kırmızı olarak 10'un sağına girer. Ebeveyn 10 kırmızı, amca 30 de kırmızı: yeniden boyama (recolor) durumu.
10 ve 30 siyah, dede 20 kırmızı olur. 20 kök olduğu için en sonda tekrar siyaha boyanır. Rotasyon yok.
Siyah yükseklik bir arttı: 20B 10B 30B 15R.

Soru 4orta

Insert 1, 2, 3, 4, 5, 6, 7, 8 into an empty red-black tree. Give the final level-order traversal with colors.

Cevabı göster

4B 2R 6R 1B 3B 5B 7B 8R

+3: RR, 1'de sola rotasyon: 2B(1R,3R). +4: amca 1 kırmızı, recolor: 2B(1B,3B(-,4R)).
+5: amca null, RR, 3'te sola: 2B(1B,4B(3R,5R)). +6: amca 3 kırmızı, recolor: 4 kırmızı, 3 ve 5 siyah.
+7: RR, 5'te sola: 6B(5R,7R) olur, 4R'nin sağında. +8: amca 5 kırmızı, recolor: 6 kırmızı, 5 ve 7 siyah. Şimdi 6R'nin ebeveyni 4R: kırmızı-kırmızı yukarı taşındı. 4'ün amcası 1 siyah, yol (2'den) sağ-sağ: 2'de sola rotasyon, 4 siyah köke, 2 kırmızı.
Sonuç: 4B(2R(1B,3B), 6R(5B,7B(-,8R))).

Soru 5orta

A red-black tree contains n = 15 keys. Using the bound height <= 2 log2(n + 1), what is the largest height it can have?

Cevabı göster

$2\log_2(15 + 1) = 2 \cdot 4 = 8$ . Red-black ağaç AVL'den biraz daha uzun olabilir (AVL sınırı yaklaşık 1.44 log2 n), ama yine O(log n).

Soru 6kolay

Insert 10, 20, 30, 40, 50 into an empty 2-3 tree. Draw the final tree (list each level's nodes).

Cevabı göster

root [20, 40]; leaves [10] [30] [50]

10, 20 aynı yaprağa: [10, 20]. 30 gelince [10, 20, 30] taşar, ortanca 20 yukarı çıkar: kök [20], yapraklar [10] [30].
40: [30, 40]. 50: [30, 40, 50] taşar, 40 yukarı çıkar ve köke katılır: [20, 40]. Yapraklar [10] [30] [50]. Kök taşmadığı için yükseklik 1 kaldı.

Soru 7orta

Insert 50, 30, 70, 10, 40, 60, 80, 20 into an empty 2-3 tree. List the nodes of each level of the final tree.

Cevabı göster

L0: [50]; L1: [30] [70]; L2: [10, 20] [40] [60] [80]

50, 30 → [30, 50]. 70 → taşma, 50 çıkar: [50] / [30] [70].
10 → [10, 30]. 40 → [10, 30, 40] taşar, 30 köke: [30, 50] / [10] [40] [70].
60 → [60, 70]. 80 → [60, 70, 80] taşar, 70 köke çıkar: kök [30, 50, 70] de taşar, 50 yeni kök olur. Ağaç bir seviye uzar: [50] / [30] [70] / [10] [40] [60] [80].
20 → [10, 20], taşma yok.

Soru 8orta

In a B-tree of order m = 5, how many keys and how many children can a non-root internal node have?

Cevabı göster

2 to 4 keys, 3 to 5 children

En fazla m - 1 = 4 anahtar ve m = 5 çocuk. En az $\lceil m/2 \rceil = 3$ çocuk, yani 3 - 1 = 2 anahtar. Kök bu alt sınırdan muaftır (en az 1 anahtar).

Soru 9kolay

A database index is stored on disk, where each disk access is very slow compared with a CPU operation. Which tree is the standard choice, and why?

Cevabı göster

B-tree (or B+ tree), because it has a very small height and so needs few disk reads

B-ağacında bir düğüm bir disk bloğu kadardır ve yüzlerce anahtar tutar. Dallanma (m) büyük olduğu için yükseklik $\log_m n$ civarı: milyonlarca kayıt 3-4 seviyeye sığar. Her seviye bir disk okuması, yani 3-4 okuma. İkili ağaçta yükseklik 20+ olurdu.

Soru 10zor

Insert 20, 10, 30, 35, 33 into an empty red-black tree. Which case occurs when 33 is inserted, and what is the final level-order with colors?

Cevabı göster

Uncle black, RL case (double rotation); 20B 10B 33B 30R 35R

+35: amca 10 kırmızı, recolor: 20B(10B, 30B(-,35R)).
+33: 35'in soluna kırmızı. Ebeveyn 35 kırmızı, amca (30'un sol çocuğu) null, siyah. Dededen (30) yol sağ-sol: RL.
Önce 35'te sağa rotasyon (33 yukarı), sonra 30'da sola rotasyon. 33 siyah, 30 kırmızı olur: 33B(30R,35R).

Soru 11zor

Insert 8, 18, 5, 15, 17, 25, 40, 80 into an empty red-black tree. Give the final level-order traversal with colors.

Cevabı göster

17B 8R 25R 5B 15B 18B 40B 80R

+15: amca 5 kırmızı, recolor: 8B(5B,18B(15R)).
+17: 15'in sağına. Amca null, dededen (18) yol sol-sağ: LR. 15'te sola, 18'de sağa: 17B(15R,18R).
+25: amca 15 kırmızı, recolor: 17 kırmızı, 15 ve 18 siyah.
+40: ebeveyn 25 kırmızı, amca null, sağ-sağ: 18'de sola rotasyon, 25B(18R,40R).
+80: amca 18 kırmızı, recolor: 25 kırmızı, 18 ve 40 siyah. Şimdi 25R'nin ebeveyni 17R. 17'nin amcası 5 siyah, 8'den yol sağ-sağ: 8'de sola rotasyon, 17 siyah köke, 8 kırmızı.
Sonuç: 17B(8R(5B,15B), 25R(18B, 40B(-,80R))). Her yolda 3 siyah (null dahil).

Soru 12zor

Keys 5, 4, 3, 2, 1 are inserted into an ordinary BST (no balancing), giving a left chain. Then key 1 is accessed in a splay tree (bottom-up splaying). Give the level-order traversal of the tree after the splay.

Cevabı göster

1 4 2 5 3

Başlangıç: 5 → 4 → 3 → 2 → 1, hepsi sol çocuk. 1'in ebeveyni 2, dedesi 3, aynı yönde: zig-zig. Önce 2 (ebeveyn) dedenin üstüne, sonra 1 ebeveynin üstüne çıkar: 1(-, 2(-, 3)).
1'in yeni ebeveyni 4, dedesi 5, yine sol-sol: zig-zig. Sonuç 1(-, 4(2(-,3), 5)).
Seviye sırası 1 4 2 5 3. Zincir boyu 4'ten 3'e indi: splay, erişilen yolu yaklaşık yarıya katlar.

Doğrulama: Bütün red-black ekleme izleri (renkler, rotasyon ve yeniden boyama adımları, black-height kontrolü), 2-3 ve B-ağacı (m=5) bölünme izleri ve splay sonuçları Java ile üretildi (verify/SEN2212/W06.java, java W06.java).

Deftere not kartı

RED-BLACK: kök siyah, null siyah, kırmızının çocuğu kırmızı olamaz, her yolda aynı sayıda siyah (black-height). height <= 2 log2(n+1) Ekleme: yeni düğüm KIRMIZI. Ebeveyn siyahsa bitti. amca KIRMIZI → ebeveyn+amca siyah, dede kırmızı, dededen devam amca SİYAH, zig-zag (LR/RL) → ebeveynde rotasyon, düz hale getir amca SİYAH, düz (LL/RR) → dedede rotasyon, ebeveyn siyah, dede kırmızı en sonda kök siyah 2-3: düğüm 1 ya da 2 anahtar; 3 olunca ortanca YUKARI çıkar ağaç yukarı doğru büyür, bütün yapraklar aynı derinlikte 2-3-4 = red-black (4-düğüm = siyah + iki kırmızı çocuk) B-ağacı order m: en fazla m-1 anahtar, kök dışı en az ceil(m/2)-1 disk için: yükseklik log_m n, her seviye bir disk okuması Splay: erişilen düğüm köke; zig, zig-zig (önce ebeveyn), zig-zag tek işlem O(n) olabilir, m işlem toplam O(m log n) (amortized) Java TreeMap / TreeSet = red-black ağaç