---
title: "İkili Ağaçlar — Bölüm 1"
subtitle: "Düğüm + parent/left/right işaretçileri, kök/yaprak, derinlik vs yükseklik, örtük traversal sırası, O(h) işlemler (subtree_first/successor/insert_after/delete) ve BST özelliği (sequence vs set)"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Demaine'in videosu:** [YouTube — Lecture 6: Binary Trees, Part 1](https://www.youtube.com/watch?v=76dhtgZt38A) (≈51 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 6: Binary Trees, Part 1](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-6-binary-trees-part-1/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 9 (L6)
- **Hoca:** Erik Demaine
- **Okuma süresi:** ≈25 dk
:::
## Bu Derste Ne Var? {#sec-bu-derste-d09}
Bugüne dek gördüğümüz yapıların hiçbiri *her şeyi* iyi yapmıyor: bağlı liste ortaya ekler ama ortaya $O(n)$'de ulaşır; dizi ortaya ulaşır ama eklerken kaydırır; hash tablosu find yapar ama find_prev/find_next'te kötüdür. Erik Demaine'in deyişiyle, **ikili ağaçlar** neredeyse her işlemi $O(\log n)$'de yapan "gördüğümüz en güçlü veri yapısıdır".
Bu ders (Bölüm 1) tüm işlemleri **$O(h)$** ($h$ = ağacın yüksekliği) yapar; bir sonraki ders $h = O(\log n)$ garantisini ekler.
Üç temel kavram bu derste yan yana gelir:
1. **İkili ağaç yapısı** — düğüm (item + parent/left/right), kök, yaprak, traversal (geziş) sırası.
2. **$O(h)$ işlemler** — subtree_first, successor, insert_after, delete; hepsi yükseklikle sınırlı.
3. **BST özelliği** — sıralı anahtarlarla, ağaç ikili aramayı dinamik olarak destekler (find, find_prev/find_next).
> *"today we are doing some of the coolest data structures we will see in this class, maybe some of the coolest data structures ever — binary trees."* — Demaine, 0:18
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 9'un (L6) kavram haritası: ikili ağaç yapısından (düğüm = item + parent/left/right) O(h) dört temel işleme (subtree_first → successor → insert_after → delete), in-order traversal sırasının ÖRTÜK temsiline (asla diziye yazılmaz) ve aynı ağacın iki arayüzüne — sequence (traversal = sıra) ve set (traversal = artan anahtar, BST özelliği). Geriye kalan tek soru, yüksekliği h'yi nasıl küçük (log n) tutarız — bu açık düğüm Ders 10'da AVL ile kapanır."
flowchart TD
A["Ders 9 (L6): İkili Ağaçlar — Bölüm 1"] --> S["İkili ağaç yapısı<br/>düğüm = item + parent/left/right"]
S --> D2["Derinlik / yükseklik<br/>köke kenar / en derin yaprağa kenar"]
A --> OP["O(h) dört işlem"]
OP --> O1["subtree_first<br/>sola git"]
OP --> O2["successor<br/>iki durum"]
OP --> O3["insert_after<br/>successor.sol"]
OP --> O4["delete<br/>item takası"]
A --> TR["Traversal sırası ÖRTÜK<br/>sol → düğüm → sağ"]
TR --> TR1["asla diziye yazılmaz<br/>kafamızda yaşar"]
A --> SQ["Sequence vs Set"]
SQ --> SQ1["sequence: traversal = sıra"]
SQ --> SQ2["set: traversal = artan anahtar<br/>BST özelliği"]
A --> Q["Açık soru: h nasıl küçük kalır?<br/>→ Ders 10: AVL (dengeli ağaç)"]
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
classDef open fill:#fde68a,stroke:#b45309,stroke-width:2.5px,color:#1f2937
class A root
class S,OP,TR,SQ branch
class D2,O1,O2,O3,O4,TR1,SQ1,SQ2 leaf
class Q open
```
::: {.callout-tip title="Builder Notu — İki Dünyanın Köprüsü"}
İkili ağaç, şimdiye dek gördüğümüz iki dünyanın güçlü yanlarını *dinamik* olarak birleştirir: bağlı listenin esnek değiştirmesi + sıralı dizinin hızlı araması.
- **Geriye → Ders 2-5:** ağaç, bağlı listenin (esnek ama yavaş erişim) ve sıralı dizinin (hızlı arama ama statik) güçlü yanlarını birleştirir — birinin zaafı ötekinin gücüdür.
- **Geriye → Ders 4 (ikili arama):** BST'de find, sıralı dizideki ikili aramanın ağaç üzerindeki halidir — ama ekleme/silme artık kaydırma değil, $O(h)$ işaretçi işi.
- **İleriye → veritabanı:** B-tree / B+-tree indeksleri tam bu fikrin disk-dostu genellemesidir; çoğu SQL motorunun varsayılan indeksi bir dengeli ağaçtır (B-tree).
- **İleriye → Ders 10 (denge):** bugün $h$ herhangi bir şey olabilir (kötü ağaçta $O(n)$); sonraki ders AVL ile $h = O(\log n)$ garanti eder.
Tek cümle: *İkili ağaç, sıralı bir düzeni "kafadaki" traversal sırasıyla temsil edip, tüm işlemleri ağaç yüksekliği $h$ ile sınırlar — yeter ki $h$ küçük ($\log n$) kalsın.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 9 (L6) motoru (_engine.py D9 bölümü) + Slate+Amber viz (_viz.py)
# Bu hücre gizlidir (#| echo: false). Aşağıdaki TÜM figür hücreleri bu hücrede
# tanımlanan BTNode / subtree_first / successor / subtree_insert_after /
# subtree_delete / tree_traversal / node_depth / node_height / bst_* /
# build_example_tree / build_chain_tree / build_balanced_tree / build_bst /
# successor_trace / delete_trace + COL_* sabitleri IMPORT ETMEDEN kullanır.
# Notion'daki öğretim içeriği (görünür Node/find display ```python bloğu) bu
# motorun tarif seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir; brief §2/§7). Standalone testte
# savefig kullanılır; Quarto render'da jupyter inline backend'i ayarlar.
# Yalnız D9 gerekenler gömülür (D1-D7 fonksiyonları GÖMÜLMEZ).
# ============================================================================
import math
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyBboxPatch, FancyArrowPatch
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir brief §1/§8)
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# ---------------------------------------------------------------------------
# _engine.py — Ders 9 (L6) ikili ağaç motoru (DETERMİNİSTİK + TEST EDİLEBİLİR)
# ---------------------------------------------------------------------------
class BTNode:
"""İkili ağaç düğümü (L6 §2): item + üç işaretçi (parent/left/right).
Değişmez: node.left.parent is node (ve right için) — parent, left/right
işleminin tersidir. Çizimde çift yönlü bağ (ok değil düz çizgi).
"""
__slots__ = ("item", "left", "right", "parent")
def __init__(self, item):
self.item = item
self.left = None
self.right = None
self.parent = None
def __repr__(self):
return f"BTNode({self.item!r})"
def subtree_first(node):
"""Alt ağacın traversal sırasındaki İLK düğümü (L6 §6): sola gidebildiğin
kadar git, düşmeden önceki düğümde dur. O(h)."""
while node.left is not None:
node = node.left
return node
def subtree_last(node):
"""Simetrik: alt ağacın traversal sırasındaki SON düğümü — sağa sonuna dek."""
while node.right is not None:
node = node.right
return node
def successor(node):
"""Traversal sırasında node'dan SONRAKİ düğüm (L6 §6, iki durum). O(h).
Durum 1 — sağ çocuk VAR: node'dan sonraki her şey sağ alt ağaçta;
ilki = subtree_first(node.right).
Durum 2 — sağ çocuk YOK: sola-dal yukarı çık (node parent'ın SOL çocuğu
olana dek); o parent successor'dur. Kök'e kadar hep sağ-dalsa
node sonuncudur → None.
"""
if node.right is not None:
return subtree_first(node.right)
while node.parent is not None and node is node.parent.right:
node = node.parent
return node.parent
def predecessor(node):
"""Simetrik (sağ ↔ sol): traversal sırasında ÖNCEKİ düğüm. O(h)."""
if node.left is not None:
return subtree_last(node.left)
while node.parent is not None and node is node.parent.left:
node = node.parent
return node.parent
def subtree_insert_after(node, new):
"""new düğümünü traversal sırasında node'dan HEMEN SONRAYA ekle (L6 §7). O(h).
Durum 1 — node.right YOK: new doğrudan node.right olur.
Durum 2 — node.right VAR: successor = subtree_first(node.right) bul;
successor'ın SOL çocuğu OLAMAZ (sağa bir kez + sola sonuna dek
inilerek bulundu) → new, successor.left olur.
"""
if node.right is None:
node.right = new
new.parent = node
else:
succ = subtree_first(node.right)
succ.left = new # garanti: succ.left boştu
new.parent = succ
return new
def subtree_delete(node):
"""node'un İTEMİNİ traversal sırasından çıkar (L6 §8). O(h).
Yaprak → parent'tan kopar (taban durum). Değilse: sol çocuk varsa
predecessor ile İTEM TAKASI yap (item bir seviye AŞAĞI iner), predecessor'ı
özyinele sil; sol yoksa (sağ var) successor ile simetrik. Her takas bir
seviye indirir → toplam ≤ h takas. Düğüm daireleri yerinde kalır; ilk kez
düğümlerin İÇERİĞİNİ değiştiriyoruz, kendilerini değil (Demaine 47:02).
Döndürür: gerçekten koparılan yaprak düğüm.
"""
if node.left is None and node.right is None: # yaprak — kopar
p = node.parent
if p is not None:
if p.left is node:
p.left = None
else:
p.right = None
node.parent = None
return node
if node.left is not None: # predecessor ile takas
other = predecessor(node)
else: # successor ile takas
other = successor(node)
node.item, other.item = other.item, node.item
return subtree_delete(other)
def tree_traversal(root):
"""In-order traversal (L6 §5): sol → düğüm → sağ; tüm ağaç O(n).
NOT: Bu sıra yalnız doğrulama/figür içindir — gerçek yapıda sıra ÖRTÜK
tutulur, asla diziye yazılmaz (Demaine 30:37).
"""
if root is None:
return []
return (tree_traversal(root.left) + [root.item]
+ tree_traversal(root.right))
def node_depth(node):
"""Derinlik (L6 §4): node'dan KÖKE giden yoldaki kenar sayısı. Kök = 0."""
d = 0
while node.parent is not None:
node = node.parent
d += 1
return d
def node_height(node):
"""Yükseklik (L6 §4): alt ağaçtaki EN UZUN aşağı yolun kenar sayısı.
Yaprak = 0; boş (None) = −1 konvansiyonu."""
if node is None:
return -1
return 1 + max(node_height(node.left), node_height(node.right))
# ---------------------------------------------------------------- BST (L6 §9)
def bst_find(root, k):
"""BST find (L6 §9): kökten in — k < anahtar → sol, k > anahtar → sağ,
eşit → bulundu. İkili aramanın ağaç hâli. O(h). Yoksa None."""
node = root
while node is not None:
if k == node.item:
return node
node = node.left if k < node.item else node.right
return None
def bst_insert(root, k):
"""BST insert: find yolundan in, düştüğün yere yaprak ekle. O(h).
Döndürür: (root, yeni düğüm). Eşit anahtar sağa gider (basit konvansiyon)."""
new = BTNode(k)
if root is None:
return new, new
node = root
while True:
if k < node.item:
if node.left is None:
node.left = new
new.parent = node
return root, new
node = node.left
else:
if node.right is None:
node.right = new
new.parent = node
return root, new
node = node.right
def build_bst(keys):
"""Anahtar listesinden (sırayla insert) BST kur — deterministik."""
root = None
for k in keys:
root, _ = bst_insert(root, k)
return root
# ------------------------------------------------------- örnek ağaç kurucular
def _link(parent, left_item=None, right_item=None):
"""İç yardımcı: parent'a çocuk düğümler bağla, (sol, sağ) döndür."""
l = r = None
if left_item is not None:
l = BTNode(left_item)
l.parent = parent
parent.left = l
if right_item is not None:
r = BTNode(right_item)
r.parent = parent
parent.right = r
return l, r
def build_example_tree():
"""L6 figürleri için deterministik örnek (n=7, h=2, traversal A..G):
D
/ \\
B F
/ \\ / \\
A C E G
"""
root = BTNode("D")
b, f = _link(root, "B", "F")
_link(b, "A", "C")
_link(f, "E", "G")
return root
def build_chain_tree(n):
"""KÖTÜ ağaç (L6 §4): yalnız sağ işaretçiler — bağlı liste gibi, h = n−1."""
if n <= 0:
return None
root = BTNode(0)
cur = root
for i in range(1, n):
new = BTNode(i)
new.parent = cur
cur.right = new
cur = new
return root
def build_balanced_tree(items):
"""Dengeli ağaç: sıralı listeden ortadan-böl özyineleme → h = ⌊log₂ n⌋."""
def rec(lo, hi, parent):
if lo > hi:
return None
mid = (lo + hi) // 2
node = BTNode(items[mid])
node.parent = parent
node.left = rec(lo, mid - 1, node)
node.right = rec(mid + 1, hi, node)
return node
return rec(0, len(items) - 1, None)
# --------------------------------------------------------- figür trace'leri
def successor_trace(node):
"""fig-successor için: ziyaret edilen düğüm item'ları + durum etiketi.
Döndürür: {"case": 1|2, "path": [item, ...], "result": item|None}
"""
path = [node.item]
if node.right is not None:
cur = node.right
path.append(cur.item)
while cur.left is not None:
cur = cur.left
path.append(cur.item)
return {"case": 1, "path": path, "result": cur.item}
cur = node
while cur.parent is not None and cur is cur.parent.right:
cur = cur.parent
path.append(cur.item)
res = cur.parent
if res is not None:
path.append(res.item)
return {"case": 2, "path": path, "result": res.item if res else None}
def delete_trace(root, item):
"""fig-delete-swap için: item'ı bul, silme sürecindeki TAKASLARI kaydet.
Döndürür: {"swaps": [(üst_item, alt_item), ...], "removed_leaf": item,
"traversal_after": [...]}
"""
def find_node(node):
if node is None:
return None
if node.item == item:
return node
return find_node(node.left) or find_node(node.right)
node = find_node(root)
swaps = []
while not (node.left is None and node.right is None):
other = predecessor(node) if node.left is not None else successor(node)
swaps.append((node.item, other.item))
node.item, other.item = other.item, node.item
node = other
subtree_delete(node)
return {
"swaps": swaps,
"removed_leaf": node.item,
"traversal_after": tree_traversal(root),
}
```
## Hedef: Tüm İşlemler O(log n) {#sec-hedef}
İki arayüzü hatırla: **dizi (sequence)** — ortaya ekle/sil, $i$. öğeye eriş; **küme (set)** — anahtarla ara, find_prev/find_next. Şimdiye dek hiçbir yapı bunların *hepsini* verimli yapmadı. İkili ağaçların hedefi: build/iterate dışındaki tüm işlemleri **$O(\log n)$** (uçlarda sabit-zamanlı bağlı liste/dinamik diziden bir log faktör geride, ama her yerde hızlı).
Bugün bu işlemleri **$O(h)$** ($h$ = yükseklik) yapacağız; $h$'yi $\log n$'e bağlamak sonraki dersin işi. @fig-chain-vs-balanced bu "$O(h)$ iyi mi kötü mü?" sorusunu somutlaştırır: aynı 7 öğe, zincir ağaçta $h = 6$, dengeli ağaçta $h = 2$.
```{python}
#| label: fig-chain-vs-balanced
#| fig-cap: "$O(h)$ iyi mi kötü mü? → tamamen $h$'ye bağlı. İki panel AYNI 7 öğeyle ($0..6$) çizilir. **Sol — zincir ağaç** (yalnız sağ çocuklar, `build_chain_tree(7)`): bağlı liste gibi düz iner, $h = 6 = n - 1$ (motor hesaplı, EXACT); tüm $O(h)$ işlemler $O(n)$'e düşer. **Sağ — dengeli ağaç** (`build_balanced_tree([0..6])`, sıralı listeyi ortadan böl): yalnızca 3 seviye, $h = 2 = \\lfloor \\log_2 7 \\rfloor$ (motor hesaplı, EXACT). İki ağacın in-order traversal'ı AYNI $[0,1,2,3,4,5,6]$ — yalnız ŞEKİL farklı. Açık soru: $h$'yi kim küçük tutar? → Ders 10: AVL (kendini dengeleyen ağaç) bu düğümü kapatır."
#| fig-width: 10.5
#| fig-height: 6.6
# fig-chain-vs-balanced (L6 §1/§4 sentez): zincir (h=n−1) vs dengeli (h=⌊log₂n⌋).
# Aynı 7 öğe (0..6); traversal her ikisinde [0..6]; yalnız şekil/yükseklik farklı.
# Veri MOTORDAN gelir (build_chain_tree / build_balanced_tree / node_height /
# tree_traversal). COL_* / plt gizli setup hücresinden (inline _engine + _viz).
_CB_LEVEL_GAP = 1.35
_CB_NODE_R = 0.34
def _cb_layout(root):
pos = {}
counter = [0]
def rec(node):
if node is None:
return
rec(node.left)
x = float(counter[0])
counter[0] += 1
y = -node_depth(node) * _CB_LEVEL_GAP
pos[node] = (x, y)
rec(node.right)
rec(root)
return pos
def _cb_draw_tree(ax, root, pos, *, accent_node_edges, x_shift):
fc_node, ec_node = accent_node_edges
for node, (x, y) in pos.items():
for child in (node.left, node.right):
if child is not None and child in pos:
cx, cy = pos[child]
ax.plot([x + x_shift, cx + x_shift], [y, cy],
color=COL_SLATE_500, linewidth=1.6, zorder=1,
solid_capstyle="round")
for node, (x, y) in pos.items():
ax.add_patch(Circle(
(x + x_shift, y), _CB_NODE_R, fc=fc_node, ec=ec_node,
linewidth=2.0, zorder=3))
ax.text(x + x_shift, y, str(node.item), ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold", zorder=4)
n = 7
items = list(range(n)) # 0..6
chain = build_chain_tree(n) # yalnız sağ çocuklar
balanced = build_balanced_tree(items) # ortadan-böl
h_chain = node_height(chain)
h_balanced = node_height(balanced)
assert h_chain == 6 and h_balanced == 2
assert tree_traversal(chain) == items and tree_traversal(balanced) == items
pos_chain = _cb_layout(chain)
pos_bal = _cb_layout(balanced)
fig, ax = plt.subplots(figsize=(10.5, 6.6))
fig.patch.set_facecolor(COL_WHITE)
left_min = min(p[0] for p in pos_chain.values())
left_max = max(p[0] for p in pos_chain.values())
right_shift = left_max + 4.2
_cb_draw_tree(ax, chain, pos_chain,
accent_node_edges=(COL_BG, COL_SLATE_500), x_shift=0.0)
_cb_draw_tree(ax, balanced, pos_bal,
accent_node_edges=(COL_AMBER_100, COL_ACCENT), x_shift=right_shift)
chain_top = max(p[1] for p in pos_chain.values())
chain_bot = min(p[1] for p in pos_chain.values())
bal_top = max(p[1] for p in pos_bal.values())
left_cx = (left_min + left_max) * 0.5
right_cx = right_shift + (min(p[0] for p in pos_bal.values())
+ max(p[0] for p in pos_bal.values())) * 0.5
ax.text(left_cx, chain_top + 0.95, "Zincir ağaç", ha="center", va="center",
fontsize=12, color=COL_TEXT, weight="bold")
ax.text(left_cx, chain_top + 0.52, "(yalnız sağ çocuklar)", ha="center",
va="center", fontsize=9, color=COL_SLATE_500, style="italic")
ax.text(right_cx, bal_top + 0.95, "Dengeli ağaç", ha="center", va="center",
fontsize=12, color=COL_TEXT, weight="bold")
ax.text(right_cx, bal_top + 0.52, "(3 seviye)", ha="center",
va="center", fontsize=9, color=COL_SLATE_500, style="italic")
chain_h_x = left_max + 0.95
chain_h_y = (chain_top + chain_bot) * 0.5
ax.add_patch(FancyBboxPatch(
(chain_h_x - 0.05, chain_h_y - 0.42), 1.95, 0.84,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.8, zorder=2))
ax.text(chain_h_x + 0.92, chain_h_y, "h = 6 = n−1", ha="center", va="center",
fontsize=11, color=COL_SLATE_500, weight="bold", zorder=4)
bal_h_x = right_shift + max(p[0] for p in pos_bal.values()) + 0.85
bal_h_y = (bal_top + min(p[1] for p in pos_bal.values())) * 0.5
ax.add_patch(FancyBboxPatch(
(bal_h_x - 0.05, bal_h_y - 0.42), 2.55, 0.84,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=2))
ax.text(bal_h_x + 1.22, bal_h_y, "h = 2 = ⌊log₂ 7⌋", ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(left_cx, chain_bot - 0.85,
"bağlı liste gibi —\nTÜM O(h) işlemler O(n)'e düşer",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
weight="bold")
ax.text(right_cx, chain_bot - 0.85,
"aynı 7 öğe, aynı traversal —\nyalnız ŞEKİL farklı",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold")
arrow_y = (bal_top + min(p[1] for p in pos_bal.values())) * 0.5
arrow_x0 = chain_h_x + 1.95 + 0.25
arrow_x1 = right_shift + min(p[0] for p in pos_bal.values()) - 0.65
ax.add_patch(FancyArrowPatch(
(arrow_x0, arrow_y), (arrow_x1, arrow_y),
arrowstyle="-|>", mutation_scale=18, color=COL_AMBER_600,
linewidth=2.4, zorder=5))
ax.text((arrow_x0 + arrow_x1) * 0.5, arrow_y + 0.34,
"aynı öğeler\nyeniden dengele", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
fig.suptitle(
"O(h) iyi mi kötü mü? → h'ye bağlı",
color=COL_TEXT, fontsize=14, weight="bold", y=0.975)
box_y = chain_bot - 1.95
box_left = left_min - 0.6
box_right = bal_h_x + 2.7
box_w = box_right - box_left
ax.add_patch(FancyBboxPatch(
(box_left, box_y), box_w, 0.86,
boxstyle="round,pad=0.03,rounding_size=0.12",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
ax.text(box_left + box_w * 0.5, box_y + 0.43,
"Açık soru: h'yi kim KÜÇÜK tutar? → Ders 10: AVL (kendini dengeleyen ağaç)",
ha="center", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.set_xlim(box_left - 0.4, box_right + 0.4)
ax.set_ylim(box_y - 0.4, chain_top + 1.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## İkili Ağaç Nedir? {#sec-ikili-agac}
Bir **ikili ağaç**, dairelerle çizdiğimiz **düğümlerden (node)** oluşur. Her düğüm bir **item** ve üç işaretçi tutar: `node.parent`, `node.left`, `node.right`. Çizimde çift yönlü (parent ↔ child) bağlar olduğundan oklar yerine düz çizgiler kullanılır.
- **Kök (root):** parent'ı olmayan tek düğüm.
- **Yaprak (leaf):** çocuğu olmayan düğüm.
- **Değişmez:** `node.left.parent == node` (ve right için de) — parent, left/right işleminin tersidir.
> *"with binary trees, because we use two types of next pointers — left and right — we can build a tree, and trees in general can have logarithmic height."* — Demaine, 8:37
@fig-tree-anatomy bu anatomiyi tek bir örnek ağaçta toplar: düğüm yapısı, kök/yaprak ve derinlik ile yüksekliğin görsel ayrımı.
```{python}
#| label: fig-tree-anatomy
#| fig-cap: "İkili ağaç anatomisi (L6 §2/§4): deterministik örnek ağaç ($D$ kök; in-order traversal $A,B,C,D,E,F,G$; $h = 2$). **Orta:** 7 daire düğüm + düz çizgi kenarlar (ok yok — çift yönlü parent↔child bağı); kök $D$ amber çerçeveli (parent yok), yapraklar $A,C,E,G$ (çocuk yok). **Sol yakın çekim:** $B$ düğümü = item + 3 işaretçi (parent yukarı, left/right aşağı). **Sağ:** iki yol kıyaslanır — $A$ için **derinlik** (slate kesikli, $A \\to B \\to D$, köke 2 kenar, $d(A) = 2$) ve kök $D$ için **yükseklik** (amber, $D \\to F \\to G$, en derin yaprağa 2 kenar, $h = 2$). Ağacın yüksekliği = kök yüksekliği = $h$; bugünkü tüm işlemler $O(h)$."
#| fig-width: 10.5
#| fig-height: 6.6
# fig-tree-anatomy (L6 §2/§4): düğüm yapısı + kök/yaprak + derinlik vs yükseklik.
# Veri MOTORDAN (build_example_tree / tree_traversal / node_height / node_depth).
_TA_NODE_R = 0.30
_TA_X_STEP = 1.25
_TA_Y_STEP = 1.55
_TA_Y_TOP = 0.0
def _ta_layout(root):
pos = {}
counter = [0]
def rec(node, depth):
if node is None:
return
rec(node.left, depth + 1)
x = counter[0] * _TA_X_STEP
counter[0] += 1
pos[node] = (x, _TA_Y_TOP - depth * _TA_Y_STEP)
rec(node.right, depth + 1)
rec(root, 0)
return pos
def _ta_find(root, item):
if root is None:
return None
if root.item == item:
return root
return _ta_find(root.left, item) or _ta_find(root.right, item)
def _ta_draw_node(ax, x, y, item, *, fc, ec, lw=2.0, tcol=None, fontsize=12.5,
zorder=4):
ax.add_patch(Circle((x, y), _TA_NODE_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=zorder))
ax.text(x, y, str(item), ha="center", va="center", fontsize=fontsize,
color=tcol or COL_TEXT, weight="bold", zorder=zorder + 1)
def _ta_draw_edge(ax, p0, p1, *, color=COL_SLATE_500, lw=1.6, dashed=False,
zorder=1):
x0, y0 = p0
x1, y1 = p1
dx, dy = x1 - x0, y1 - y0
dist = math.hypot(dx, dy)
ux, uy = dx / dist, dy / dist
sx, sy = x0 + ux * _TA_NODE_R, y0 + uy * _TA_NODE_R
ex, ey = x1 - ux * _TA_NODE_R, y1 - uy * _TA_NODE_R
ax.plot([sx, ex], [sy, ey], color=color, linewidth=lw,
linestyle=(0, (5, 2)) if dashed else "-", zorder=zorder,
solid_capstyle="round")
root = build_example_tree()
assert tree_traversal(root) == list("ABCDEFG")
assert node_height(root) == 2
pos = _ta_layout(root)
nodes = {nd.item: nd for nd in pos}
A, B, C, D = nodes["A"], nodes["B"], nodes["C"], nodes["D"]
E, F, G = nodes["E"], nodes["F"], nodes["G"]
leaves = {"A", "C", "E", "G"}
fig, ax = plt.subplots(figsize=(10.5, 6.6))
fig.patch.set_facecolor(COL_WHITE)
for nd in pos:
for child in (nd.left, nd.right):
if child is not None:
_ta_draw_edge(ax, pos[nd], pos[child], color=COL_SLATE_500,
lw=1.7, zorder=1)
for item, nd in nodes.items():
x, y = pos[nd]
if item == "D":
_ta_draw_node(ax, x, y, item, fc=COL_AMBER_100, ec=COL_ACCENT, lw=2.6)
else:
_ta_draw_node(ax, x, y, item, fc=COL_BG, ec=COL_PRIMARY, lw=1.8)
dx, dy = pos[D]
ax.text(dx, dy + _TA_NODE_R + 0.46, "kök (parent yok)", ha="center",
va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold")
ax.add_patch(FancyArrowPatch(
(dx, dy + _TA_NODE_R + 0.34), (dx, dy + _TA_NODE_R + 0.04),
arrowstyle="-|>", mutation_scale=12, color=COL_AMBER_700,
linewidth=1.8, zorder=5))
leaf_y = pos[A][1]
leaf_xs = [pos[nodes[i]][0] for i in ("A", "C", "E", "G")]
ax.text((min(leaf_xs) + max(leaf_xs)) * 0.5, leaf_y - _TA_NODE_R - 0.46,
"yapraklar A · C · E · G (çocuk yok)", ha="center", va="center",
fontsize=9, color=COL_SLATE_500, style="italic")
zx, zy = -3.05, -0.45
zr = 0.52
ax.add_patch(Circle((zx, zy), zr, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=2.6, zorder=4))
ax.text(zx, zy, "B", ha="center", va="center", fontsize=18,
color=COL_TEXT, weight="bold", zorder=5)
ax.text(zx, zy + zr + 0.78, "düğüm = item + 3 işaretçi", ha="center",
va="center", fontsize=10, color=COL_TEXT, weight="bold")
ax.text(zx, zy + zr + 0.50, "node.item", ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic")
ax.add_patch(FancyArrowPatch(
(zx, zy + zr + 0.06), (zx, zy + zr + 0.34),
arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_700,
linewidth=2.0, zorder=5))
ax.text(zx + 0.12, zy + zr + 0.22, "parent", ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold")
for sign, lbl, col in ((-1, "left", COL_PRIMARY), (1, "right", COL_PRIMARY)):
ox = zx + sign * zr * 0.66
ax.add_patch(FancyArrowPatch(
(ox, zy - zr + 0.04), (ox + sign * 0.30, zy - zr - 0.34),
arrowstyle="-|>", mutation_scale=12, color=col,
linewidth=1.9, zorder=5))
ax.text(ox + sign * 0.34, zy - zr - 0.42, lbl,
ha="center", va="center", fontsize=8.5, color=col, weight="bold")
depth_path = [A, B, D]
for i in range(len(depth_path) - 1):
_ta_draw_edge(ax, pos[depth_path[i]], pos[depth_path[i + 1]],
color=COL_SLATE_400, lw=3.0, dashed=True, zorder=2)
ax.text(pos[A][0] - _TA_NODE_R - 0.18, pos[A][1], "d(A) = 2",
ha="right", va="center", fontsize=10, color=COL_SLATE_500,
weight="bold", zorder=6)
height_path = [D, F, G]
for i in range(len(height_path) - 1):
_ta_draw_edge(ax, pos[height_path[i]], pos[height_path[i + 1]],
color=COL_ACCENT, lw=3.2, dashed=False, zorder=3)
mx = (pos[D][0] + pos[F][0]) * 0.5 + 0.22
my = (pos[D][1] + pos[F][1]) * 0.5 + 0.22
ax.text(mx, my, "h(kök) = 2", ha="left", va="center", fontsize=10,
color=COL_AMBER_700, weight="bold", zorder=6)
lx = max(p[0] for p in pos.values()) + 0.95
ly = _TA_Y_TOP + 0.05
ax.add_patch(FancyBboxPatch(
(lx, ly - 1.55), 2.85, 1.55,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=2))
ax.plot([lx + 0.20, lx + 0.70], [ly - 0.40, ly - 0.40],
color=COL_SLATE_400, linewidth=3.0, linestyle=(0, (5, 2)),
zorder=3, solid_capstyle="round")
ax.text(lx + 0.85, ly - 0.40, "derinlik (koke)", ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, weight="bold")
ax.plot([lx + 0.20, lx + 0.70], [ly - 0.92, ly - 0.92],
color=COL_ACCENT, linewidth=3.2, zorder=3, solid_capstyle="round")
ax.text(lx + 0.85, ly - 0.92, "yükseklik (aşağı)", ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold")
ax.add_patch(Circle((lx + 0.45, ly - 1.36), 0.13, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=2.0, zorder=3))
ax.text(lx + 0.85, ly - 1.36, "kök = D", ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold")
bottom_y = pos[A][1] - _TA_NODE_R - 0.92
ax.text((min(leaf_xs) + max(leaf_xs)) * 0.5, bottom_y,
"derinlik = düğümden köke kenar sayısı · yükseklik = en uzun "
"aşağı yol · ağacın yüksekliği = kök yüksekliği = h",
ha="center", va="center", fontsize=9, color=COL_TEXT)
fig.suptitle(
"İkili ağaç anatomisi: düğüm (item + parent/left/right) · kök/yaprak · "
"derinlik vs yükseklik",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
all_y = [p[1] for p in pos.values()]
ax.set_xlim(zx - zr - 0.7, lx + 3.1)
ax.set_ylim(bottom_y - 0.45, max(all_y) + _TA_NODE_R + 0.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Neden İki İşaretçi? {#sec-iki-isaretci}
Bağlı liste düğümünün tek "sonraki" işaretçisi vardır → yalnızca bir liste kurabilir, ortadaki düğümün **derinliği lineerdir** (oraya ulaşmak $O(n)$). İkili ağaç **iki** tür sonraki işaretçi (left, right) kullandığından bir *ağaç* kurabilir; ağaçlar **logaritmik yükseklikte** olabilir, böylece kökten herhangi bir düğüme yalnızca $\log n$ adımda ulaşılır. İki dünyanın en iyisinin sırrı budur.
## Tanımlar: Alt Ağaç, Derinlik, Yükseklik {#sec-tanimlar}
- **Alt ağaç (subtree of x):** $x$ ve tüm torunları (descendants); $x$ o alt ağacın köküdür.
- **Derinlik (depth):** $x$'ten köke giden yoldaki **kenar sayısı** ($x$'in atalarının sayısı). Kökün derinliği 0.
- **Yükseklik (height):** $x$'in alt ağacındaki **en uzun aşağı yoldaki kenar sayısı** (= alt ağaçtaki maksimum derinlik). Yaprakların yüksekliği 0.
> *"height of a node is the number of edges in the longest downward path."* — Demaine, 13:03
Ağacın yüksekliği = **kökün yüksekliği = $h$**. Bugünkü tüm işlemler $O(h)$ olacak; kötü bir ağaç (sadece sağ işaretçiler kullanılan, bağlı liste gibi) $O(n)$ yüksekliğe sahip olabilir — bundan kaçınmak sonraki dersin konusu (bkz. @fig-chain-vs-balanced).
## Traversal (Geziş) Sırası {#sec-traversal}
Ağaçta doğal bir düzen vardır: **traversal sırası** (in-order). Özyinelemeli tanım: her düğüm için, `node.left` alt ağacındaki düğümler $x$'ten **önce**, `node.right` alt ağacındakiler **sonra** gelir.
> *"the nodes in x.left are before x, and the nodes in x.right come after x."* — Demaine, 18:24
Geziş algoritması: sol alt ağacı gez → $x$'i çıkar → sağ alt ağacı gez (tüm ağaç için $O(n)$). **Kritik:** bu sıra **asla açıkça hesaplanmaz** — diziye yazılamaz (ortaya ekleme $O(n)$ olurdu). Sıra her zaman *örtüktür*, "kafamızdadır"; ağaç yapısı onu örtük olarak kodlar.
> *"the traversal order is never explicitly computed... it's always implicit, in our heads."* — Demaine, 30:37
@fig-traversal-order, örnek ağacın bu örtük sırasını (altta hayalet bir dizi olarak) ve düğümlerden o diziye inen kesikli okları gösterir.
```{python}
#| label: fig-traversal-order
#| fig-cap: "In-order traversal: ağacın ÖRTÜK sırası (L6 §5; sol → düğüm → sağ). Üstte örnek ağaç (7 düğüm, kök $D$); her düğümün üst-sağında amber sıra rozeti ($A{\\to}1, \\dots, G{\\to}7$). Altta **hayalet** bir dizi şeridi $[A][B][C][D][E][F][G]$ — kesikli çerçeveli, çünkü bu dizi ASLA gerçekten kurulmaz; her düğümden kendi hücresine ince kesikli slate ok iner. Vurgu (amber kutu): sıra ÖRTÜKTÜR, işaretçilerde yaşar — diziye yazmak ortaya eklemeyi $O(n)$ yapardı, ağacın tüm amacı tam da bundan kaçınmaktır (Demaine 30:37)."
#| fig-width: 10.0
#| fig-height: 6.4
# fig-traversal-order (L6 §5): in-order ÖRTÜK düzen — ağaç + hayalet dizi şeridi.
# Veri MOTORDAN (build_example_tree / tree_traversal / node_depth).
_TO_R = 0.34
_TO_LEVEL_GAP = 1.30
_TO_X_UNIT = 1.30
_TO_CELL_W = _TO_X_UNIT
_TO_CELL_H = 0.66
def _to_assign_inorder_x(root):
pos = {}
counter = [0]
def rec(node):
if node is None:
return
rec(node.left)
pos[node] = counter[0]
counter[0] += 1
rec(node.right)
rec(root)
return pos
root = build_example_tree()
order = tree_traversal(root)
assert order == ["A", "B", "C", "D", "E", "F", "G"]
xpos = _to_assign_inorder_x(root)
nodes_inorder = sorted(xpos, key=lambda nd: xpos[nd])
fig, ax = plt.subplots(figsize=(10.0, 6.4))
fig.patch.set_facecolor(COL_WHITE)
node_xy = {}
for nd in nodes_inorder:
x = xpos[nd] * _TO_X_UNIT
y = -node_depth(nd) * _TO_LEVEL_GAP
node_xy[nd] = (x, y)
for nd in nodes_inorder:
for child in (nd.left, nd.right):
if child is not None:
x0, y0 = node_xy[nd]
x1, y1 = node_xy[child]
ax.plot([x0, x1], [y0, y1], color=COL_SLATE_400,
linewidth=1.8, zorder=1, solid_capstyle="round")
rank_of = {item: i for i, item in enumerate(order, start=1)}
for nd in nodes_inorder:
x, y = node_xy[nd]
ax.add_patch(Circle((x, y), _TO_R, facecolor=COL_BG, edgecolor=COL_PRIMARY,
linewidth=2.0, zorder=4))
ax.text(x, y, str(nd.item), ha="center", va="center",
fontsize=13, color=COL_TEXT, weight="bold", zorder=6)
rank = rank_of[nd.item]
bx, by = x + _TO_R * 0.92, y + _TO_R * 0.92
ax.add_patch(Circle((bx, by), 0.155, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=1.6, zorder=7))
ax.text(bx, by, str(rank), ha="center", va="center", fontsize=7.5,
color=COL_AMBER_700, weight="bold", zorder=8)
rx, ry = node_xy[root]
ax.text(rx, ry + _TO_R + 0.30, "kök", ha="center", va="bottom",
fontsize=9, color=COL_SLATE_500, style="italic", zorder=5)
min_y = min(y for (_, y) in node_xy.values())
strip_y = min_y - 1.30
cell_cx = []
for i, item in enumerate(order):
cx = i * _TO_X_UNIT
x_left = cx - _TO_CELL_W * 0.42
ax.add_patch(FancyBboxPatch(
(x_left, strip_y), _TO_CELL_W * 0.84, _TO_CELL_H,
boxstyle="square,pad=0.0",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=2,
linestyle=(0, (4, 2))))
ax.text(cx, strip_y + _TO_CELL_H * 0.5, str(item), ha="center", va="center",
fontsize=11.5, color=COL_SLATE_500, weight="bold", zorder=4)
ax.text(cx, strip_y - 0.26, str(i), ha="center", va="center",
fontsize=8, color=COL_SLATE_400, zorder=4)
cell_cx.append(cx)
ax.text(-_TO_X_UNIT * 0.75, strip_y + _TO_CELL_H * 0.5,
"traversal\nsırası\n(in-order)", ha="right", va="center", fontsize=9.5,
color=COL_AMBER_700, weight="bold", zorder=5)
for nd in nodes_inorder:
x, y = node_xy[nd]
cx = cell_cx[rank_of[nd.item] - 1]
ax.add_patch(FancyArrowPatch(
(x, y - _TO_R - 0.04), (cx, strip_y + _TO_CELL_H + 0.04),
arrowstyle="-|>", mutation_scale=9, color=COL_SLATE_400,
linewidth=1.0, zorder=3, linestyle=(0, (2, 2)),
shrinkA=0, shrinkB=2))
note_y = strip_y - 1.12
box_left = cell_cx[0] - _TO_CELL_W * 0.52
box_w = (cell_cx[-1] + _TO_CELL_W * 0.42) - box_left
ax.add_patch(FancyBboxPatch(
(box_left, note_y), box_w, 0.78,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=2))
ax.text(box_left + box_w * 0.5, note_y + 0.50,
"Bu dizi ASLA açıkça kurulmaz — sıra ÖRTÜKTÜR, işaretçilerde yaşar.",
ha="center", va="center", fontsize=9.8, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(box_left + box_w * 0.5, note_y + 0.20,
"\"the traversal order... is always implicit, in our heads.\" "
"— Demaine 30:37",
ha="center", va="center", fontsize=8.3, color=COL_SLATE_500,
style="italic", zorder=4)
fig.suptitle(
"In-order traversal: ağacın ÖRTÜK sırası (sol → düğüm → sağ)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
xs_all = [x for (x, _) in node_xy.values()] + cell_cx
ax.set_xlim(min(xs_all) - 2.3, max(xs_all) + 0.9)
ax.set_ylim(note_y - 0.45, max(y for (_, y) in node_xy.values()) + _TO_R + 0.85)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-tip title="Builder Notu — Örtük Düzen, Range Scan ve Lazy Temsil"}
Traversal sırasının asla diziye yazılmaması, bir veri yapısı tasarım ilkesinin saf hâlidir: *pahalı bir gösterimi açıkça tutmak yerine, ucuz güncellenebilir bir yapıyla örtük temsil et.*
- **DB indeks `BETWEEN` / range scan:** Bir B-tree indeksinde `WHERE x BETWEEN a AND b` sorgusu, tam olarak in-order traversal'ın bir parçasını yürür — `a`'yı bul, successor zinciriyle `b`'ye kadar git. Sıralı sonuç "kafadaki" düzenden okunur, ayrıca tutulan bir sıralı dizi yoktur.
- **Sıralı yineleme (ordered iteration):** Bir set'i artan sırada gezmek (`SELECT ... ORDER BY` indeks üzerinden) ağaçta doğal $O(n)$ traversal'dır; ekstra sıralama maliyeti yoktur çünkü düzen yapıda zaten kodludur.
- **Lazy temsil genel ilkesi:** "Materialize etme, gerektiğinde üret" — sıralı dizi (eager) yerine ağaç (lazy) seçmek, ortaya ekleme/silmeyi $O(n)$'den $O(h)$'ye düşürür. Aynı sezgi: streaming iterator'lar, generator'lar, sanal DOM diff'leri.
Tek cümle: *Örtük traversal, "sıralı görünmek" ile "sıralı dizi tutmak" arasındaki farktır — birincisi $O(h)$'de güncellenir, ikincisi $O(n)$'de.*
:::
## subtree_first ve successor {#sec-subtree-first-successor}
İki temel sorgu (ikisi de **$O(h)$**):
- **`subtree_first(node)`:** Bir alt ağacın traversal sırasındaki ilk düğümü. Tanım gereği sol her zaman önce gelir → mümkün olduğunca **sola git** (`node = node.left`), düşmeden bir önceki düğümde dur.
- **`successor(node)`:** Tüm ağacın traversal sırasında node'dan *sonraki* düğüm. İki durum:
> *"all of these operations are going to be order h."* — Demaine, 32:02
**Çalışılan Örnek — successor.** *Durum 1:* node'un sağ çocuğu varsa, successor = `subtree_first(node.right)` (sağ alt ağacın en solundaki düğüm — node'dan sonraki her şeyin ilki). *Durum 2:* sağ çocuk yoksa, **sola-dal yukarı çık**: `node = node.parent`, ta ki bir "sol dalı" yukarı çıkana dek (yani önceki düğüm parent'ın sol çocuğuysa). O parent, successor'dur. Sezgi: sağ alt ağaç yoksa, node'dan sonra gelen ilk şey, onu sol-tarafında bırakan en yakın atadır.
Örnek ağaçta (kök $D$): `successor(B) = C` Durum 1'dir ($B$'nin sağ çocuğu $C$ var); `successor(C) = D` Durum 2'dir ($C$'nin sağ çocuğu yok, yol $C \to B \to D$). @fig-successor bu iki durumu yan yana gösterir.
```{python}
#| label: fig-successor
#| fig-cap: "Traversal successor — iki durum, her ikisi de $O(h)$ (L6 §6, **İMZA** figür; örnek ağaç $A..G$, $h = 2$). **Sol panel — Durum 1, successor(B):** $B$'nin sağ çocuğu VAR → successor sağ alt ağacın ilkidir: `subtree_first(node.right)`; bir adım sağa ($C$), sonra sola sonuna dek (yok) → dur. Yol $B \\to C$ (amber), sonuç $C$. **Sağ panel — Durum 2, successor(C):** $C$'nin sağ çocuğu YOK → sola-dal yukarı çık: $C$, $B$'nin sağ çocuğu (devam et), $B$, $D$'nin SOL çocuğu (DUR). Yol $C \\to B \\to D$ (amber, yukarı), sonuç $D$. Sezgi: sağ alt ağaç yoksa, successor node'u sol tarafında bırakan en yakın atadır."
#| fig-width: 10.5
#| fig-height: 6.4
# fig-successor (L6 §6 İMZA): successor'ın iki durumu yan-yana iki panel.
# Veri MOTORDAN (build_example_tree / successor_trace). tr1=B→C (case1),
# tr2=C→B→D (case2). COL_* / plt gizli setup hücresinden.
_SU_R = 0.30
_SU_X_GAP = 1.00
_SU_Y_GAP = 1.15
_SU_INORDER_X = {"A": 0, "B": 1, "C": 2, "D": 3, "E": 4, "F": 5, "G": 6}
_SU_LEVEL = {"D": 0, "B": 1, "F": 1, "A": 2, "C": 2, "E": 2, "G": 2}
def _su_coords(item, x_off, y_top):
x = x_off + _SU_INORDER_X[item] * _SU_X_GAP
y = y_top - _SU_LEVEL[item] * _SU_Y_GAP
return x, y
def _su_draw_tree(ax, root, x_off, y_top, *, fill_item, frame_item,
path_edges, successor_item):
path_set = {tuple(sorted(e)) for e in path_edges}
def walk_edges(node):
for child in (node.left, node.right):
if child is not None:
px, py = _su_coords(node.item, x_off, y_top)
cx, cy = _su_coords(child.item, x_off, y_top)
hot = tuple(sorted((node.item, child.item))) in path_set
ax.plot([px, cx], [py, cy],
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=3.0 if hot else 1.5,
zorder=2 if hot else 1,
solid_capstyle="round")
walk_edges(child)
walk_edges(root)
for (top_item, bot_item) in path_edges:
tx, ty = _su_coords(top_item, x_off, y_top)
bx, by = _su_coords(bot_item, x_off, y_top)
ax.add_patch(FancyArrowPatch(
(tx, ty), (bx, by), arrowstyle="-|>", mutation_scale=18,
color=COL_AMBER_700, linewidth=3.0,
shrinkA=_SU_R * 72 * 0.46, shrinkB=_SU_R * 72 * 0.46, zorder=4))
def walk_nodes(node):
x, y = _su_coords(node.item, x_off, y_top)
if node.item == fill_item:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.8
elif node.item == frame_item:
fc, ec, lw = COL_WHITE, COL_ACCENT, 2.8
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 1.6
ax.add_patch(Circle((x, y), _SU_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
tcol = COL_AMBER_700 if node.item in (fill_item, frame_item) else COL_TEXT
ax.text(x, y, node.item, ha="center", va="center",
fontsize=12.5, color=tcol, weight="bold", zorder=6)
for child in (node.left, node.right):
if child is not None:
walk_nodes(child)
walk_nodes(root)
sx, sy = _su_coords(successor_item, x_off, y_top)
ax.text(sx + _SU_R + 0.16, sy + _SU_R + 0.10, "SUCCESSOR", ha="left",
va="bottom", fontsize=8.5, color=COL_AMBER_700, weight="bold",
zorder=7)
t = build_example_tree()
node_b = t.left # B
node_c = t.left.right # C
assert successor_trace(node_b) == {"case": 1, "path": ["B", "C"], "result": "C"}
assert successor_trace(node_c) == {"case": 2, "path": ["C", "B", "D"], "result": "D"}
fig, ax = plt.subplots(figsize=(10.5, 6.4))
fig.patch.set_facecolor(COL_WHITE)
x_off_left = 0.0
x_off_right = 6 * _SU_X_GAP + 2.6
y_top = 0.0
_su_draw_tree(ax, t, x_off_left, y_top,
fill_item="B", frame_item="C",
path_edges=[("B", "C")], successor_item="C")
cx_l = x_off_left + 3 * _SU_X_GAP
ax.text(cx_l, y_top + 0.95, "Durum 1 — successor(B)",
ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold")
ax.text(cx_l, y_top - 2 * _SU_Y_GAP - 0.55,
"sağ çocuk VAR → subtree_first(node.right)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold")
ax.text(cx_l, y_top - 2 * _SU_Y_GAP - 0.92,
"bir adım sağa (C), sonra sola sonuna dek (yok) → dur",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic")
_su_draw_tree(ax, t, x_off_right, y_top,
fill_item="C", frame_item="D",
path_edges=[("C", "B"), ("B", "D")], successor_item="D")
cx_r = x_off_right + 3 * _SU_X_GAP
ax.text(cx_r, y_top + 0.95, "Durum 2 — successor(C)",
ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold")
ax.text(cx_r, y_top - 2 * _SU_Y_GAP - 0.55,
"sağ çocuk YOK → sola-dal yukarı çık",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold")
ax.text(cx_r, y_top - 2 * _SU_Y_GAP - 0.92,
"C, B'nin sağ çocuğu → çık; B, D'nin sol çocuğu → DUR",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic")
sep_x = (x_off_left + 6 * _SU_X_GAP + x_off_right) * 0.5
ax.plot([sep_x, sep_x], [y_top - 2 * _SU_Y_GAP - 0.4, y_top + 0.7],
color=COL_SLATE_400, linewidth=1.0, linestyle=(0, (3, 3)), zorder=0)
fig.suptitle(
"Traversal successor — iki durum, her ikisi de O(h)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975)
ax.set_xlim(x_off_left - 0.9, x_off_right + 6 * _SU_X_GAP + 0.9)
ax.set_ylim(y_top - 2 * _SU_Y_GAP - 1.25, y_top + 1.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## insert_after {#sec-insert-after}
`insert_after(node, new)`: yeni bir düğümü, traversal sırasında node'dan hemen sonraya ekle. İki durum (her ikisi de successor'a indirgenir, **$O(h)$**):
**Çalışılan Örnek — insert_after.** *Durum 1:* node'un **sağ çocuğu yoksa**, new'i doğrudan `node.right` yap. *Durum 2:* sağ çocuk varsa, node'un successor'ını bul (`subtree_first(node.right)`); bu successor'ın **sol çocuğu olmadığı garantilidir** (çünkü sağa bir kez, sonra sola sonuna dek giderek bulundu). O hâlde new'i successor'ın **sol çocuğu** yap. Yeni traversal sırası: node → new → eski successor → ... Sabit-zaman iş + $O(h)$ successor = **$O(h)$**.
Örnek ağaçta `insert_after(C, X)` Durum 1'dir ($C$.right boş → $X$, $C$.right olur, traversal `...C, X, D...`); `insert_after(D, Y)` Durum 2'dir ($D$.right dolu (F), successor $= E$, $Y$ → $E$.left, traversal `...D, Y, E...`). @fig-insert-after iki durumu yan yana gösterir.
```{python}
#| label: fig-insert-after
#| fig-cap: "insert_after — sabit işaretçi işi + $O(h)$ successor arama $= O(h)$ (L6 §7; örnek ağaç $A..G$). **Sol panel — Durum 1, insert_after(C, X):** $C$.right BOŞ → $X$ (amber yeni düğüm) doğrudan $C$.right olur; yeni traversal $\\dots C, X, D \\dots$ **Sağ panel — Durum 2, insert_after(D, Y):** $D$.right DOLU ($F$) → successor$(D) = $ `subtree_first(D.right)` $= E$ (yol $D \\to F \\to E$, kesikli amber). Bu successor'ın sol çocuğu OLAMAZ (sağa bir kez + sola sonuna dek inilerek bulundu) → $Y$, $E$'nin SOL çocuğu olur; yeni traversal $\\dots D, Y, E \\dots$ İki durumda da yalnız birkaç işaretçi değişir, maliyet successor aramasıyla sınırlı: $O(h)$."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-insert-after (L6 §7): insert_after iki durumu (C.right boş / D.right dolu).
# Veri MOTORDAN (build_example_tree / subtree_insert_after / subtree_first).
# Traversal'lar ASSERT edilir. COL_* / plt gizli setup hücresinden.
_IA_LEVEL_DY = 1.25
_IA_NODE_R = 0.30
_IA_X_STEP = 1.0
def _ia_layout(root):
pos = {}
counter = [0]
def assign(node, depth):
if node is None:
return
assign(node.left, depth + 1)
pos[node] = (counter[0] * _IA_X_STEP, -depth * _IA_LEVEL_DY)
counter[0] += 1
assign(node.right, depth + 1)
assign(root, 0)
return pos
def _ia_draw_edge(ax, p0, p1, *, color, lw, dashed=False, z=1):
x0, y0 = p0
x1, y1 = p1
dx, dy = x1 - x0, y1 - y0
d = math.hypot(dx, dy) or 1.0
ux, uy = dx / d, dy / d
sx, sy = x0 + ux * _IA_NODE_R, y0 + uy * _IA_NODE_R
ex, ey = x1 - ux * _IA_NODE_R, y1 - uy * _IA_NODE_R
ax.plot([sx, ex], [sy, ey], color=color, linewidth=lw,
linestyle=(0, (4, 2)) if dashed else "-", zorder=z,
solid_capstyle="round")
def _ia_draw_node(ax, pos, node, *, new=False, succ=False, z=4):
x, y = pos[node]
if new:
fc, ec, lw, tc = COL_AMBER_300, COL_AMBER_700, 2.6, COL_TEXT
elif succ:
fc, ec, lw, tc = COL_AMBER_100, COL_ACCENT, 2.6, COL_TEXT
else:
fc, ec, lw, tc = COL_BG, COL_PRIMARY, 1.8, COL_TEXT
ax.add_patch(Circle((x, y), _IA_NODE_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=z))
ax.text(x, y, str(node.item), ha="center", va="center",
fontsize=12.5, color=tc, weight="bold", zorder=z + 1)
def _ia_draw_tree(ax, root, *, new_node=None, succ_nodes=None,
succ_path_edges=None, new_edge=None):
succ_nodes = set(succ_nodes or [])
succ_path_edges = set(succ_path_edges or [])
pos = _ia_layout(root)
def walk_edges(node):
if node is None:
return
for child in (node.left, node.right):
if child is not None:
is_new = (new_edge is not None and node is new_edge[0]
and child is new_edge[1])
is_succ = ((node, child) in succ_path_edges
or (child, node) in succ_path_edges)
if is_new:
_ia_draw_edge(ax, pos[node], pos[child],
color=COL_AMBER_700, lw=2.8, z=2)
elif is_succ:
_ia_draw_edge(ax, pos[node], pos[child],
color=COL_ACCENT, lw=2.4, dashed=True, z=3)
else:
_ia_draw_edge(ax, pos[node], pos[child],
color=COL_SLATE_400, lw=1.6, z=1)
walk_edges(child)
walk_edges(root)
def walk_nodes(node):
if node is None:
return
walk_nodes(node.left)
_ia_draw_node(ax, pos, node,
new=(node is new_node), succ=(node in succ_nodes))
walk_nodes(node.right)
walk_nodes(root)
return pos
def _ia_center(pos):
xs = [x for x, _ in pos.values()]
return (min(xs) + max(xs)) / 2.0
def _ia_mini_strip(ax, items, x_center, y, hot_item):
cw = 0.52
x0 = x_center - (len(items) * cw) / 2.0
for k, it in enumerate(items):
x = x0 + k * cw
hot = (it == hot_item)
ax.add_patch(plt.Rectangle(
(x, y), cw * 0.9, 0.42,
facecolor=COL_AMBER_300 if hot else COL_WHITE,
edgecolor=COL_AMBER_700 if hot else COL_SLATE_400,
linewidth=2.0 if hot else 1.2, zorder=3))
ax.text(x + cw * 0.45, y + 0.21, str(it), ha="center", va="center",
fontsize=9.5, color=COL_TEXT,
weight="bold" if hot else "normal", zorder=4)
# --- Motor: Durum 1 (insert_after(C, X)) ---
t1 = build_example_tree()
c_node = t1.left.right
assert c_node.item == "C" and c_node.right is None
x_node = BTNode("X")
subtree_insert_after(c_node, x_node)
assert tree_traversal(t1) == ["A", "B", "C", "X", "D", "E", "F", "G"]
# --- Motor: Durum 2 (insert_after(D, Y)) ---
t2 = build_example_tree()
subtree_insert_after(t2.left.right, BTNode("X")) # X mevcut (Durum 1 sonrası)
d_node = t2
succ_before = subtree_first(d_node.right)
assert succ_before.item == "E" and succ_before.left is None
f_node = d_node.right
e_node = f_node.left
y_node = BTNode("Y")
subtree_insert_after(d_node, y_node)
assert tree_traversal(t2) == ["A", "B", "C", "X", "D", "Y", "E", "F", "G"]
fig, (axL, axR) = plt.subplots(1, 2, figsize=(11, 7))
fig.patch.set_facecolor(COL_WHITE)
for ax in (axL, axR):
ax.set_aspect("equal")
ax.axis("off")
posL = _ia_draw_tree(axL, t1, new_node=x_node, new_edge=(c_node, x_node))
axL.text(_ia_center(posL), 0.95, "Durum 1 — insert_after(C, X)",
ha="center", va="center", fontsize=12, color=COL_TEXT, weight="bold")
axL.text(_ia_center(posL), 0.45, "C.right BOŞ → X doğrudan C.right",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold")
y_strip_L = min(y for _, y in posL.values()) - 0.95
_ia_mini_strip(axL, ["C", "X", "D"], _ia_center(posL), y_strip_L, hot_item="X")
axL.text(_ia_center(posL), y_strip_L - 0.30, "traversal: ... C X D ...",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic")
posR = _ia_draw_tree(axR, t2, new_node=y_node, succ_nodes=[e_node],
succ_path_edges=[(d_node, f_node), (f_node, e_node)],
new_edge=(e_node, y_node))
axR.text(_ia_center(posR), 0.95, "Durum 2 — insert_after(D, Y)",
ha="center", va="center", fontsize=12, color=COL_TEXT, weight="bold")
axR.text(_ia_center(posR), 0.45, "D.right DOLU → successor(D)=E → Y, E.left",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold")
axR.text(posR[f_node][0] + 0.45, posR[f_node][1] + 0.05,
"successor:\nD → F → E", ha="left", va="center",
fontsize=8.5, color=COL_ACCENT, weight="bold")
y_note = min(y for _, y in posR.values()) - 0.55
axR.text(_ia_center(posR), y_note,
"successor'ın sol çocuğu OLAMAZ → E.left yeri garantili",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic")
y_strip_R = y_note - 0.50
_ia_mini_strip(axR, ["D", "Y", "E"], _ia_center(posR), y_strip_R, hot_item="Y")
axR.text(_ia_center(posR), y_strip_R - 0.30, "traversal: ... D Y E ...",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic")
for ax, pos in ((axL, posL), (axR, posR)):
xs = [x for x, _ in pos.values()]
ys = [y for _, y in pos.values()]
ax.set_xlim(min(xs) - 1.0, max(xs) + 1.6)
ax.set_ylim(min(ys) - 1.9, max(ys) + 1.5)
fig.suptitle(
"insert_after: sabit işaretçi işi + O(h) successor arama = O(h)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.97)
plt.tight_layout(rect=(0, 0, 1, 0.94))
plt.show()
```
## delete {#sec-delete}
`delete(node)`: bir düğümü traversal sırasından çıkar. Düğüm bir **yaprak** ise basitçe parent'tan kopar (taban durum). Değilse, düğümü ağaçta **aşağı taşıyarak** yaprağa indirip silmek için takas yapılır:
- **Sol çocuk varsa:** predecessor (sıralamada önceki) sol alt ağaçtadır (daha aşağıda). node'un **item'ını predecessor'ın item'ıyla takas et**, sonra predecessor'ı **özyinelemeli sil**.
- **Sağ çocuk varsa (sol yoksa):** simetrik — successor ile takas et, successor'ı sil.
Her takasta düğüm bir seviye aşağı iner; toplam iş ağaç yüksekliğiyle orantılı → **$O(h)$**. (Burada ilk kez düğümlerin *içeriğini* değiştiriyoruz, düğümün kendisini değil.)
> *"trees will not preserve connections — that's just the name of the game."* — Demaine, 47:02
@fig-delete-swap somut bir örnekte (`build_bst([16,8,24,4,12,2,6,10,14,13])`, kök 16'yı sil) bu takas zincirini üç kare hâlinde gösterir: $16 \leftrightarrow 14$, sonra $16 \leftrightarrow 13$, sonra yaprakta kopar; son traversal $[2,4,6,8,10,12,13,14,24]$.
```{python}
#| label: fig-delete-swap
#| fig-cap: "İç düğüm silme = item TAKASI zinciri (L6 §8, **İMZA** figür; `build_bst([16,8,24,4,12,2,6,10,14,13])`, $h = 4$, kök $16$ silinir). Düğüm DAİRELERİ yapısal konumda sabit kalır; yalnız İÇERİK aşağı iner (Demaine 47:02). **Kare 1:** $16$ (kök) amber dolgu \"SİL\"; predecessor yolu $16 \\to 8 \\to 12 \\to 14$ (kesikli amber); çift-başlı takas oku $16 \\leftrightarrow 14$. **Kare 2:** $14$ köke çıktı, $16$ bir seviye indi ($14$'ün eski yeri); $16$'nın sol çocuğu $13$ ile ikinci takas $16 \\leftrightarrow 13$. **Kare 3:** $16$ artık yaprakta → parent'tan koparılır (✕). Altta son in-order şeridi $[2,4,6,8,10,12,13,14,24]$ ($16$ yok ✓). Her takas item'ı bir seviye indirir → toplam $\\le h = 4$ takas $= O(h)$."
#| fig-width: 10.0
#| fig-height: 6.9
# fig-delete-swap (L6 §8 İMZA): iç düğüm silme = item takası zinciri, 3 kare.
# Veri MOTORDAN (build_bst / delete_trace / tree_traversal / node_height).
# swaps == [(16,14),(16,13)], traversal_after == [2,4,6,8,10,12,13,14,24], h==4.
_DS_KEYS = [16, 8, 24, 4, 12, 2, 6, 10, 14, 13]
_DS_INORDER = [2, 4, 6, 8, 10, 12, 13, 14, 16, 24]
_DS_XPOS = {v: i for i, v in enumerate(_DS_INORDER)}
_DS_DEPTH = {
16: 0, 8: 1, 24: 1, 4: 2, 12: 2, 2: 3, 6: 3, 10: 3, 14: 3, 13: 4,
}
_DS_PARENT = {
8: 16, 24: 16, 4: 8, 12: 8, 2: 4, 6: 4, 10: 12, 14: 12, 13: 14,
}
_DS_X_SCALE = 0.92
_DS_Y_SCALE = 1.05
_DS_R = 0.30
def _ds_node_xy(item):
return _DS_XPOS[item] * _DS_X_SCALE, -_DS_DEPTH[item] * _DS_Y_SCALE
def _ds_draw_tree(ax, contents, y_off, *,
amber_fill=None, dashed_path=None, leaf_cut=None):
amber_fill = set(amber_fill or [])
dashed_path = list(dashed_path or [])
for child, parent in _DS_PARENT.items():
cx, cy = _ds_node_xy(child)
px, py = _ds_node_xy(parent)
cut = (leaf_cut is not None and child == leaf_cut)
ax.plot([px, cx], [py + y_off, cy + y_off],
color=COL_AMBER_700 if cut else COL_SLATE_400,
linewidth=1.8 if cut else 1.6,
linestyle=(0, (4, 3)) if cut else "-", zorder=1)
for a, b in zip(dashed_path, dashed_path[1:]):
ax_, ay_ = _ds_node_xy(a)
bx_, by_ = _ds_node_xy(b)
ax.plot([ax_, bx_], [ay_ + y_off, by_ + y_off],
color=COL_ACCENT, linewidth=2.6, linestyle=(0, (2, 1.6)),
zorder=2)
for pos_item in _DS_DEPTH:
x, y = _ds_node_xy(pos_item)
y += y_off
shown = contents.get(pos_item, pos_item)
is_fill = pos_item in amber_fill
is_cut = (leaf_cut is not None and pos_item == leaf_cut)
if is_fill:
fc, ec, lw, tcol = COL_ACCENT, COL_AMBER_700, 2.6, COL_WHITE
elif is_cut:
fc, ec, lw, tcol = COL_AMBER_100, COL_AMBER_700, 2.4, COL_AMBER_700
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.7, COL_TEXT
circ = Circle((x, y), _DS_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=4)
if is_cut:
circ.set_linestyle((0, (3, 2)))
ax.add_patch(circ)
ax.text(x, y, str(shown), ha="center", va="center",
fontsize=10.5, color=tcol, weight="bold", zorder=6)
if is_cut:
d = _DS_R * 0.62
for (dx0, dy0, dx1, dy1) in ((-d, -d, d, d), (-d, d, d, -d)):
ax.plot([x + dx0, x + dx1], [y + dy0, y + dy1],
color=COL_AMBER_700, linewidth=2.2, zorder=7)
def _ds_swap_arrow(ax, top_item, bot_item, y_off, label):
tx, ty = _ds_node_xy(top_item)
bx, by = _ds_node_xy(bot_item)
ty += y_off
by += y_off
ax.add_patch(FancyArrowPatch(
(tx, ty), (bx, by), arrowstyle="<|-|>", mutation_scale=15,
color=COL_ACCENT, linewidth=2.6, zorder=8,
shrinkA=_DS_R * 30, shrinkB=_DS_R * 30,
connectionstyle="arc3,rad=0.22"))
mx, my = (tx + bx) * 0.5, (ty + by) * 0.5
ax.text(mx + 0.42, my, label, ha="left", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=9)
def _ds_panel_title(ax, x, y_off, text, sub=None):
top_y = y_off + 0.62
ax.text(x, top_y, text, ha="left", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=10)
if sub is not None:
ax.text(x, top_y - 0.40, sub, ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=10)
tr = delete_trace(build_bst(_DS_KEYS), 16)
assert tr["swaps"] == [(16, 14), (16, 13)]
assert tr["traversal_after"] == [2, 4, 6, 8, 10, 12, 13, 14, 24]
traversal_after = tr["traversal_after"]
pre = build_bst(_DS_KEYS)
assert tree_traversal(pre) == [2, 4, 6, 8, 10, 12, 13, 14, 16, 24]
h = node_height(pre)
assert h == 4
fig, ax = plt.subplots(figsize=(10.0, 6.9))
fig.patch.set_facecolor(COL_WHITE)
OFF1, OFF2, OFF3 = 0.0, -6.0, -12.0
panel_x_left = -1.0
_ds_draw_tree(ax, {}, OFF1, amber_fill={16}, dashed_path=[16, 8, 12, 14])
_ds_swap_arrow(ax, 16, 14, OFF1, "takas ① 16 ↔ 14")
_ds_panel_title(ax, panel_x_left, OFF1, "Kare 1 — sil(16): iç düğüm",
sub="predecessor yolu 16→8→12→14 (kesikli) · item bir seviye iner")
kx, ky = _ds_node_xy(16)
ax.text(kx, ky + OFF1 + _DS_R + 0.30, "SİL", ha="center", va="bottom",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=10)
_ds_draw_tree(ax, {16: 14, 14: 16}, OFF2, amber_fill={14}, dashed_path=[14, 13])
_ds_swap_arrow(ax, 14, 13, OFF2, "takas ② 16 ↔ 13")
_ds_panel_title(ax, panel_x_left, OFF2, "Kare 2 — 16 bir seviye indi",
sub="14 köke çıktı · 16 (14'ün eski yeri) sol çocuk 13 ile takas")
px, py = _ds_node_xy(14)
ax.text(px + _DS_R + 0.18, py + OFF2, "16", ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=10)
_ds_draw_tree(ax, {16: 14, 14: 13, 13: 16}, OFF3, leaf_cut=13)
_ds_panel_title(ax, panel_x_left, OFF3, "Kare 3 — 16 yaprağa indi → kopar",
sub="taban durum: yaprak parent'tan koparılır (✕)")
lx, ly = _ds_node_xy(13)
ax.text(lx + _DS_R + 0.18, ly + OFF3, "16 (yaprak)", ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=10)
strip_y = OFF3 - 5 * _DS_Y_SCALE - 0.05
sw = 0.74
for k, v in enumerate(traversal_after):
x = k * sw
ax.add_patch(plt.Rectangle(
(x, strip_y), sw * 0.9, 0.58,
facecolor=COL_BG, edgecolor=COL_PRIMARY, linewidth=1.5, zorder=3))
ax.text(x + sw * 0.45, strip_y + 0.29, str(v), ha="center", va="center",
fontsize=10, color=COL_TEXT, weight="bold", zorder=5)
ax.text(-0.22, strip_y + 0.29, "in-order", ha="right", va="center",
fontsize=9, color=COL_TEXT, weight="bold", zorder=5)
ax.text(len(traversal_after) * sw + 0.10, strip_y + 0.29,
"16 yok ✓", ha="left", va="center", fontsize=9.5,
color=COL_AMBER_700, weight="bold", zorder=5)
fig.suptitle(
"İç düğüm silme = item TAKASI zinciri: düğüm daireleri yerinde, "
"yalnız İÇERİK iner",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ax.text(panel_x_left, strip_y - 0.62,
f"her takas item'ı BİR seviye indirir → toplam ≤ h={h} takas = O(h) "
"· düğüm kendileri değil, içerikleri değişir (Demaine 47:02)",
ha="left", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=10)
max_x = (len(_DS_INORDER) - 1) * _DS_X_SCALE
ax.set_xlim(panel_x_left - 0.7, max_x + 3.2)
ax.set_ylim(strip_y - 1.1, OFF1 + 1.25)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-tip title="Builder Notu — İşaretçi Cerrahisi ve Korunan Değişmez"}
delete, ağaç işlemlerinin ortak iskeletini açığa çıkarır: her işlem birkaç işaretçiyi keser/bağlar, ve doğruluğu **korunan bir değişmezle (invariant)** kanıtlanır.
- **Parent-child invariant:** Her düğümde `node.left.parent is node` (ve right için). insert_after yeni bir bağ kurarken bu değişmezi *hem yukarı hem aşağı* tamamlamalı (`new.parent = ...` unutulursa successor yukarı-yürüyüşü kırılır). delete'te item takası bu değişmezi hiç bozmaz — çünkü daireler yerinde kalır, yalnız içerik değişir; bu yüzden takas "güvenli" bir tekniktir.
- **Her işlem bir ispat:** subtree_first/successor/insert_after/delete doğruluğu, "traversal sırası korunur" + "parent-child tutarlı" değişmezlerinin her adımda sağlandığını göstermekle ispatlanır. Bir builder için ders: işaretçi koduna güven, ispatla gelir — testte bu iki değişmezi assert et (`tree_traversal == beklenen`, `check_parent_child`).
- **Genel ilke:** Bağlı yapılarda (linked list, ağaç, graf) her mutasyon bir "cerrahi"dir; bug'lar neredeyse her zaman yarım kalmış bir bağ (dangling/half-updated pointer) yüzündendir. Değişmezi yaz, her işlemden sonra kontrol et.
Tek cümle: *İşaretçi cerrahisinin güvenliği, her kesimden sonra aynı değişmezi geri kurmaktan gelir — ağaç kodunun doğruluğu, hız değil, değişmez disiplinidir.*
:::
## Sequence ve Set Olarak Ağaç {#sec-sequence-set}
Aynı ağaç iki arayüzü de gerçekleştirir, yalnızca traversal sırasının *anlamı* değişir:
- **Dizi (sequence):** traversal sırası = sequence sırası ($x_0, x_1, \dots, x_{n-1}$).
- **Küme (set):** traversal sırası = **artan anahtar sırası**.
Set durumunda **BST özelliği (binary search tree property)** doğar: her düğümde, sol alt ağacın tüm anahtarları $<$ düğüm $<$ sağ alt ağacın tüm anahtarları.
> *"this is something called the binary search tree property, BST property."* — Demaine, 49:11
**find(k):** kökten başla, $k$'yı düğümle karşılaştır; küçükse sola, büyükse sağa in — ikili aramanın ağaç hâli, $O(h)$. **find_prev/find_next:** ağaçtan düşersen ($k$ yoksa), son denenen yön sana önceki ya da sonrakini verir; diğerini predecessor/successor ile bulursun. (Diziyi tam gerçekleştirmek biraz daha iş ister — sonraki ders.)
::: {.callout-tip title="Builder Notu — BST = Dinamik İkili Arama (B-tree/SQL İndeksin Atası)"}
BST özelliği, Ders 4'teki sıralı dizi ikili aramasını *dinamik* hâle getirir: arama hâlâ $O(h)$, ama artık ekleme/silme de $O(h)$ — kaydırma yok.
- **Dinamik ikili arama:** Sıralı dizi find'i $O(\log n)$ yapar ama insert/delete $O(n)$ (kaydırma). BST, find + find_prev/next + insert + delete'in *hepsini* $O(h)$ yapar; $h = O(\log n)$ sağlanırsa (Ders 10), sıralı dizinin tüm avantajı + dinamiklik elde edilir.
- **B-tree / B+-tree = disk-dostu genelleme:** Her düğümde 2 değil $B$ çocuk tutarak ağaç sığlaşır ($h \approx \log_B n$); bu, bir disk bloğu = bir düğüm eşlemesiyle disk erişimini minimize eder. PostgreSQL, MySQL InnoDB, SQLite — hepsinin varsayılan indeksi bir B+-tree'dir; "varsayılan SQL indeksi bir dengeli ağaçtır" sözünün kökü budur (hash/GIN gibi özel indeks türleri ayrı uzmanlıklardır).
- **find_prev/find_next = en yakın komşu:** Hash tablosunun yapamadığı "en yakın daha büyük/küçük anahtar" sorgusu (range query, `BETWEEN`, autocomplete) ağacın doğal yaptığı şeydir — bu yüzden veritabanı sıralı taramaları hash değil ağaç indeksi ister.
Tek cümle: *BST, ikili aramayı statik diziden kurtarıp dinamik yapar; B-tree onu diske taşır — modern her veritabanı indeksinin atası bu derstir.*
:::
## Bu Dersin Özeti {#sec-ozet-d09}
1. **İkili ağaç**: düğüm (item + `parent`/`left`/`right`); kök parent'sız, yaprak çocuksuz.
2. **İki işaretçi** (left/right) logaritmik yükseklik sağlar; bağlı listenin lineer derinliğini aşar.
3. **Derinlik** (köke kenar) ve **yükseklik** (en derin yaprağa kenar); ağacın yüksekliği $h$.
4. **Traversal sırası** (in-order): sol → düğüm → sağ; örtük, asla diziye yazılmaz.
5. **subtree_first / successor / insert_after / delete**: hepsi **$O(h)$**.
6. **Sequence**: traversal = sıra; **Set**: traversal = artan anahtar (BST özelliği).
7. **find / find_prev / find_next**: BST'de ikili arama, $O(h)$.
::: {.callout-important title="Tek Bir Cümle"}
İkili ağaç, sıralı bir düzeni örtük traversal sırasıyla temsil eder ve tüm işlemleri ağaç yüksekliği $h$ ile sınırlar; geriye tek soru kalır — $h$'yi nasıl küçük ($\log n$) tutarız?
:::
## Kontrol Soruları {#sec-sorular-d09}
::: {.callout-note collapse="true" title="Soru 1: Traversal (geziş) sırası neden açıkça bir dizide tutulmaz?"}
**Cevap:**
Traversal sırasını bir dizide tutmak, ortaya ekleme/silmede tüm öğeleri kaydırmayı gerektirir → $O(n)$. İkili ağacın tüm amacı bu düzeni *örtük* (işaretçilerle) tutmaktır; böylece insert_after, delete gibi işlemler yalnızca birkaç işaretçi değiştirerek $O(h)$ zamanda düzeni günceller. Sıra "kafadadır"; bilgisayarda yalnızca düğümler ve işaretçiler saklanır.
:::
::: {.callout-note collapse="true" title="Soru 2: successor'da neden iki durum var? Her birinde nereye bakılır?"}
**Cevap:**
*Durum 1 — sağ çocuk var:* node'dan sonra gelen her şey sağ alt ağaçtadır; bunların ilki (en solu) successor'dır → `subtree_first(node.right)`. *Durum 2 — sağ çocuk yok:* node'dan sonra gelecek hiçbir şey altında değil; sola-dal yukarı çıkıp, node'u sol tarafında bırakan en yakın atayı buluruz (o atanın sol alt ağacı node'u içerir, kendisi sonra gelir). İkisi de $O(h)$.
:::
::: {.callout-note collapse="true" title="Soru 3: delete'te neden item takası yapılır, düğüm doğrudan silinmez?"}
**Cevap:**
Yaprak olmayan bir düğümü doğrudan silmek ağacı koparır (çocuklarına giden işaretçiler boşa düşer). Bunun yerine, düğümün item'ını predecessor/successor'ın item'ıyla takas ederiz; bu, "silinecek" item'ı ağaçta bir seviye aşağı taşır. Tekrarlayarak item bir yaprağa iner ve yaprak güvenle silinir. Düğüm daireleri yerinde kalır, yalnızca içerikleri değişir; toplam iş $O(h)$.
:::
::: {.callout-note collapse="true" title="Soru 4: Bir kümeyi sıralı dizi yerine ikili ağaçla tutmanın kazancı nedir?"}
**Cevap:**
Sıralı dizi find'i $O(\log n)$ (ikili arama) yapar ama insert/delete $O(n)$'dir (kaydırma). İkili ağaç (BST), find'i ve find_prev/next'i $O(h)$ yapar *ve* insert/delete'i de $O(h)$'de tutar — düzeni kaydırma olmadan, işaretçilerle günceller. $h = O(\log n)$ sağlanırsa (sonraki ders), tüm işlemler $O(\log n)$ olur; sıralı dizinin statik kısıtı kalkar.
:::
## Egzersizler {#sec-egzersizler-d09}
**Egzersiz 1.** Verilen bir ikili ağaç için traversal (in-order) sırasını elle çıkar; sonra `subtree_first(kök)` ve `successor` ile baştan sona dolaşarak aynı sırayı yeniden üret.
**Egzersiz 2.** `subtree_last` ve `predecessor` işlemlerini, `subtree_first`/`successor`'ın simetriği olarak tanımla (sağ ↔ sol).
**Egzersiz 3.** insert_after Durum 2'de, successor'ın neden sol çocuğu olamayacağını tek cümlede ispatla (`subtree_first`'in tanımına dayan).
**Egzersiz 4.** Python'da bir BST düğüm sınıfı yaz ve `find(k)` ile `find_next(k)`'yi gerçekleştir:
```python
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = self.parent = None
def find(node, k):
while node and node.key != k:
node = node.left if k < node.key else node.right
return node
```
**Egzersiz 5.** delete'te, hem sol hem sağ çocuğu olan bir düğüm için neden "tek bir durum" (sadece sol VEYA sadece sağ) yeterli olur? Demaine'in "iki durumdan biri beni mutlu eder" gözlemini açıkla.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-d09}
**Ders 10 (L7): İkili Ağaçlar — Bölüm 2**
Erik Demaine ile, bugün açık bıraktığımız soruyu kapatıyoruz: ağacın yüksekliği $h$'yi **$O(\log n)$** olmaya nasıl zorlarız? **AVL ağaçları** (dengeli ikili ağaçlar) ve **rotasyon** işlemiyle, tüm $O(h)$ işlemleri $O(\log n)$ garantisine çeviriyoruz. (Not: ders akışında araya **Problem Oturumu 4** girer.)
::: {.callout-warning title="Ders 10 Öncesi Yapılacak"}
- Bu dersin egzersizlerini, özellikle **Egzersiz 4**'ü (BST find) çöz.
- **Dört $O(h)$ işlemini** (subtree_first, successor, insert_after, delete) ezberden anlat.
- Ana cümleyi tekrar oku: *"Geriye tek soru kalır — $h$'yi nasıl küçük tutarız?"*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d09}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **İkili ağaç (düğüm)** | item + parent/left/right; kök parent'sız, yaprak çocuksuz | Böl. 2 |
| **Derinlik / yükseklik** | Köke kenar / en derin yaprağa kenar; ağaç yüksekliği $h$ | Böl. 4 |
| **Traversal sırası** | In-order: sol → düğüm → sağ; örtük | Böl. 5 |
| **subtree_first** | Alt ağacın ilki; sola git; $O(h)$ | Böl. 6 |
| **successor** | Sıradaki düğüm; sağ varsa subtree_first, yoksa sola-dal yukarı; $O(h)$ | Böl. 6 |
| **insert_after** | Sağ yoksa `node.right`; varsa successor'ın sol çocuğu; $O(h)$ | Böl. 7 |
| **delete** | Yaprak→kopar; değilse pred/succ item takası + özyinele; $O(h)$ | Böl. 8 |
| **BST özelliği** | sol anahtarlar $<$ düğüm $<$ sağ anahtarlar; find $O(h)$ | Böl. 9 |
## Builder ve OMSCS Bağlantıları {#sec-baglantilar-d09}
::: {.callout-tip title="6 köprü"}
Bu ders, "sıralı düzeni nasıl ucuza dinamik tutarız" sezgisini kurar — köprülerin özeti:
1. **BST / dengeli ağaç** → veritabanı indeksleri (B-tree, B+-tree): varsayılan SQL indeksi ve dosya sistemi dizinleri bu fikrin disk-dostu hâli.
2. **Traversal sırası** → sıralı yineleme: bir set'i sıralı gezmek (range query, `BETWEEN`) ağaçta doğal $O(n)$ traversal.
3. **find_prev / find_next** → "en yakın komşu" sorguları: hash tablosunun yapamadığı, ağacın doğal yaptığı şey.
4. **$O(h) \to O(\log n)$** → denge disiplini: bir veri yapısının garantisi, en kötü durum yüksekliğini sınırlamaya bağlıdır (sonraki ders).
5. **İşaretçi manipülasyonu + invariant** → her ağaç işleminin doğruluğu, korunan bir değişmezle (BST özelliği, parent-child tutarlılığı) ispatlanır.
6. **Örtük düzen** → genel ilke: pahalı bir gösterimi (sıralı dizi) açıkça tutmak yerine, ucuz güncellenebilir bir yapıyla (ağaç) örtük temsil etmek.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
İkili ağaç, "sıralı dizi gibi hızlı ara ama bağlı liste gibi esnek değiştir" hayalini gerçekleştirir — düzeni işaretçilerle örtük tutarak. Tüm işlemler $O(h)$'dir; tek görev, $h$'yi $O(\log n)$'de tutmak (bir sonraki ders: AVL).
:::
