Dengeli Arama Ağaçları

OYUNLARDA YAPAY ZEKÂ · ARAMA AĞAÇLARI

2-3 ağaçları, kırmızı-siyah ağaçlar, B-ağaçları — en kötü durumda bile lg N

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

Neden denge? — BST’nin kâbusu: sıralı anahtarlar
2-3 ağaçları — bir düğüme iki anahtar sığarsa…
Kırmızı-siyah BST — 2-3 ağacını sıradan BST ile taklit et
Döndürme & renk çevirme — ağacı onaran iki küçük hamle
Ekleme — üç satırlık sihir
Analiz — yükseklik ≤ 2 lg N garantisi
Oyunda & kütüphanelerde — SortedDictionary, ağ enterpolasyonu
B-ağaçları — veritabanları ve dosya sistemleri

🎮 Bu dersin sonunda…

…C#’ın SortedDictionary’sinin içinde ne olduğunu, bir oyunun kayıt veritabanının milyonlarca kayıtta neden 3–4 adımda aradığını ve “ortalama hızlı” ile “her zaman hızlı” arasındaki farkı bileceksiniz.

🤔 ISINMA: TEKRAR (REPLAY) SİSTEMİ

Oyununuz her olayı zaman damgasıyla kaydediyor: 0.016 → zıpla, 0.033 → ateş, 0.050 → hasar…

Olayları bir BST’ye koyarsak: anahtarlar (zaman) hep artarak geliyor. Ağaç neye benzer?

Hep sağa giden bir çizgi → bağlı liste! 10 dakikalık maçta ~36.000 olay → bir arama 36.000 adım. 😱

Artan ID’ler, zaman damgaları, sıralı dosyadan okunan seviyeler… Gerçek hayatta veri sık sık sıralı gelir. Rastgele girdiye güvenemeyiz.

Mini sözlük

balanced tree	dengeli ağaç	Yüksekliği her zaman ~lg N kalan ağaç
2-node · 3-node	2-düğüm · 3-düğüm	1 anahtar & 2 çocuk · 2 anahtar & 3 çocuk
perfect balance	mükemmel denge	Kökten her null bağlantıya aynı uzaklık
red-black BST	kırmızı-siyah BST	2-3 ağacını ikili ağaçla taklit eden yapı
left-leaning (LLRB)	sola yatık	Kırmızı bağlantılar hep sola eğik
rotation	döndürme	Sırayı bozmadan bir bağlantının yönünü değiştirmek
color flip	renk çevirme	Geçici 4-düğümü bölmek
B-tree · page	B-ağacı · sayfa	Düğüm başına yüzlerce anahtar · diskten bir okumada gelen blok

LEVEL 0

Neden denge?

BST ortalamada iyi, en kötü durumda felaket

neden denge?
2-3 ağaçları
kırmızı-siyah BST
döndürme & renk çevirme
ekleme
analiz
oyunda & kütüphanelerde
B-ağaçları

Hatırlatma: BST’ye sıralı ekleme

Hedef: garantili lg N

yapı	arama (en kötü)	ekleme (en kötü)	arama (ortalama)	sıralı işlemler?
sıralı arama (bağlı liste)	N	N	N/2	hayır
ikili arama (sıralı dizi)	lg N	N	lg N	evet
BST	N	N	1,39 lg N	evet
bu dersin hedefi	~lg N	~lg N	~lg N	evet

🎮 Oyunda neden “en kötü durum” önemli?60 FPS’te bir karenin bütçesi 16,6 ms. Ortalama 1 ms süren işlem bir karede 40 ms sürerse oyuncu takılma stutter / hitch görür. Oyuncular ortalamayı değil, takılmayı hatırlar!

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

📊 İkili arama ağacı ve AVL

VisuAlgo (NUS)

Ekleme, silme ve döndürmeleri adım adım gösterir; AVL kipinde ağacın kendini nasıl dengelediğini izleyin.

🔗 Data Structure Visualizations

David Galles (USF)

Neredeyse her veri yapısı için bir oyun alanı: ekle, sil, ara düğmeleriyle yapının nasıl değiştiğini izleyin.

🔗 cp-algorithms

cp-algorithms.com

Algoritmaların matematiksel ve kod düzeyinde ayrıntılı anlatımı (geometri, graf, veri yapıları).

Quiz 1 · neden denge?

Boş bir BST’ye 1, 2, 3, …, 1000 anahtarları bu sırayla eklenirse ağacın yüksekliği ne olur?

Her yeni anahtar öncekilerin hepsinden büyük → hep en sağa eklenir. Ağaç 1000 düğümlük bir çizgi olur: yükseklik 999. Dengeli bir ağaçta ise lg 1000 ≈ 10 civarında olurdu.

LEVEL 1

2-3 ağaçları

bir düğüme iki anahtar sığarsa ağaç hep mükemmel dengede kalır

neden denge?
2-3 ağaçları
kırmızı-siyah BST
döndürme & renk çevirme
ekleme
analiz
oyunda & kütüphanelerde
B-ağaçları

2-3 ağacı 2-3 tree

2-düğüm: 1 anahtar, 2 çocuk (sıradan BST düğümü) K
3-düğüm: 2 anahtar, 3 çocuk IM
- sol: I’dan küçükler
- orta: I ile M arasındakiler
- sağ: M’den büyükler
Simetrik sıra: soldan sağa okuyunca anahtarlar sıralı
Mükemmel denge: kökten her null bağlantıya yol aynı uzunlukta!

Gri zeminli kutular 3-düğüm.

2-3 ağacında arama: K var mı?

Kök P: K < P → sol
I M: I < K < M → orta
K: bulundu! ✔
Ağaçta olmayan C için: P → sol, I M → sol, A E → A ile E arası → null → yok.

BST ile aynı fikirTek fark: 3-düğümde iki karşılaştırma yapıp üç yoldan birini seçeriz.

Ekleme 1: yaprak bir 2-düğümse

Aşağı inip anahtarın gideceği yaprağı bul. Yaprak 2-düğümse: anahtarı içine koy, 3-düğüm olsun. Bitti!

K + L → KL

Ağacın şekli değişmedi → yükseklik aynı, denge bozulmadı.

⚙️ BST ile kritik farkBST yeni anahtarı yeni bir yaprak olarak aşağıya asar → ağaç aşağı doğru uzar, bir dal diğerlerinden derin olabilir.

2-3 ağacı ise önce var olan düğüme sığdırmaya çalışır. Ağaç aşağıya doğru asla uzamaz!

Ekleme 2: yaprak bir 3-düğümse

Anahtarı yine içine koy → geçici bir 4-düğüm (3 anahtar, 4 çocuk): ACE
Böl split: ortadaki anahtar (C) ebeveyne çıkar, kalanlar iki 2-düğüm olur: A E
Ebeveyn 2-düğümse → 3-düğüm olur, bitti ✔
Ebeveyn de 3-düğümse → o da geçici 4-düğüm olur → onu da böl, ortadakini bir üste çıkar… Gerekirse köke kadar.
Kök 4-düğüm olursa → böl: ortadaki anahtar yeni kök olur. Yükseklik ancak böyle 1 artar — ve bütün yapraklar aynı anda 1 aşağı iner. Denge korunur!

🌳 Ters büyüyen ağaçBST aşağı doğru (yapraklardan) büyür. 2-3 ağacı yukarı doğru (kökten) büyür. Mükemmel dengenin sırrı bu.

2-3 ağacı — oyun alanı

Renkler: sarı = aşağı inerken bakılan düğüm · kırmızı = geçici 4-düğüm · mor = bölünen parçalar · yeşil = yeni / değişen. Önce “S U P E R M A R I O K A R T”, sonra “Sıralı” deneyin: yapraklar hep aynı seviyede mi?

Neden işe yarıyor? Yerel dönüşümler

Bir 4-düğümü bölmek yerel local bir işlem: sadece o düğüm ve ebeveyni değişir. Ağacın geri kalanına dokunulmaz.
Bölme işlemi sırayı korur (A < C < E hâlâ doğru yerde).
Bölme işlemi dengeyi korur: hiçbir yaprağın derinliği değişmez (kök bölünmesi hariç; o da herkesi birden 1 indirir).

ÖnermeN anahtarlı bir 2-3 ağacında arama ve ekleme en fazla lg N düğüm ziyaret eder.

Kanıt fikriMükemmel denge var. En kötü: hepsi 2-düğüm → yükseklik lg N. En iyi: hepsi 3-düğüm → log₃ N ≈ 0,63 lg N.

Sayılarla 2-3 ağacı

N	yükseklik en az (log₃ N)	yükseklik en çok (lg N)	sıradan BST en kötü
1.000	6	10	999
1 milyon	12	20	999.999
1 milyar	19	30	~1 milyar

1 milyar kayıtta bile en fazla 30 düğüm. Ve bu bir garanti — “şanslıysak” değil.

Quiz 2 · 2-3 ağaçları

Bir 2-3 ağacında eklemeden sonra ağacın yüksekliği hangi durumda artar?

Bölmeler ortadaki anahtarı yukarı iter; ağacın şekli ancak kök bölündüğünde değişir: yeni bir kök oluşur ve bütün yapraklar birlikte 1 seviye aşağı iner. Bu yüzden denge hiç bozulmaz.

Peki neden 2-3 ağacını doğrudan kodlamıyoruz?

İki farklı düğüm türü (2-düğüm, 3-düğüm) + geçici 4-düğüm
Düğüm türünü sürekli kontrol eden if’ler, bir türden ötekine kopyalama…
Bölmenin bir sürü özel durumu (sol/orta/sağ çocuk, kök…)

⚠️ Sorun“Bunu kodlamak mümkün ama kod karmaşık ve bakımı zor; ek yükü de onu sıradan BST’den yavaş yapabilir.”

Çözüm: 2-3 ağacını sıradan bir BST ile temsil et. Sadece bağlantılara bir renk ekle! →

LEVEL 2

Kırmızı-siyah BST

left-leaning red-black BST — 2-3 ağacının ikili ağaç kılığı

neden denge?
2-3 ağaçları
kırmızı-siyah BST
döndürme & renk çevirme
ekleme
analiz
oyunda & kütüphanelerde
B-ağaçları

Fikir: 3-düğümü iki düğüme böl, araya kırmızı bağlantı koy

EJ ⇄

Kırmızı bağlantı: “bu iki düğüm aslında tek bir 3-düğüm”
Siyah bağlantı: 2-3 ağacının gerçek bağlantıları
Kırmızı bağlantı hep sola yatar: büyük anahtar (J) yukarıda, küçük (E) onun sol çocuğu
Kazanç: BST’nin get() kodu olduğu gibi çalışır — renklere bakmaz bile!

Birebir eşleme 1-1 correspondence

2-3 ağacı

Kırmızı-siyah BST

Kırmızı bağlantıları yatay çizin (düğümleri ebeveynlerinin seviyesine çekin) → 2-3 ağacının kendisi! ↓

Kırmızıları yatırınca…

A–E, I–M, T–U yan yana: 3-düğümler ✔
Bütün null bağlantılar aynı seviyede: mükemmel siyah denge ✔

Tanım: sola yatık kırmızı-siyah BST

Kırmızı ve siyah bağlantıları olan bir BST, şu üç kuralı sağlıyorsa:

Kırmızı bağlantılar sola yatar.
Hiçbir düğüme iki kırmızı bağlantı değmez (yoksa 4-düğüm olurdu).
Mükemmel siyah denge: kökten her null bağlantıya giden yolda siyah bağlantı sayısı aynı.

🎮 Benzetme: takım otobüsüKırmızı bağlantı = aynı koltukta oturan iki oyuncu (bir 3-düğüm). Siyah bağlantı = otobüsün katları. Kural 3: her oyuncu aynı sayıda kat aşağıda. Kural 2: bir koltuğa en fazla iki kişi!

🎒 Ön bilgi: düğüme renk alanı eklemek

Bağlantının rengini, bağlantının gösterdiği (alttaki) düğümde saklarız: red = True/False
Mantıksal tür boolean: sadece iki değer → 1 bit bilgi yeter
RED = True gibi sabitler constant kodu okunur yapar
is_red(None) → False: null bağlantılar siyah sayılır. Böylece her yerde “null mı?” diye kontrol etmeyiz

⚙️ Bellek notuGerçek kütüphaneler bu tek biti bazen işaretçinin (pointer) kullanılmayan en düşük bitine gizler (Linux çekirdeğinin rbtree’si böyle yapar).

Arama: BST ile birebir aynı kod

Renklere hiç bakılmıyor
Ama ağaç dengeli olduğu için en fazla ~2 lg N adım
Önceki sunumdaki tüm sıralı işlemler (min, max, floor, ceiling, rank, select, range) da aynen çalışır! 🎁

Dersİyi bir temsil seçmek = bedava kod. Zor işi sadece ekleme yapacak.

Kırmızı-siyah BST — oyun alanı

“2-3 görünümü” kutusunu işaretleyin: kırmızı bağlantılar yatay çizilir ve ağaç 2-3 ağacına dönüşür. Aynı diziyi önceki 2-3 oyun alanında oynatıp karşılaştırın!

LEVEL 3

Döndürme & renk çevirme

ağacı onaran iki küçük, yerel hamle

neden denge?
2-3 ağaçları
kırmızı-siyah BST
döndürme & renk çevirme
ekleme
analiz
oyunda & kütüphanelerde
B-ağaçları

Sola döndürme rotate left

önce: kırmızı bağlantı sağa yatık ❌

sonra: kırmızı bağlantı sola yatık ✔

S yukarı çıkar, E onun sol çocuğu olur. Ortadaki alt ağaç (E ile S arasındakiler) E’nin sağına geçer. Sıra korunur, sadece 3 bağlantı değişir → sabit zaman!

Döndürme — kendiniz deneyin

rotateLeft ardından rotateRight: ağaç eski hâline döner. İki döndürme birbirinin tersi.

rotateLeft — kod

x = h’nin sağ çocuğu (yukarı çıkacak)
x’in sol alt ağacı → h’nin sağına
h → x’in soluna
Renkler: x, h’nin eski rengini alır; h kırmızı olur (çünkü artık x ile h arasındaki bağlantı kırmızı)
Yeni alt ağaç kökü x’i döndür

⚠️ Sıra önemli!2. ve 3. adımın yeri değişirse x’in sol alt ağacı kaybolur (üzerine yazılır).

🎒 Ön bilgi: “yeni kökü döndür” kalıbı

Döndürmeden sonra alt ağacın kökü değişti. Ebeveyn hâlâ eski köke (h) bakıyor! Bu yüzden:


h = rotate_left(h)          # h artık yeni kökü gösterir
h.left = put(h.left, k, v)  # alt ağaç değişmiş olabilir: yeniden bağla

Fonksiyon yeni kökü geri döndürür, çağıran onu ilgili bağlantıya atar. BST sunumundaki put’ta da aynı kalıp vardı.

🎒 Referans hatırlatması

h bir düğümün kendisi değil, ona bakan bir ok. rotate_left(h) içindeki x.left = h düğümlerin oklarını değiştirir; ama dışarıdaki h değişkeni otomatik güncellenmez.

Atamayı unutursanız (sadece rotate_left(h) yazarsanız) ağacın bir parçası kaybolur — en sık yapılan hata!

Renk çevirme flip colors

önce: iki çocuk da kırmızı = geçici 4-düğüm AES

sonra: E yukarı “çıktı” (ebeveynine kırmızıyla bağlı)

2-3 ağacındaki 4-düğümü bölme işleminin aynısı: ortadaki anahtar ebeveynin parçası olur. Sadece 3 renk değişir, hiçbir bağlantı yer değiştirmez!

🎬 Ara: kırmızı-siyah ağaç, 4 dakikada

Red-black trees in 4 minutes — Intro
Michael Sambol · 3 dk 54 sn · YouTube’da aç

Kırmızı-siyah ağacın kuralları ve dengenin neden korunduğu, renkli ve kısa bir özet. Bizim sola yatık sürümümüzden biraz farklı (kitaplardaki genel sürüm); farkı bulmak iyi bir alıştırma.

🤔 İzlerkenVideodaki kurallardan hangisi bizim “kırmızı bağlantı hep sola yatar” kuralımızda yok? Kökten yaprağa her yolda aynı sayıda siyah düğüm olması 2-3 ağacındaki hangi özelliğe karşılık geliyor?

Quiz 3 · döndürme

Bir BST’de rotateLeft(h) uygulandıktan sonra hangisi her zaman doğrudur?

Döndürme sırayı korur — bu yüzden güvenle kullanabiliriz. Yükseklik bazen azalır, bazen artar, bazen aynı kalır; o yüzden C “her zaman” doğru değil. Döndürmenin amacı yükseklik değil, kırmızı bağlantının yönünü düzeltmek.

LEVEL 4

Ekleme

yeni düğüm hep kırmızı · sonra yukarı çıkarken onar

neden denge?
2-3 ağaçları
kırmızı-siyah BST
döndürme & renk çevirme
ekleme
analiz
oyunda & kütüphanelerde
B-ağaçları

Ekleme stratejisi

BST gibi aşağı in, yeni düğümü en alta ekle.
Yeni düğümü ebeveynine kırmızı bağlantıyla bağla. (2-3 dilinde: yaprağa bir anahtar daha sıkıştırmak.)
Özyinelemeden geri dönerken (yukarı çıkarken) her düğümde üç durumu kontrol et ve düzelt:

sağ çocuk kırmızı, sol değil	rotateLeft	sağa yatık kırmızı → sola yatır
sol ve solun solu kırmızı	rotateRight	art arda iki kırmızı → dengele (4-düğüm oluşur)
iki çocuk da kırmızı	flipColors	4-düğümü böl, ortadakini yukarı gönder

Bu üç kontrolün sırası önemli: biri ötekini tetikleyebilir (ör. rotateRight sonrası iki kırmızı çocuk → flip). Bir “kırmızı” yukarı itilir, üstte yine kontrol edilir… köke kadar.

Üç durum, tek resimde

1) sağa yatık → rotateLeft

⬇

2) iki kırmızı sol → rotateRight

⬇

3) iki kırmızı çocuk → flipColors

⬇

Boş ağaca A, C, B (ya da C, B, A) eklemek bu zinciri sırasıyla tetikler. Animasyonda adım adım izleyin →

Ekleme — kod put

🎒 put kodundaki yeni ifadeler

not is_red(…) · !IsRed(…)	değil not	Doğruyu yanlışa, yanlışı doğruya çevirir. `!` C#/JS yazımı
a and b · a && b	kısa devre short-circuit	`a` yanlışsa `b`’ye hiç bakılmaz. Bu yüzden `is_red(h.left) and is_red(h.left.left)` güvenli: h.left null ise ikinci kısım çalışmaz, null hatası olmaz!
h.left = put(h.left, …)	yeniden bağlama	Alt ağacın kökü döndürmeyle değişmiş olabilir → yeni kökü bağlantıya geri yaz
tree.root	ağaç nesnesi	Ağacın kökünü tutan küçük bir nesne. Kök de değişebildiği için `tree.root = put(…)`

Kısa devre olmadan aynı kontrol (geleneksel yazım):

Ekleme — adım adım

“S U P E R M A R I O K A R T” düğmesine basın ve ◀ Geri / İleri ▶ ile tek tek ilerleyin. Her notta hangi kuralın çalıştığı yazıyor. Kendi harflerinizi de ekleyebilirsiniz.

Sıralı ekleme: kâbus bitti mi?

Oyun alanında 📈 Sıralı A…O’ya basın. 15 harf, alfabetik sırayla.

Sıradan BST: yükseklik 14 (çizgi)
Kırmızı-siyah: yükseklik 3 — mükemmel dengeli ikili ağaç! 🎉
Sırayla gelen her anahtar sağa kırmızı eklenir → döndürme → renk çevirme → kırmızı yukarı tırmanır… Ağaç kendini sürekli toparlar.

🎮 Isınma sorusuna dönüşTekrar sistemindeki 36.000 olay artık bir çizgi değil: yükseklik en fazla 2 lg 36.000 ≈ 30, pratikte ~16. 2.250 kat daha hızlı arama.

Quiz 4 · ekleme

Boş bir kırmızı-siyah BST’ye sırayla A, B, C eklenince kök hangisi olur?

A kök. B sağa kırmızı eklenir → rotateLeft: B kök, A sol kırmızı. C, B’nin sağına kırmızı eklenir → iki çocuk kırmızı → flipColors: B kırmızı olur, ama kök her zaman siyah yapılır. Sonuç: B kök, A ve C siyah çocuklar. Kök hiçbir zaman kırmızı kalmaz.

🧪 Kod laboratuvarı: rotateLeft yaz

İpucu: Döndürme slaytındaki resme bakın: orta alt ağaç (x.left) h’ye geçer, h de x’in soluna iner. Renk: x, h’nin eski rengini alır; h kırmızı olur. Sonra 2. ve 3. adımın yerini değiştirip neler olduğuna bakın.

🐍 Kod laboratuvarı — Python

Bu kodda tek bir hata var: iki satırın sırası yanlış. Çalıştırın: hangi hatayı görüyorsunuz? (İpucu: x.left = h yapıldıktan sonra x.left neyi gösteriyor? h’nin sağı neye bağlanıyor?) Düzeltin.

LEVEL 5

Analiz

yükseklik ≤ 2 lg N — her girdi için

neden denge?
2-3 ağaçları
kırmızı-siyah BST
döndürme & renk çevirme
ekleme
analiz
oyunda & kütüphanelerde
B-ağaçları

Garanti: yükseklik ≤ 2 lg N

ÖnermeN düğümlü bir sola yatık kırmızı-siyah BST’nin yüksekliği en fazla 2 lg N’dir.

Kanıt (sezgisel)

Her kökten-null yolunda siyah bağlantı sayısı aynı = karşılık gelen 2-3 ağacının yüksekliği ≤ lg N.
İki kırmızı bağlantı art arda gelemez → bir yolda en fazla siyahlar kadar kırmızı olabilir.
Toplam ≤ lg N + lg N = 2 lg N. ∎

En kötü yol: sırayla siyah, kırmızı, siyah, kırmızı… (en soldaki yol). Pratikte ortalama yol ~1,0 lg N — neredeyse mükemmel!

Deney: yükseklik ölçümü

Sütunlar: sıradan BST (rastgele / sıralı ekleme) ve kırmızı-siyah BST (rastgele / sıralı). Sıralı eklemede sıradan BST’nin yüksekliği N − 1’dir (çizgi). Kırmızı-siyah ağaçtaki sayıların lg N’ye ne kadar yakın olduğuna dikkat!

Sembol tablosu karnesi

yapı	en kötü durum		ortalama durum		sıralı işlemler?
yapı	arama	ekleme	arama	ekleme	sıralı işlemler?
sıralı arama (bağlı liste)	N	N	N/2	N	hayır
ikili arama (sıralı dizi)	lg N	N	lg N	N/2	evet
BST	N	N	1,39 lg N	1,39 lg N	evet
2-3 ağacı	c lg N	c lg N	c lg N	c lg N	evet
kırmızı-siyah BST	2 lg N	2 lg N	1,0 lg N	1,0 lg N	evet

“c”: düğüm türü kontrolü yüzünden sabit çarpan büyük. Hash tabloları (Bölüm 13) ortalamada daha da hızlı, ama sıralı işlemleri desteklemez.

Quiz 5 · analiz

Kırmızı-siyah BST’nin yüksekliği neden 2 lg N’yi aşamaz?

Siyah yükseklik ≤ lg N (2-3 ağacının yüksekliği). Kırmızılar en fazla siyahlar kadar olabilir (araya hep bir siyah girer) → toplam ≤ 2 lg N. Karıştırma (A) quicksort’un ve rastgele BST’nin numarasıydı; burada girdi ne olursa olsun garanti var.

Tarihçe 📜

1962 · AVL ağacıİlk kendini dengeleyen BST: Sovyet bilim insanları Georgy Adelson-Velsky ve Evgenii Landis. 🎮 Adelson-Velsky, 1974’te ilk Dünya Bilgisayar Satranç Şampiyonası’nı kazanan Kaissa programının geliştiricilerinden biriydi!

1978 · Kırmızı-siyah ağaçLeo Guibas ve Robert Sedgewick. Neden kırmızı? Sedgewick’in anlattığına göre Xerox PARC’taki renkli lazer yazıcının en iyi bastığı renk kırmızıydı. 2008’de Sedgewick “sola yatık” sürümle kodu birkaç satıra indirdi.

⚙️ AVL mi, kırmızı-siyah mı?AVL daha sıkı dengelidir (yükseklik ≤ 1,44 lg N) → arama biraz daha hızlı, ama ekleme/silmede daha çok döndürme yapar. Kırmızı-siyah ekleme-silmenin bol olduğu yerlerde (çekirdek, kütüphaneler) tercih edilir.

⚠️ SİLME?

Önceki sunumdaki Hibbard silmesi dengeyi bozar (ağaç zamanla √N yüksekliğe kayar).

Kırmızı-siyah ağaçta silme de lg N’de yapılabilir: aşağı inerken “borç alarak” her adımda geçici 3- ya da 4-düğümler oluşturulur, en altta silinir, yukarı çıkarken yine aynı üç kuralla onarılır.

Kodu ekleme kodundan daha uzun ve inceliklidir; bu derste ayrıntısına girmiyoruz. Merak edenler: açık kaynak RedBlackBST.java (deleteMin, delete).

LEVEL 6

Oyunda & kütüphanelerde

kırmızı-siyah ağaçlar her yerde — siz fark etmeden

neden denge?
2-3 ağaçları
kırmızı-siyah BST
döndürme & renk çevirme
ekleme
analiz
oyunda & kütüphanelerde
B-ağaçları

Kırmızı-siyah ağaçlar nerede?

C#: SortedDictionary<K,V>, SortedSet<T> 🎮 Unity’de kullanabilirsiniz
Java: TreeMap, TreeSet
C++: std::map, std::set (yaygın derleyicilerde) — Unreal’ın TSortedMap’i ise sıralı dizi kullanır
Python / JavaScript: dilde hazır dengeli ağaç yok! (bisect modülü, sortedcontainers kütüphanesi)

Linux çekirdeği: işlem zamanlayıcısı (CFS, 2007–2023; yerine gelen EEVDF de) çalışmaya hazır işlemleri kırmızı-siyah ağaçta tutar. Sıradaki işlem = en soldaki düğüm (min)!
Oyun motorları: zamanlayıcılar, olay kuyrukları, tekrar (replay) zaman çizelgeleri, sıralı skor tabloları…

🎒 Sıralı sözlük ≠ sözlükC#’ta Dictionary (hash tablosu, Bölüm 13) daha hızlıdır ama anahtarları sırasız tutar. “En küçük”, “şundan hemen önceki”, “şu aralıktakiler” sorularını SortedDictionary hızlı yanıtlar.

🎮 Ağ oyunu: anlık görüntü enterpolasyonu

Sunucu saniyede ~20 kez dünya durumunun anlık görüntüsünü snapshot yollar. İstemci akıcı görüntü için 100 ms geriden çizer:

Çizilecek an: t = şimdi − 0,1
floor(t): t’den önceki son görüntü
ceiling(t): t’den sonraki ilk görüntü
İkisinin arasında oyuncu konumlarını enterpole et (ara değer bul)
Eski görüntüleri sil: deleteMin

Gerçek dünyaValve’ın Source motoru (Counter-Strike, Team Fortress 2) bu tekniği kullanır: varsayılan enterpolasyon gecikmesi 100 ms. Zaman damgaları sıralı geldiği için sıradan BST burada en kötü durumuna düşerdi!

🔗 Ayrıntısı: G7 · Ağ Senkronizasyonu (ara değerleme, tahmin ve geri sarma demolarıyla) sunumunda.

floor(t): kütüphaneyle ve elle

🎒 var (C#): türü derleyici çıkarır — SortedSet<double> times = new SortedSet<double>(); ile aynı. bisect_right: ikili arama (Arama Algoritmaları sunumu) ile “t’den büyük ilk eleman”ın indeksini bulur.

🤔 TARTIŞMA

Python’da bisect.insort ekleme başına O(N) ama yine de çoğu zaman hızlı çalışır. Neden? (İpucu: bağlı listeler sunumundaki önbellek ve memmove)
Skor tablosunda “oyuncu kaçıncı sırada?” (rank) sorusunu Dictionary ile nasıl yanıtlarsınız? SortedDictionary ile?
Bir RTS’de 10.000 zamanlanmış olay var (“12,5 sn’de birim üret”). Her karede “zamanı gelenleri” çalıştırmak için hangi işlemler gerekiyor?

LEVEL 7

B-ağaçları

düğüm başına yüzlerce anahtar: veritabanları ve dosya sistemleri

neden denge?
2-3 ağaçları
kırmızı-siyah BST
döndürme & renk çevirme
ekleme
analiz
oyunda & kütüphanelerde
B-ağaçları

Disk yavaş, sayfa büyük

Diskten (ya da SSD’den) okuma sayfa sayfa page olur: tek bayt isteseniz de 4–16 KB gelir.
Okuma, bellekteki bir karşılaştırmadan binlerce–milyonlarca kat yavaş.
O hâlde ölçü: kaç sayfa okuduk? (karşılaştırma sayısı değil)
Fikir: 2-3 ağacını genelleştir → düğüm başına M − 1’e kadar anahtar. Bir düğüm = bir sayfa.

⚙️ Yaklaşık erişim süreleri

L1 önbellek	~1 ns
RAM	~100 ns
NVMe SSD	~20–100 µs
mekanik disk (HDD)	~5–10 ms

HDD’den bir okuma ≈ RAM’den 100.000 okuma!

B-ağacı B-tree

Her düğümde M/2 ile M − 1 arası anahtar (kök hariç). M tipik olarak yüzler–binler.
Ekleme 2-3 ağacındaki gibi: yaprağa koy, M anahtara ulaşan düğümü ikiye böl, ortadakini yukarı gönder.
Mükemmel denge: yükseklik ~log_M/2 N
2-3 ağacı = M = 3 olan B-ağacı. 2-3-4 ağacı = M = 4.

📜 1970 · BoeingRudolf Bayer ve Edward McCreight, Boeing araştırma laboratuvarında icat etti. “B” neyin kısaltması? Boeing? Balanced? Bayer? Yazarlar hiçbir zaman açıklamadı. 😄

M = 4 olan küçük bir B-ağacı (düğüm başına 1–3 anahtar). Gerçek sistemlerde bir düğüme yüzlerce anahtar sığar.

B-ağacı hesaplayıcı

M = 1000 ile 1 milyar kayıtta 3–4 seviye. Kök ve ikinci seviye zaten RAM’de durur → bir aramada 1–2 disk okuması.

B-ağaçları nerede?

Veritabanları: SQLite, MySQL (InnoDB), PostgreSQL, SQL Server indeksleri — B-ağacı ya da B+ ağacı (veriler sadece yapraklarda)
Dosya sistemleri: NTFS, APFS, Btrfs (“B-tree file system”), ext4 dizinleri (HTree)
Rust dilinin standart sıralı sözlüğü BTreeMap: bellekte bile B-ağacı!

🎮 OyunlardaBirçok mobil oyun ve araç kayıtları, envanterleri, başarımları SQLite veritabanında tutar. SELECT * FROM items WHERE id = 42 dediğinizde arka planda bir B-ağacında 3–4 düğüm geziliyor.

⚙️ RAM’de bile B-ağacı?Rust neden kırmızı-siyah değil de B-ağacı seçti? Önbellek! Bir düğümdeki anahtarlar yan yana → tek önbellek satırı yüklemesiyle birçok karşılaştırma. Kırmızı-siyah ağaçta her adım başka bir yere atlayan bir işaretçi (önbellek ıskası).

Quiz 6 · B-ağaçları

Her düğümün yaklaşık 500–1000 bağlantısı olan bir B-ağacında 1 milyar kayıt var. Bir arama yaklaşık kaç düğüm ziyaret eder?

log₁₀₀₀ 10⁹ = 3 ve log₅₀₀ 10⁹ ≈ 3,3 → 3–4 seviye. Dengeli ikili ağaçta bu sayı ~30 olurdu; diskte her seviye bir okuma demek. Fark: 30 × 10 ms = 0,3 sn yerine 30–40 ms (ve kök RAM’deyse daha da az).

Derin hikâye: Java 8 HashMap’i neden kırmızı-siyah ağaca döner?

2011’in sonunda (28C3 konferansı) araştırmacılar, birçok web platformunun hash tablolarına kasıtlı çakışan anahtarlar göndererek sunucuları kilitleyebildiklerini gösterdi: bütün anahtarlar aynı kovaya düşünce arama O(1)’den O(n)’e, toplam iş O(n²)’ye çıkıyordu (Hash Tabloları sunumu).
Java 8 (2014) buna veri yapısıyla cevap verdi (JEP 180): bir kovadaki eleman sayısı 8’i geçerse (ve tablo yeterince büyükse, en az 64 kova) o kovanın bağlı listesi bir kırmızı-siyah ağaca dönüştürülür. En kötü durum O(n)’den O(log n)’e iner.
Sayı tekrar 6’nın altına düşerse kova yeniden listeye çevrilir: küçük kovalarda liste daha hızlı ve daha az bellek kullanır.

DersDengeli ağaçlar sadece “sıralı sözlük” değildir: en kötü durumu garanti altına alan bir güvenlik aracıdır. İki veri yapısını birleştirmek (ortalama durum için hash, en kötü durum için ağaç) gerçek sistemlerde sık görülen bir tasarım.

Kaynak: JEP 180: Handle Frequent HashMap Collisions with Balanced Trees

🧰 Kütüphaneler ve araçlar

ad	platform	ne yapar / sınırları	nasıl eklenir
SortedSet · SortedDictionary	C# / Unity	Kırmızı-siyah ağaç; aralık görünümü `GetViewBetween`, `Min`, `Max`.	yerleşik
ImmutableSortedSet	C#	Değişmez (immutable) sıralı küme; AVL ağacı tabanlı. Geri alma/anlık görüntü için.	yerleşik (System.Collections.Immutable)
SQLite	her platform (Unity eklentileriyle)	Tablolar ve indeksler B-ağacıdır; kayıt dosyaları ve büyük veri için.	Unity: sqlite-net vb. paketler
std::map · std::set	C++	Kırmızı-siyah ağaç.	`#include <map>`
sortedcontainers	Python	Ağaç değil, “listelerin listesi” ama sıralı işlemler için pratikte çok hızlı.	`pip install sortedcontainers`

🧩 Oyunlarda dengeli ağaçlar

Kayıt ve veritabanı: SQLite ile oyuncu verisi, envanter, ilerleme; sorguları indeksli sütunlara göre yazın (B-ağacı).
Sıralı yapı + sık değişim: canlı liderlik tablosu, öncelikli görevler, zaman çizelgesi.
Değişmez sürümler: geri alma, tekrar oynatma, ağ için anlık görüntü (ImmutableSortedSet paylaşımlı yapı kullanır).
Kendi kırmızı-siyah ağacınızı üretimde yazmayın; öğrenmek için LLRB yazıp değişmez denetleyicisiyle test edin.

Değişmezleri test edinHer işlemden sonra: kök siyah mı? Kırmızı düğümün kırmızı çocuğu var mı? Her yoldaki siyah sayısı eşit mi? Anahtarlar sıralı mı? Bu dört kontrolü yapan bir fonksiyon, rotasyon hatalarını anında yakalar.

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

Rotasyonda ebeveyn/kök bağlantısını güncellememek
Renk kurallarını sadece eklemede düşünüp silmeyi unutmak
Üretimde kendi kırmızı-siyah ağacını yazmak
Küçük bellek içi veri için B-ağacı seçmek

İyi bir istek (prompt) örneği

“C# (.NET 8). Sola yatık kırmızı-siyah ağacı (LLRB) yaz: Put, Get, Contains, Min, Max, Floor, Ceiling, Rank. Ayrıca IsBalanced, Is23, IsBST kontrol fonksiyonları. NUnit testleri: 100.000 sıralı ve 100.000 rastgele anahtar ekle, her 1.000 eklemede kontrolleri çalıştır, yüksekliğin 2·log₂N’yi geçmediğini doğrula.”

Değişmez denetleyicisi (invariant checker) isteyin
Rotasyonları adım adım açıklatın
Önce hazır yapıyı (SortedSet) sorun
Rastgele ve sıralı ekleme testleri isteyin

🚀 Proje ve araştırma önerileri

[kolay] LLRB + denetleyici — LLRB’yi yazıp değişmez denetleyicisiyle test edin.
[orta] SQLite kayıt sistemi — Unity’de SQLite ile envanter; indeksli ve indekssiz sorguları ölçün.
[orta] Zaman çizelgesi — Sıralı sözlükle “t anından sonraki ilk olay” sorgusu yapan bir olay sistemi.
[araştırma] AVL, kırmızı-siyah, B-ağacı — Üçünü (ya da hazır sürümlerini) ekleme/arama ağırlıklı iş yüklerinde karşılaştırın.

📄 Akademik okumalar ve kaynaklar

Adelson-Velsky & Landis 1962 · An Algorithm for the Organization of Information (Soviet Mathematics Doklady 3)
İlk dengeli ikili ağaç (AVL).

Bayer & McCreight 1972 · Organization and Maintenance of Large Ordered Indexes (Acta Informatica 1)
B-ağaçları.

Guibas & Sedgewick 1978 · A Dichromatic Framework for Balanced Trees (FOCS 1978)
Kırmızı-siyah ağaçlar.

Sedgewick 2008 · Left-leaning Red-Black Trees (makale taslağı)
Bu sunumdaki LLRB.

Neler öğrendik? 🎒

Sorun: BST sıralı girdide çizgiye döner.
2-3 ağacı: 3-düğümler + bölme; ağaç yukarı büyür → mükemmel denge.
Kırmızı-siyah BST: 3-düğüm = kırmızı bağlantıyla bağlı iki düğüm. Arama kodu BST ile aynı.
Üç hamle: rotateLeft, rotateRight, flipColors.

Ekleme: kırmızı ekle, yukarı çıkarken 3 kuralla onar; kök siyah.
Garanti: yükseklik ≤ 2 lg N (pratikte ~lg N).
🎮 SortedDictionary / SortedSet, Linux zamanlayıcısı, ağ enterpolasyonu.
💾 B-ağaçları: düğüm = disk sayfası; veritabanları, dosya sistemleri.

Alıştırmalar 🏋️

Kâğıt-kalem: E A S Y Q U T I O N anahtarlarını boş bir 2-3 ağacına sırayla ekleyin. Sonra aynısını kırmızı-siyah BST’ye ekleyip “2-3 görünümü” ile karşılaştırın.
1’den 7’ye sırayla eklenen anahtarların kırmızı-siyah ağacını çizin. Sonuç neden mükemmel dengeli bir ikili ağaç?
Bir kırmızı-siyah ağacın kurallara uyduğunu kontrol eden bir fonksiyon yazın: (a) kırmızılar sola yatık mı, (b) art arda iki kırmızı var mı, (c) siyah denge tutuyor mu?
Unity’de SortedDictionary<float, string> ile bir “zamanlanmış olaylar” sistemi yapın: her karede zamanı gelen olayları çalıştırıp silin.
B-ağacı hesaplayıcıda M = 4’ü seçin: 2-3-4 ağacının yüksekliği kırmızı-siyah ağaçla nasıl karşılaştırılır?
🤖 Bir YZ asistanından kırmızı-siyah ağaç kodu isteyin. Sola yatık (LLRB) mı yoksa klasik sürüm mü verdi? Kaç satır? Sıralı 1…1000 ekleyip yüksekliği ölçün.

🎮 Bu sunumdaki oyunlar

Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.

Counter-Strike 1999– · takım nişancısı

Teröristler ve antiterör timi; isabet ve gecikme telafisi çok tartışılan rekabetçi nişancı.

📖 Fandom wikisi · ▶ video 1:49

Kaynaklar: videolar 🎬

Red-black trees in 3 minutes — Intro
Michael Sambol

Red-black trees in 5 minutes — Insertions
Michael Sambol

Red-Black Trees — rules
Rob Edwards

2-3 Tree Insertion
distanceedjohn

Understanding B-Trees
Spanning Tree

Kaynaklar: okuma ve görselleştirme 📚

NEXT LEVEL ▶

BST’nin Geometrik Uygulamaları

Aralık arama, kd-ağaçları, çarpışma adayları: oyun dünyasında “yakınımda ne var?”

SONRAKİ SUNUM ▶