Ağaçlar ve BST

OYUNLARDA YAPAY ZEKÂ · VERİ YAPILARI

Ağaçlar ve
İkili Arama Ağaçları

Trees & Binary Search Trees — hiyerarşi · gezinme · davranış ağaçları · ikili arama · BST

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

Ağaç nedir? — kök, yaprak, derinlik… tree
Gezinme ve oyun YZ’sinin yıldızı: davranış ağaçları traversal · behavior tree
Arama: sıralı arama ve ikili arama binary search
İkili arama ağacı binary search tree, BST
Şekil ve performans — neden bazen çok hızlı, bazen çok yavaş?
Sıralı işlemler — eşleştirme, skor tablosu ordered operations
Silme deletion
⚙️ Perde arkası: özyineleme, yığın taşması, bellek · 🌳 quadtree, BSP

🎮 Bu dersin sonunda…

…bir NPC’nin “beynini” ağaç olarak çizebilecek, 1 milyon oyuncu arasından birini 20 adımda bulmanın nasıl mümkün olduğunu açıklayabileceksiniz.

🤔 ISINMA SORUSU

Unity’de bir tankı döndürdünüz.
Taret ve namlu da onunla birlikte döndü. Neden?

Siz sadece gövdeyi döndürdünüz. Taretin dönmesi gerektiğini Unity nereden biliyor?

Çünkü Hierarchy penceresinde taret, gövdenin çocuğu; namlu da taretin çocuğu.

Bu ebeveyn–çocuk yapısının adı: AĞAÇ 🌳 tree

Oyunlarda ağaçlar her yerde

🎬

Sahne grafiği scene graph
Unity Hierarchy, Godot sahne ağacı

🧠

Davranış ağacı behavior tree
Halo, Unreal, Unity’deki NPC beyinleri

🌲

Karar ağacı decision tree
“Can az mı? → kaç, değilse → saldır”

♟️

Oyun ağacı game tree
Satranç/XOX yapay zekâsı: minimax

🗺️

Uzaysal ağaçlar quadtree · BSP
Çarpışma, görünürlük, Doom!

🔍

Arama ağaçları BST
Skor tablosu, eşleştirme, sözlükler

Bugün hepsinin ortak temelini kuracağız. Oyun YZ dersinin geri kalanında bu ağaçların çoğuyla tekrar karşılaşacağız. 💪

Mini sözlük (1/2)

tree	ağaç	Düğümlerin ebeveyn–çocuk bağlarıyla bağlandığı, döngüsüz yapı
node	düğüm	Ağaçtaki her bir eleman (bir oyun nesnesi, bir anahtar…)
edge / link	kenar / bağlantı	İki düğüm arasındaki ebeveyn–çocuk bağı
root	kök	En üstteki, ebeveyni olmayan düğüm
parent / child	ebeveyn / çocuk	Bir üstteki / bir alttaki düğüm
sibling	kardeş	Aynı ebeveynin çocukları
leaf	yaprak	Çocuğu olmayan düğüm
subtree	alt ağaç	Bir düğüm ve onun altındaki her şey

Mini sözlük (2/2)

depth / height	derinlik / yükseklik	Köke uzaklık / en uzak yaprağa uzaklık (kenar sayısı)
binary tree	ikili ağaç	Her düğümün en fazla 2 çocuğu (sol, sağ) var
traversal	gezinme / dolaşma	Tüm düğümleri belli bir sırayla ziyaret etmek
recursion	özyineleme	Bir fonksiyonun kendini (daha küçük bir parça için) çağırması
call stack	çağrı yığını	Bilgisayarın “hangi fonksiyondayım?” listesi
symbol table	sembol tablosu	Anahtar → değer saklayan yapı (sözlük, `Dictionary`)
binary search	ikili arama	Sıralı veride her adımda yarısını atarak arama
BST	ikili arama ağacı	Solu küçük, sağı büyük olan ikili ağaç

LEVEL 0

Ağaç Nedir?

tree — kök yukarıda, yapraklar aşağıda (evet, ters 🙃)

ağaç nedir?
gezinme & davranış ağaçları
arama & ikili arama
ikili arama ağacı (BST)
şekil ve performans
sıralı işlemler
silme
perde arkası & ötesi

Tanım: ağaç tree

Düğümlerden ve onları bağlayan kenarlardan oluşur.
Tek bir kök vardır; kökün ebeveyni yoktur.
Kök hariç her düğümün tam olarak bir ebeveyni vardır.
Bu yüzden döngü cycle yoktur: aşağı inerek başladığınız yere dönemezsiniz.

Bilgisayarcılar ağaçları hep ters çizer: kök en üstte, yapraklar en altta. 🙃 (Soy ağacı ve şirket şemaları gibi.)

Terimleri keşfet: bir sahne ağacı 🎬

Bir düğüme (soldaki Hierarchy listesinde ya da çizimde) tıklayın. Mavi çerçeve = ebeveyn, yeşil çerçeve = çocuklar, açık mavi zemin = alt ağaç.

🔗 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 · ağaç nedir?

Önceki slayttaki sahne ağacında Namlu’nun derinliği ve Oyuncu’nun yüksekliği kaçtır?

Namlu: Sahne → Oyuncu → Silah → Namlu = 3 kenar (kökün derinliği 0). Oyuncu’dan en uzak yaprak Namlu: Oyuncu → Silah → Namlu = 2 kenar. Derinlik köke doğru, yükseklik yapraklara doğru ölçülür.

🎮 Sahne grafiği: dönüşümler ağaçtan aşağı akar scene graph

🎒 Ön bilgi: sınıf ve nesne class & object

Sınıf class = kalıp: “Her oyun nesnesinin bir adı ve çocukları olur.”
Nesne object = kalıptan üretilen somut örnek: “Tank”, “Taret”…
Alan field = nesnenin bilgisi: name, children
Yapıcı constructor = nesne üretilirken çalışan fonksiyon
self (Python) / this (C#, JS) = “şu an üretilen / kullanılan nesne”
Nokta = “-nin”: tank.name → “tank’ın adı”

🎒 Ön bilgi: referans ve `null` reference · null

Bir değişken nesnenin kendisini değil, nerede durduğunu (adresini) tutar: bir ok gibi düşünün.

b = a yeni nesne üretmez: iki ok aynı nesneyi gösterir. b üzerinden yapılan değişiklik a’da da görünür!
None / null = ok hiçbir şeyi göstermiyor. Ağaçta “çocuk yok” demek.
null bir nesnenin alanına erişmeye çalışmak → hata (NullReferenceException — Unity’nin en meşhur hatası 😅)

Ağacı gezmenin doğal yolu: özyineleme recursion

🪆 MatruşkaHer bebeğin içinde daha küçük bir bebek var. Her alt ağaç da kendi başına bir ağaç!

Özyinelemenin iki kuralı

Temel durum base case: duracağın yer (çocuk yoksa döngü hiç dönmez).
Daha küçük problem: kendini bir alt ağaç için çağır.

⚙️ Özyineleme nasıl çalışır? Çağrı yığını call stack

Geçen dönem yığın stack veri yapısını gördük. Bilgisayar da her fonksiyon çağrısını bir yığına koyar:

Çağrı yapılınca → yığına push (yeni “kare” stack frame: parametreler, yerel değişkenler, dönüş adresi)
Fonksiyon bitince → yığından pop, kaldığı yere döner
Yığının derinliği = ağacın o anki derinliği

Çağrı yığını — “Namlu” yazılırken

print_tree(Namlu, 3)

print_tree(Silah, 2)

print_tree(Oyuncu, 1)

print_tree(Sahne, 0)

yığının tabanı

Yığın çok derinleşirse: stack overflow (yığın taşması). Birazdan BST’de göreceğiz!

Her hiyerarşi ağaç değildir 🤔

Strateji oyunlarındaki teknoloji ağaçları tech tree (Civilization, Age of Empires…) adına rağmen çoğu zaman ağaç değildir: bir teknolojinin iki ön koşulu (iki ebeveyni) olabilir.

Bu yapının adı yönlü döngüsüz graf directed acyclic graph, DAG. Graflar dersinde göreceğiz.

Ders: Bir şeye “ağaç” denmesi, onun matematiksel olarak ağaç olduğu anlamına gelmez. Tanımı kontrol edin: her düğümün tek ebeveyni var mı?

LEVEL 1

Gezinme & Davranış Ağaçları

traversal · behavior trees — ağacı hangi sırayla dolaşırız?

ağaç nedir?
gezinme & davranış ağaçları
arama & ikili arama
ikili arama ağacı (BST)
şekil ve performans
sıralı işlemler
silme
perde arkası & ötesi

İkili ağaç binary tree

Her düğümün en fazla iki çocuğu var: sol left ve sağ right.

Çocuk yoksa bağlantı null (Python’da None).

⚙️ Bellekteleft ve right aslında birer referans reference (adres, işaretçi). Düğümler bellekte yan yana durmaz; birbirini adresle “gösterir”.

🎒 Ön bilgi: fonksiyonu parametre olarak vermek callback

Gezinme fonksiyonu her düğümde ne yapılacağını bilmek zorunda değil. Bunu ona bir fonksiyon vererek söyleriz: ekrana yaz, listeye ekle, say…

Başka bir fonksiyona parametre olarak verilen fonksiyona geri çağırma callback denir.

Okuma kılavuzu Fonksiyonun adını parantezsiz verirsek fonksiyonun kendisini veririz: visit = print. Parantezle yazarsak (print()) onu hemen çalıştırmış oluruz.

lambda k: out.append(k) / k => out.push(k): “bir k al, onu listeye ekle” diyen isimsiz fonksiyon lambda · arrow function.

Dört gezinme sırası traversal orders

ad	sıra	akılda tutma	oyunda nerede?
preorder (önce-sıra)	kök → sol → sağ	“önce ben”	Hierarchy’yi yazdırmak, davranış ağacı tick’i
inorder (iç-sıra)	sol → kök → sağ	“ben ortada”	BST’de anahtarları sıralı listelemek
postorder (son-sıra)	sol → sağ → kök	“önce çocuklar”	Klasör boyutu, nesneleri yok etmek (`Destroy`)
level-order (seviye)	seviye seviye, soldan sağa	“kat kat”	En yakın çözüm (BFS), menülerde katman

Gezinme animasyonu — yığın ve kuyruk ile

Level-order: kuyruk ile gezinme queue · BFS

🎮 OyundaLevel-order = genişlik öncelikli arama breadth-first search, BFS. Izgarada yol bulmanın, “en az hamlede” çözümün temeli. Yol bulma dersinde döneceğiz!

⚙️ JS notuarray.shift() tüm elemanları bir sola kaydırır → O(N). Büyük kuyruklarda baş indeksi tutmak çok daha hızlı.

Quiz 2 · gezinme

Bir oyun klasörünün toplam boyutunu hesaplamak istiyoruz: her klasörün boyutu = kendi dosyaları + tüm alt klasörlerinin boyutu. Hangi gezinme?

Bir klasörün boyutunu bilmek için önce bütün çocuklarının boyutunu bilmek gerekir → çocuklar önce, kök en son: postorder. Aynı mantık: bir nesneyi yok etmeden (Destroy) önce çocuklarını yok etmek. Hierarchy’yi ekrana yazdırmak ise preorder’dır (önce ebeveyn).

🧠 Davranış ağacı behavior tree, BT

NPC’nin “beyni”: her karede (veya birkaç karede bir) kökten başlayarak gezilir (tick). Her düğüm başarılı success ya da başarısız failure döner.

düğüm	ne yapar?
? Seçici selector	Çocukları soldan sağa dener; biri başarılı olunca durur (“VEYA”)
→ Dizi sequence	Çocukları sırayla çalıştırır; biri başarısız olunca durur (“VE”)
◇ Koşul condition	Bir soru sorar: “Düşman görünüyor mu?”
▭ Eylem action	Bir şey yapar: ateş et, siper al, devriye gez

📜 Halo 2 (2004) Bungie’den Damian Isla, Halo 2’nin yapay zekâsını GDC 2005’te anlattı: düşmanların karmaşık davranışlarını düzenli tutmak için bir davranış ağacı kullanmışlardı. Bu konuşmadan sonra BT’ler sektörün standardı oldu; bugün Unreal Engine’in içinde hazır geliyor.

🎮 Canlı demo: bir nöbetçinin beyni

🔗 Ayrıntısı: Y3 · Davranış Ağaçları (senaryolarla, adım adım tick ve kendi motorunuzu yazarak) sunumunda.

Davranış ağacı kodu — sadece iki küçük sınıf

Gerçek BT’lerde üçüncü bir durum da vardır: çalışıyor running (ör. “yürüyor, henüz varmadı”). Unity’de hazır paketler, Unreal’da yerleşik editör var.

🎒 Davranış ağacı kodundaki yeni ifadeler

interface IBTNode	C# arayüz	“`Tick` metodu olan her şey.” `Selector`, `Sequence`, `Cond`, `Act` farklı sınıflar ama hepsi bu sözü verir → hepsi ağaçta düğüm olabilir
*kids · params · ...kids	değişken sayıda parametre	`Selector(a, b, c)` gibi istediğin kadar çocuk ver; fonksiyonun içinde hepsi bir liste/dizi olarak gelir
Cond(lambda n: n.hp > 30)	koşulu fonksiyonla vermek	“bir NPC al, canı 30’dan büyük mü söyle.” Koşul düğümü bu fonksiyonu her tick’te çağırır (callback)
Selector(Sequence(…), …)	iç içe nesne	Nesneleri iç içe üretmek = ağacı kurmak. Girintiler ağacın şeklini gösterir
any() · all()	Python (modern)	`any`: “en az biri True mu?”, ilk True’da durur · `all`: “hepsi True mu?”, ilk False’ta durur
some() · every()	JS (modern)	Dizinin `any` / `all` karşılıkları; içlerine bir ok fonksiyonu verilir

🤔 TARTIŞMA

Seçicinin çocuklarının sırası neden önemli? “Devriye gez”i en başa koysak ne olur?
“Düşman görünüyor?” koşulu iki kez kontrol ediliyor. Pahalı bir koşul (ör. görüş ışını, raycast) olsaydı ne yapardınız?
Bu ağacı if / else ile yazsaydık ne olurdu? 50 davranışlı bir boss için?

🎬 Ara: davranış ağaçları neden bu kadar yaygın?

Behaviour Trees: The Cornerstone of Modern Game AI
AI and Games (Tommy Thompson)

Oyun YZ’si üzerine en iyi kanallardan biri. Halo, Alien: Isolation gibi oyunlardan örneklerle BT’leri anlatıyor.

🤔 İzlerkenVideoda “selector” ve “sequence” düğümlerini bizim demodaki renklerle eşleştirin. Hangi oyunda BT’nin kaç seviye derin olduğu söyleniyor?

LEVEL 2

Arama

searching — 1 milyon kayıt içinde birini nasıl bulursun?

ağaç nedir?
gezinme & davranış ağaçları
arama & ikili arama
ikili arama ağacı (BST)
şekil ve performans
sıralı işlemler
silme
perde arkası & ötesi

🤔 ISINMA: 20 SORU

Aklınızdan dünyadaki herhangi bir insanı tutun.
Ben sadece evet/hayır soruları soracağım.

Kaç soruda bulabilirim? 100? 1000? 1 milyon?

Her soru adayları yarıya indirirse: 2³³ ≈ 8,6 milyar ≥ dünya nüfusu → 33 soru yeter!

“Akinator” adlı ünlü oyun, aklınızdaki karakteri genellikle 20 civarı soruda bulur. Bu dersin sihirli kelimesi: logaritma.

Sembol tablosu: anahtar → değer symbol table

İki temel işlem:

put(key, val) — ekle / güncelle
get(key) — anahtarın değerini getir

🎮 Oyunda eşya adı → adet · oyuncu ID → profil · kelime → çeviri · durum adı → animasyon · ızgara hücresi → içindeki birimler

🎒 dict · Dictionary<string, int> · Map: anahtar → değer çiftleri. C#’taki TryGetValue("kalkan", out int n): “varsa değerini n’ye yaz ve true döndür”.

Bu hazır yapılar nasıl bu kadar hızlı? Bugün bir yöntemi (ağaçlar), ileride diğerini (hash tabloları) göreceğiz.

İki basit yöntem

1) Sıralı arama sequential search Anahtarları sırasız bir listede tut. Ararken baştan sona tek tek bak.

Ekleme: sona ekle (hızlı) · Arama: en kötü N karşılaştırma

2) İkili arama binary search Anahtarları sıralı bir dizide tut. Ortadakine bak; aradığın küçükse sol yarıda, büyükse sağ yarıda ara.

Arama: en kötü ~lg N karşılaştırma · Ekleme: ???

İkili arama — kod

Python’da hazırı: bisect modülü. Değişmez invariant: “anahtar dizideyse, a[lo…hi] aralığındadır.”

📐 Logaritma: “kaç kez yarıya bölebilirim?” logarithm

Tanım (basitçe)\( \lg N = \log_2 N \) = N’i 1’e inene kadar kaç kez ikiye bölebilirsin. Ya da: 2’yi kaç kez çarparsan N olur? \( 2^{10} = 1024 \)

🧠 Akılda tutma hilesi\( 2^{10} \approx 1000 \) (bin) · \( 2^{20} \approx \) 1 milyon · \( 2^{30} \approx \) 1 milyar. Yani 1 milyar sıralı kayıtta ikili arama: ~30 adım.

🎮 Sayı tahmin oyunu

Bilgisayar modunda 1–100 arası bir sayı tutun ve dürüst cevap verin. Bilgisayar ikili arama yapıyor: en fazla 7 tahminde bulur, çünkü \( 2^7 = 128 \ge 100 \).

Quiz 3 · arama

1.000.000 elemanlı sıralı bir dizide ikili arama en kötü durumda yaklaşık kaç karşılaştırma yapar?

\( 2^{20} \approx 1.048.576 \) → 20 kez yarıya bölünce tek eleman kalır. Sıralı arama ise en kötü 1.000.000 karşılaştırma yapardı: 50.000 kat fark!

Quiz 4 · arama · kod

İkili arama kodunda while (lo <= hi) yerine while (lo < hi) yazarsak ne olur?

Aralık tek elemana indiğinde (lo == hi) döngü o elemana hiç bakmadan biter. Örn. [7] dizisinde 7’yi ararsak hemen −1 döner. Bu tür “bir eksik/bir fazla” hatalarına off-by-one hatası denir — ikili aramada çok yaygındır.

📜 Basit görünen, yazması zor bir algoritma

1946 → 1962Knuth’a göre ikili arama ilk kez 1946’da yayımlandı; ama her N için doğru çalışan ilk sürüm ancak 1962’de çıktı.

%90Jon Bentley, profesyonel programcılara ikili arama yazdırdığında çoğunun kodunda hata buldu (Programming Pearls).

2006Joshua Bloch: Java’nın kendi kütüphanesindeki ikili arama 9 yıl boyunca hatalıydı! Hata: mid = (lo + hi) / 2

⚙️ Tamsayı taşması integer overflowC#’ta int 32 bittir: en büyük değer 2.147.483.647. Bir fazlası en küçük negatif sayıya “sarar”. Oyunlarda da çok görülür (efsane: Civilization’daki “nükleer Gandhi”).

Peki ekleme? Sıralı dizinin bedeli

Sıralı diziye yeni bir anahtar eklemek için ondan büyük olanların hepsini bir sağa kaydırmak gerekir — insertion sort’un tek adımı gibi!

yapı	arama	ekleme
sırasız liste (sıralı arama)	N	1
sıralı dizi (ikili arama)	lg N	N
❓ ikisinin de iyi yanı	lg N	lg N

🎮 Neden önemli?1 milyon oyunculu bir skor tablosuna saniyede yüzlerce yeni skor geliyor. Her eklemede 500.000 elemanı kaydırmak = sunucu alarmı 🚨

Çözüm: ikili aramanın “ortadakine bak, sola/sağa git” fikrini bir ağaca dönüştürmek → BST!

LEVEL 3

İkili Arama Ağacı

binary search tree (BST) — solum küçük, sağım büyük

ağaç nedir?
gezinme & davranış ağaçları
arama & ikili arama
ikili arama ağacı (BST)
şekil ve performans
sıralı işlemler
silme
perde arkası & ötesi

Tanım: ikili arama ağacı BST

Her düğüm bir anahtar (ve değer) taşır ve şu kurala uyar:

Simetrik sıra symmetric order Her düğümün anahtarı, sol alt ağacındaki tüm anahtarlardan büyük, sağ alt ağacındaki tüm anahtarlardan küçüktür.

Kök = ikili aramadaki “ortadaki eleman”. Sol alt ağaç = sol yarı, sağ alt ağaç = sağ yarı. 💡

Dikkat: kural sadece çocuklar için değil, tüm alt ağaç için geçerli.

Arama search / get: ikili aramanın ağaç hali

Ağaç boşsa (null) → yok search miss
Anahtar köke eşitse → bulundu search hit
Küçükse → sol alt ağaçta ara
Büyükse → sağ alt ağaçta ara

Her adımda bir alt ağacı tamamen eleriz.

Arama animasyonu — çağrı yığını ile

Ekleme insert / put: ara, bulamadığın yere ekle

Önce ara.
Anahtar varsa → değerini güncelle.
null bir bağlantıya ulaştıysan → oraya yeni düğüm koy.

⚠️ En önemli satırx.left = put(x.left, …)
Özyineleme yeni (ya da aynı) alt ağacın kökünü döndürür; biz de bağlantıyı onunla yeniden kurarız. Böylece yeni düğüm ebeveynine bağlanmış olur.

Ekleme animasyonu: S U P E R M A R I O K A R T

🎬 Ara: BST’ye ekleme ve arama, tahtada

Data structures: Binary Search Tree
mycodeschool · 19 dk 27 sn · YouTube’da aç

Az önceki ekleme animasyonunun tahtada, kalemle anlatılan hâli: neden “küçükse sola, büyükse sağa”, arama ve ekleme neden ağacın yüksekliği kadar sürer. İlk 10 dakika bu bölüm için yeterli.

🤔 İzlerkenVideodaki ağaçta bir değeri aramak kaç karşılaştırma sürüyor; bu sayı neye bağlı? Değerler sıralı gelseydi ağaç neye dönüşürdü? (“Ekleme sırası ağacın şeklini belirler” demosunda deneyin.)

Quiz 5 · BST

S U P E R M A I O K T ağacına (önceki slaytlardaki ağaç) L eklenirse nereye gider?

L < S → sola (P) · L < P → sola (E) · L > E → sağa (M) · L < M → sola (I) · L > I → sağa (K) · L > K → sağa: null → L, K’nin sağ çocuğu olur. Ekleme hep bir null bağlantıya, yani yaprak olarak yapılır.

Quiz 6 · BST · kod

put fonksiyonunda x.left = put(x.left, key, val) yerine sadece put(x.left, key, val) yazarsak ne olur?

Yeni düğüm oluşturulur ama hiçbir ebeveyne bağlanmaz: döndürülen değer çöpe gider. Sonra çöp toplayıcı onu siler. Kod laboratuvarında deneyin: “ağaçta 3 düğüm var ama 10 anahtar eklendi” mesajını göreceksiniz.

🧪 Kod laboratuvarı: put

Tahmin et → değiştir → çalıştır (Ctrl+Enter):

5. satırda node.left = kısmını sil. Kaç düğüm kaldı?
< ile >’yi yer değiştir (4. ve 6. satır). Ağaç neye benzedi?
9. satırı (return node;) sil.
Anahtarlar: sıralı A…J seç. Ağacın şekli?

🐍 Aynı laboratuvar — Python (ve bir yığın taşması deneyi)

Python tarayıcıda çalışır (ilk açılışta internet gerekir).

Önce S U P E R M A R I O K A R T ile çalıştır.
Hazır listeden 1..1200 (çok derin!) seç. Hata mesajını oku: neden?
Fonksiyonu while döngüsüyle (özyinelemesiz) yeniden yaz ve 1..1200’ü tekrar dene.

Quiz 7 · BST

Bir BST’yi inorder (sol → kök → sağ) gezersek anahtarlar hangi sırayla çıkar?

Simetrik sıra kuralı yüzünden: önce soldaki (hepsi küçük) anahtarlar, sonra kök, sonra sağdakiler (hepsi büyük). Yani N anahtarı bir BST’ye ekleyip inorder gezmek bir sıralama algoritmasıdır (“tree sort”) — sıralama dersine selam! 👋

🧪 Kod laboratuvarı: inorder gezinme

Görevler:

Çalıştır: çıktı sıralı mı?
6. satırı 5. satırın üstüne taşı. Laboratuvar hangi gezinme olduğunu söylüyor?
Postorder yap. Sonra 4. satırı (temel durum) sil — ne oldu?
Büyükten küçüğe yazdırmak için ne değiştirmelisin?

LEVEL 4

Şekil ve Performans

Aynı anahtarlar, farklı sıra → bambaşka ağaçlar

ağaç nedir?
gezinme & davranış ağaçları
arama & ikili arama
ikili arama ağacı (BST)
şekil ve performans
sıralı işlemler
silme
perde arkası & ötesi

Ekleme sırası ağacın şeklini belirler

Ne kadar hızlı? 📐

Arama/ekleme maliyeti = kökten o düğüme yol uzunluğu (derinlik + 1).

En iyi (mükemmel dengeli): ~lg N
En kötü (sıralı ekleme): N
Ortalama (rastgele sırayla ekleme): ?

Önerme N farklı anahtar rastgele sırayla eklenirse, BST’de başarılı bir arama ortalama ~2 ln N ≈ 1,39 lg N karşılaştırma yapar.

Yani mükemmel dengeli ağaçtan sadece %39 daha kötü! (Kanıtı kitapta; quicksort’un analiziyle aynı matematik.)

Quiz 8 · performans

1’den 7’ye kadar anahtarları hangi sırayla eklersek mükemmel dengeli (yüksekliği 2 olan) bir BST elde ederiz?

Önce ortanca (4) kök olur, sonra her yarının ortancası (2 ve 6), sonra kalanlar. Bu “ortanca önce” sırası = ikili aramanın baktığı sıra! (D’de 1-2-3 zincir oluşturur.)

⚠️ Oyunlarda tehlike: veri çoğu zaman sıralı gelir

Oyuncu ID’leri: 1, 2, 3, 4… (veritabanı otomatik artırır)
Zaman damgaları timestamp: hep artar
Önceden sıralanmış dosyadan yüklenen seviye verisi

→ Düz bir BST bu verilerle bağlı listeye döner. Arama 1 milyon adım!

✅ Çözüm 1: dengeli ağaçlarKendini her eklemede yeniden düzenleyen ağaçlar: 2-3 ağacı, kırmızı-siyah ağaç red-black tree. En kötü durumda bile ~lg N. → Sonraki ders!

✅ Çözüm 2: karıştırHepsi baştan biliniyorsa önce Fisher–Yates ile karıştır, sonra ekle (sıralama dersindeki karıştırma!).

⚙️ Derin ağaç + özyineleme = yığın taşması stack overflow

Özyinelemeli get/put her seviyede yığına bir kare ekler. Yükseklik 100.000 olursa yığında 100.000 kare!

Python: varsayılan özyineleme sınırı ~1000 → RecursionError
C#: StackOverflowException yakalanamaz — program (oyun!) anında kapanır 💥
JavaScript: RangeError: Maximum call stack size exceeded

Çözüm: dengeli ağaç kullan ya da döngüyle (özyinelemesiz) yaz.

LEVEL 5

Sıralı İşlemler

ordered operations — BST’nin hash tablosuna karşı kozu

ağaç nedir?
gezinme & davranış ağaçları
arama & ikili arama
ikili arama ağacı (BST)
şekil ve performans
sıralı işlemler
silme
perde arkası & ötesi

BST sadece “var mı?” sorusuna cevap vermez

işlem	ne döndürür?	🎮 oyunda
`min()` / `max()`	en küçük / en büyük anahtar	en düşük / en yüksek skor
`floor(k)` taban	≤ k olan en büyük anahtar	MMR’ı 1530 olan oyuncuya alttan en yakın rakip
`ceiling(k)` tavan	≥ k olan en küçük anahtar	…üstten en yakın rakip
`rank(k)` sıra	k’den küçük kaç anahtar var?	“Skor tablosunda kaçıncıyım?”
`select(i)` seç	i. sıradaki anahtar	“10. sıradaki oyuncu kim?”
`keys(lo, hi)` aralık	[lo, hi] arasındaki anahtarlar	“Seviyesi 20–25 arası oyuncular”

🔑 Hash tablosu (Dictionary) bunları yapamaz!Hash tabloları get/put’ta BST’den de hızlıdır, ama anahtarları sırasız saklar. “En yakın rakip” ya da “kaçıncıyım” sorusu için tüm tabloyu taramak gerekir. (Hash tabloları: ileriki bir ders.)

🎒 Ön bilgi: aynı şeyin iki yazılışı — geleneksel ve modern

Bundan sonraki kodlarda önce geleneksel (if/for) yazımı göreceksiniz; yorum satırlarında da sık karşılaşacağınız modern kısa yazımı.

ne yapar?	geleneksel	modern
koşula göre iki değerden birini seç ternary	`if t is not None:` `return t` `else:` `return x`	Python: `return t if t is not None else x` C#/JS: `return t != null ? t : x;`
“soldaki null ise sağdakini al” null-coalescing	`if (t != null) return t;` `return x;`	C#: `return t ?? x;` JS: `return t ?? x;`
tek satırlık metot gövdesi	`int Size(Node x) {` `if (x == null) return 0;` `return x.Size; }`	C#: `int Size(Node x) => x == null ? 0 : x.Size;` JS: `const size = x => x === null ? 0 : x.size;`

İkisi de aynı makine işini yapar; modern yazım sadece daha kısa. Okuyabilmeniz yeterli — yazarken hangisi size daha açık geliyorsa onu kullanın.

floor ve ceiling taban · tavan

floor(k):

k = kök → cevap kök
k < kök → cevap kesinlikle solda
k > kök → kök bir aday; sağda ≤ k daha büyük biri varsa o, yoksa kök

ceiling: aynısının ayna görüntüsü.

🎮 Eşleştirme sistemi matchmaking: en yakın MMR

Quiz 9 · sıralı işlemler

A E I K M O P R S T U anahtarlarını içeren bir BST’de floor(G) ve ceiling(Q) nedir?

floor(G): G’den küçük ya da eşit olan en büyük anahtar → E. ceiling(Q): Q’dan büyük ya da eşit olan en küçük anahtar → R. Ağacın şekli cevabı değiştirmez; sadece kaç adımda bulunacağını değiştirir.

rank ve select: `size` alanının gücü

Her düğüm kendi alt ağacının boyutunu tutar: size(x) = 1 + size(sol) + size(sağ) (put sırasında güncellenir).

rank(k): sağa her gittiğimizde “kök + sol alt ağacın tamamı” k’den küçüktür → ekle.

select(i): sol alt ağaçta t anahtar var. i < t → sol; i > t → sağ (i − t − 1); i = t → bulduk.

🎮 Skor tablosu: “Kaçıncıyım?” — rank ve select

Aralık sorgusu ve gerçek skor tabloları

İnorder gezinmenin budanmış pruned hali: aralık dışında kalan alt ağaçlara hiç girmez.

🏆 Gerçek dünyadaMobil oyunların çoğu skor tablosunu Redis adlı veritabanındaki sıralı kümelerle sorted set tutar. İçeride BST’ye benzer sıralı bir yapı (skip list) var: “kaçıncıyım?” sorusu milyonlarca oyuncuda bile ~lg N adımda cevaplanır.

LEVEL 6

Silme

deletion — en zor kısım: iki çocuklu düğüm

ağaç nedir?
gezinme & davranış ağaçları
arama & ikili arama
ikili arama ağacı (BST)
şekil ve performans
sıralı işlemler
silme
perde arkası & ötesi

Önce kolayı: en küçüğü sil deleteMin

Sol bağlantı null olana kadar sola git.
O düğümü, kendi sağ çocuğuyla değiştir (sağ çocuğu yoksa null).
Dönüşte size’ları güncelle.

🎮 Örnek: zaman sırasına göre tutulan olay kuyruğundan en eski olayı çıkarmak.

Hibbard silmesi: üç durum Hibbard deletion

Durum 1: yaprakÇocuğu yok → ebeveynin bağlantısını null yap. Kolay!

Durum 2: tek çocukÇocuğunu ebeveyne bağla (deleteMin gibi).

Durum 3: iki çocukYerine ardılı successor koy: sağ alt ağacın en küçüğü. Ardılı da kendi yerinden deleteMin ile çıkar.

Neden ardıl? Ardıl, silinen anahtardan büyük olan en küçük anahtar: soldakilerin hepsinden büyük, sağdakilerin hepsinden küçük → simetrik sıra korunur. ✔

Hibbard silmesi — kod

Silme animasyonu

Quiz 10 · silme

S U P E R M A I O K T ağacında E (iki çocuklu) silinirse yerine hangi anahtar gelir?

E’nin sağ alt ağacı: M, I, K, O. Bunların en küçüğü (sürekli sola giderek): M → I → (I’nın solu boş) → I. I, E’nin yerine geçer; I’nın eski yerine sağ çocuğu K gelir.

📜 Hibbard’ın küçük sırrı

Hibbard silmesi (1962) hep sağdaki ardılı kullanır: simetrik değil.

Rastgele ekleme + silme işlemleri uzun süre devam ederse ağaç yavaş yavaş dengesini kaybeder: ortalama derinlik ~lg N yerine ~√N’e doğru kayar.

Basit ve her durumda verimli, simetrik bir BST silme algoritması bulmak uzun yıllar çözülemeyen bir problem olarak kaldı; pratikte çözüm: dengeli ağaçlar.

🤔 Sizce?Silerken bir seferinde ardılı, bir seferinde öncülü predecessor (soldaki en büyük) kullansak ne olur? Rastgele seçsek?

LEVEL 7

Perde Arkası & Ötesi

bellek · çöp toplayıcı · hazır yapılar · uzaysal ağaçlar

ağaç nedir?
gezinme & davranış ağaçları
arama & ikili arama
ikili arama ağacı (BST)
şekil ve performans
sıralı işlemler
silme
perde arkası & ötesi

⚙️ Ağaçlar bellekte: düğümler dağınık durur

Her düğüm ayrı bir nesne object: anahtar + değer + 2 referans + size + nesne başlığı object header.

64-bit C#’ta küçük bir düğüm bile ~40–50 bayt; bir int dizisinin elemanı ise 4 bayt.

Düğümler bellekte rastgele yerlerde → kökten yaprağa her adım büyük ihtimalle bir önbellek ıskası cache miss (sıralama dersindeki bağlı liste demosu!).

⚙️ B-ağaçları B-treeVeritabanları ve dosya sistemleri her düğüme yüzlerce anahtar sığdırır; böylece her disk/önbellek okuması çok iş görür. Ağaç çok basık olur: 1 milyar kayıt → 3–4 seviye!

🎮 Oyun motorlarındaFizik ve görüntüleme için kullanılan ağaçlar (ör. BVH) genellikle düğüm nesneleri yerine düz dizilerde saklanır — hem önbellek dostu hem çöp toplayıcıya yük yok.

⚙️ Nesne yerine dizi: işaretçi yerine indeks

Bu derste “Ağaçta derinlik deneyi” demosu 1 milyon düğümlük ağaçları tam olarak böyle kuruyor: milisaniyeler içinde! ⚡

⚙️ Çöp toplayıcı (GC)Oyun sırasında binlerce küçük Node nesnesi oluşturup atmak GC’yi tetikler → takılma stutter. Unity’de dizi tabanlı yapılar ve nesne havuzları object pooling bu yüzden çok yaygın.

Özet tablo 📋

yapı	arama (ort.)	ekleme (ort.)	en kötü	sıralı işlemler
sırasız liste (sıralı arama)	N/2	N (önce ara)	N	✘
sıralı dizi (ikili arama)	lg N	N/2	N	✔
BST	1,39 lg N	1,39 lg N	N	✔
dengeli BST (kırmızı-siyah) — sonraki ders	~lg N	~lg N	2 lg N	✔
hash tablosu — ileriki ders	~1	~1	N	✘

Değerler karşılaştırma sayısıdır (~ anlamında).

Hazır sıralı yapılar: arkalarında ağaç var

dil	sıralı sembol tablosu	içerde
C#	`SortedDictionary<K,V>`, `SortedSet<T>`	kırmızı-siyah ağaç
C++	`std::map`, `std::set`	kırmızı-siyah ağaç (yaygın uygulamalar)
Java	`TreeMap`, `TreeSet`	kırmızı-siyah ağaç
Python	yerleşik yok → `sortedcontainers` kütüphanesi	sıralı listeler
JavaScript	yerleşik yok → kendiniz yazın (ya da kütüphane)	—

🐧 Bilgisayarınızın kalbinde bir ağaçLinux çekirdeğinin işlemci zamanlayıcısı, çalışmayı bekleyen programları bir kırmızı-siyah ağaçta tutar ve hep en az işlemci zamanı almış olanı (en soldaki düğüm, yani min) seçer.

🎮 Uzaysal ağaçlar: quadtree spatial partitioning

Fareyi haritada gezdirin. Quadtree: kalabalık bölgeleri 4 çeyreğe bölmeye devam eden bir ağaç (her düğümün 4 çocuğu). Menzil sorgusu, menzille kesişmeyen kutuların tamamını atlar — BST’deki aralık sorgusunun 2 boyutlu hali!

Bu yalnızca bir tadımlıkQuadtree’nin nasıl kurulduğu, sorgunun elle izlemesi, kodu, düzgün ızgara ve BVH ile karşılaştırması ve oyun motorlarındaki ayarları ayrı bir sunumda: G2 · Uzaysal Bölümleme (56 slayt, üç demo, beş laboratuvar).

📜 Doom (1993) ve BSP ağaçları

1993’te sıradan bir PC, 3D görünen bir labirenti saniyede onlarca kez çizemiyordu. Hangi duvar hangisinin önünde?

John Carmack, akademik bir makalede gördüğü ikili uzay bölümleme binary space partitioning, BSP fikrini kullandı: harita, bir duvar çizgisiyle önü ve arkası diye ikiye bölünür, her parça yine bölünür… → bir ikili ağaç!

Ağaç, harita yüklenmeden önce bir kez hesaplanır. Oyun sırasında oyuncunun konumuna göre ağacı gezmek, duvarları yakından uzağa sıralı verir — sıralama dersindeki ressam algoritmasının tersi!

🌳 Oyun motorlarındaki ağaçlar

BSP: Doom, Quake
Quadtree / Octree: arazi, çarpışma
BVH: fizik, ışın izleme
Davranış ağaçları: YZ
Oyun ağacı + minimax: satranç, XOX

♟️ Bir sonraki büyük ağaç: oyun ağacı game tree

XOX’ta her düğüm bir tahta durumu, her çocuk olası bir hamle. Kök = boş tahta.

Tüm XOX oyunları: 255.168 farklı oyun (yaprak). Bilgisayar hepsini gezebilir → asla kaybetmez.
Satrançta ağaç evrendeki atomlardan büyük. 1997’de Deep Blue, Kasparov’u yenerken saniyede ~200 milyon pozisyon değerlendiriyordu — ve yine de ağacın küçük bir kısmını.

🔜 YakındaMinimax: “Ben en iyi hamlemi yaparım, rakip de kendi en iyisini yapar” varsayımıyla oyun ağacını postorder gezmek. Oyun YZ’sinin klasiği!

Derin hikâye: Huffman’ın dönem ödevi (1951–52)

MIT’de bilgi kuramı dersi veren Robert Fano, öğrencilerine bir seçenek sundu: ya final sınavına girersiniz ya da bir dönem ödevi yazarsınız. Ödev konusu: en verimli ikili kodu bulmak. Fano’nun kendisi de Claude Shannon’la birlikte bu problem üzerinde çalışmış, en iyi çözümü bulamamıştı.
David Huffman aylarca uğraştı; tam vazgeçip sınava çalışmaya karar verdiği sırada fikri buldu: ağacı yukarıdan aşağı değil, aşağıdan yukarı kurmak. En az görülen iki sembolü birleştir, yeni bir düğüm yap, tekrarla. Sonuç kanıtlanabilir şekilde en iyi önek koduydu.
Huffman kodlaması bugün ZIP ve PNG’nin kullandığı DEFLATE’in, JPEG’in ve MP3’ün içinde: her gün milyarlarca kez kurulan bir ikili ağaç.

DersBir ikili ağaç sadece “arama” için değildir: yapının kendisi bir karar dizisidir (sol = 0, sağ = 1). Huffman ağacı BST değildir ama aynı düşünce aracını kullanır. Bazen problemi tersinden (aşağıdan yukarı) kurmak çözümü açar.

Kaynak: Wikipedia: Huffman coding

🧰 Kütüphaneler ve araçlar

ad	platform	ne yapar / sınırları	nasıl eklenir
SortedDictionary · SortedSet	C# / Unity	Kırmızı-siyah ağaç: sıralı anahtarlar, O(log n) ekleme/silme/arama, `GetViewBetween` ile aralık sorgusu.	yerleşik
SortedList<K,V>	C#	Adı yanıltıcı: dizi tabanlıdır; arama O(log n) ama ekleme O(n). Az değişen veriler için.	yerleşik
sortedcontainers	Python	Python’da yerleşik ağaç yok; SortedList/SortedDict/SortedSet saf Python, hızlı ve yaygın.	`pip install sortedcontainers`
std::map · std::set	C++	Kırmızı-siyah ağaç; `lower_bound` ile aralık.	`#include <map>`
TreeMap	Java	Kırmızı-siyah ağaç; `floorKey`, `ceilingKey`, `subMap`.	yerleşik

🧩 Ne zaman ağaç, ne zaman sözlük?

Sadece “bu anahtar var mı, değeri ne?” → hash tablosu (Dictionary) daha hızlı.
Sıra önemliyse ağaç: “puanı 1000 ile 2000 arasındaki oyuncular”, “şu andan sonraki ilk olay”, “bu sayıdan küçük en büyük anahtar”.
Oyunlarda: zaman çizelgesindeki olaylar, sıralı sohbet geçmişi, mesafeye göre sıralı hedef listeleri, otomatik tamamlama (ön ek aralığı).
Kendi BST’nizi yazmak öğreticidir; üretimde dengeli olanları (SortedSet, std::map) kullanın.

Dengesiz ağaç tuzağıSıralı veriyi dengesiz bir BST’ye eklemek ağacı bir listeye çevirir: her işlem O(n), özyinelemeli kod derin ağaçta yığın taşmasına uğrar. Bu sunumda gördüğünüz yüksekliğe dikkat edin.

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

Sıralı veriyi dengesiz BST’ye eklemek
Silmede ardılın sağ alt ağacını kaybetmek
Derin ağaçta özyineleme ile yığın taşması
Çok eklemeli işte SortedList kullanmak

İyi bir istek (prompt) örneği

“C# (.NET 8). Bir oyunun liderlik tablosu için SortedSet<(int skor, int id)> kullanan bir sınıf yaz: Ekle, Sil, Güncelle (sil + ekle), “skoru [a, b] aralığındakiler” (GetViewBetween), “ilk 10”. Ayrıca aynı API’yi kendi yazdığın basit (dengesiz) BST ile uygula ve sıralı ekleme yapan bir testte ikisinin süresini karşılaştır.”

Dengeli mi dengesiz mi açıkça sorun
Silmenin üç durumunu (0, 1, 2 çocuk) test ettirin
Özyinelemesiz (döngüyle) sürüm isteyin
Aralık sorgusu için hazır API’yi (GetViewBetween, subMap) sorun

🚀 Proje ve araştırma önerileri

[kolay] Huffman sıkıştırıcı — Bir metin dosyasını Huffman ağacıyla kodlayıp çözün; sıkıştırma oranını ölçün.
[orta] Ağaç görselleştirici — Ekleme sırası rastgele ve sıralı olduğunda BST’nin şeklini ve yüksekliğini çizin.
[orta] Otomatik tamamlama — Sıralı bir kelime kümesinde ön ek aralığı sorgusuyla (ceiling/floor) öneriler.
[araştırma] Ortalama derinlik — Rastgele ekleme sırasının ortalama düğüm derinliğini ölçüp ~1,39 log₂ N ile karşılaştırın.

📄 Akademik okumalar ve kaynaklar

Huffman 1952 · A Method for the Construction of Minimum-Redundancy Codes (Proceedings of the IRE 40(9))
Huffman kodlaması.

Hibbard 1962 · Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting (Journal of the ACM 9(1))
BST silme yöntemi ve analizi.

Knuth 1998 · The Art of Computer Programming, Vol. 3, §6.2.2 (Addison-Wesley)
İkili arama ağaçlarının analizi.

Neler öğrendik? 🎒

Ağaç: kök, ebeveyn, çocuk, yaprak, derinlik, yükseklik.
Özyineleme ve çağrı yığını; çok derin → yığın taşması.
Gezinme: pre / in / post (yığın), level-order (kuyruk).
Davranış ağacı: seçici, dizi, koşul, eylem — preorder tick.

İkili arama: lg N; logaritma = “kaç kez yarıya?”
BST: get/put ~1,39 lg N (rastgele), en kötü N.
Sıralı işlemler: floor, ceiling, rank, select, aralık.
Silme: Hibbard, ardıl.
⚙️ Bellek, önbellek, GC · 🎮 quadtree, BSP, minimax.

Alıştırmalar 🏋️

Kâğıt-kalem: E A S Y Q U E S T I O N anahtarlarını sırayla boş bir BST’ye ekleyin. Ağacı çizin; yüksekliği nedir? Pre/in/post-order çıktıları?
Unity’de: bir sahnedeki tüm nesneleri girintili yazdıran PrintTree’yi çalıştırın; sonra her nesnenin derinliğini ve sahnenin yüksekliğini hesaplayın.
Davranış ağacı demosuna “Mermi yoksa → şarjör değiştir” davranışını ekleyecek şekilde ağacı kâğıda çizin. Yeni düğüm nereye girmeli?
p5.js’te tıklanan noktalara x koordinatına göre bir BST kuran ve ağacı ekrana çizen küçük bir program yazın. Soldan sağa tıklarsanız ne olur?
Kod laboratuvarında put’u özyinelemesiz yazın ve 1..1200 ile test edin.
🤖 Bir YZ asistanından “C#’ta BST floor fonksiyonu” isteyin. Kodu bu derste gördüğümüzle karşılaştırın; boş ağaç ve “anahtar yok” durumlarını test edin.

🎮 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.

Halo: Combat Evolved 2001 · nişancı

Xbox’ın amiral gemisi bilimkurgu nişancısı; korkak küçük Grunt’lar ve lider Elite’ler meşhurdur.

📖 Fandom wikisi · ▶ video 3:39

Doom 1993 · nişancı

Türü popülerleştiren nişancı; kaynak kodu 1997’de açıldı.

📖 Fandom wikisi · ▶ video 1:00

Civilization 1991– · sıra tabanlı strateji

Bir uygarlığı taş devrinden uzay çağına yönetirsiniz; teknoloji ağacı serinin simgesi.

📖 Fandom wikisi · ▶ video 2:45

Age of Empires 1997 · gerçek zamanlı strateji

Tarihî uygarlıklarla ordu kurup savaşılan klasik strateji serisi.

📖 Fandom wikisi · ▶ video 1:00