---
title: "İkili Ağaçlar — Bölüm 2: AVL"
subtitle: "Dizi ağaçları (subtree_at, size), alt ağaç zenginleştirme (O(1) güncelleme kuralı), rotasyon (traversal sırası korunur), AVL skew ∈ {−1, 0, +1} ve Nₕ Fibonacci-benzeri üstel büyüme → h ≤ 2 log n garantisi"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Demaine'in videosu:** [YouTube — Lecture 7: Binary Trees, Part 2: AVL](https://www.youtube.com/watch?v=U1JYwHcFfso) (≈54 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 7: Binary Trees, Part 2: AVL](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-7-binary-trees-part-2-avl/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 10 (L7)
- **Hoca:** Erik Demaine
- **Okuma süresi:** ≈26 dk
:::
## Bu Derste Ne Var? {#sec-bu-derste-d10}
Ders 9 (L6) ikili ağaçları kurdu: tüm işlemler **$O(h)$** ($h$ = yükseklik). Açık kalan tek soru vardı — $h$'yi nasıl küçük tutarız? Bu ders onu kapatır: **AVL ağaçları** ve **rotasyon** ile $h = O(\log n)$ garanti edilir, böylece tüm $O(h)$ işlemler **$O(\log n)$** olur.
Üç temel kavram bu derste yan yana gelir:
1. **Dizi ağaçları + alt ağaç zenginleştirme** — `size` alanıyla $i$. öğeye $O(h)$'de erişim (subtree_at).
2. **Rotasyon** — traversal sırasını bozmadan ağacı yeniden dengeleyen araç.
3. **AVL / yükseklik dengesi** — her düğümde skew $\in \{-1, 0, +1\}$; bu, $h \le 2 \log n$'i garanti eder.
> *"the goal of today is to take all of these operations that run in order h time and get them to run in order log n time."* — Demaine, 3:05
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 10'un (L7) kavram haritası: hedef, dünkü O(h) işlemleri O(log n)'e indirmek. İki köprü ekleniyor — (1) dizi ağacında subtree_at, her düğümdeki size alanıyla boyut-temelli ikili arama yapar; size ise alt ağaç zenginleştirme kuralından (node.size = sol + sağ + 1, O(1) güncelleme) gelir. (2) rotasyon, traversal sırasını (A, X, B, Y, C) ASLA bozmadan derinlikleri değiştirir → yeniden dengeleme aracı. AVL kuralı bunu skew ∈ {−1, 0, +1} ile sabitler; en az dengeli AVL'nin düğüm sayısı Nₕ Fibonacci-benzeri (üstel) olduğundan yükseklik h ≤ 2 log n çıkar. Sonuç: her sequence/set işlemi O(log n)."
flowchart TD
A["Ders 10 (L7): İkili Ağaçlar — Bölüm 2: AVL"] --> G["Hedef: O(h) işlemleri<br/>O(log n)'e indir"]
G --> SA["subtree_at<br/>i. öğeye boyut-temelli arama"]
SA --> SZ["size alanı<br/>her düğümde alt ağaç boyutu"]
SZ --> AU["Augmentation kuralı<br/>size = sol + sağ + 1 (O(1))"]
G --> RO["Rotasyon<br/>sıra korunur (A, X, B, Y, C)"]
RO --> RO1["derinlikler değişir<br/>yeniden dengeleme aracı"]
AU --> AV["AVL kuralı<br/>skew −1, 0 veya +1"]
RO --> AV
AV --> HB["En az dengeli AVL: Nₕ Fibonacci-benzeri<br/>üstel düğüm sayısı"]
HB --> RES["h en çok 2 log n<br/>tüm işlemler O(log n)"]
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 goal fill:#fde68a,stroke:#b45309,stroke-width:2.5px,color:#1f2937
class A root
class SA,RO,AV,HB branch
class SZ,AU,RO1,RES leaf
class G,RES goal
```
::: {.callout-tip title="Builder Notu — Denge = Garanti Mühendisliği"}
İkili ağaç tek başına $O(h)$'dir; bugün yapılan tek şey, o $h$'ye bir **üst sınır garantisi** eklemek — yapıyı yeniden kurmadan, sadece dengeleyerek.
- **Geriye → Ders 3 (ikili arama):** BST'deki find, sıralı dizideki ikili aramanın ağaç hâlidir — ama artık *dinamik* (insert/delete $O(\log n)$).
- **Geriye → Ders 9 (L6):** bugün, dünkü $O(h)$ işlemlerin üstüne yalnızca denge ekliyoruz; alt yapı (düğüm, traversal, successor) aynı.
- **İleriye → veritabanı:** B-tree / B+-tree, dengeli ağacın disk-dostu hâlidir; çoğu SQL indeksi ve dosya sistemi dizini bu fikre dayanır (varsayılan indeks tipik olarak bir dengeli ağaçtır).
- **İleriye → order-statistics tree:** `size` zenginleştirmesi, "rank" ve "$k$. en küçük" sorgularını $O(\log n)$'de yapar — sıralama istatistikleri.
Tek cümle: *İkili ağaca `size`/`height` gibi alt ağaç özellikleri ekleyip rotasyonla yükseklik dengesi (AVL) tutarsak, her işlem $O(\log n)$ olur — dengeli ağacın tüm gücü budur.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 10 (L7) AVL motoru (_engine.py D10 bölümü + D9 successor/
# predecessor) + Slate+Amber viz (_viz.py COL_* + apply_style). Bu hücre gizlidir
# (#| echo: false). Aşağıdaki TÜM figür hücreleri bu hücrede tanımlanan
# AVLNode / update_node / skew / right_rotate / left_rotate / rebalance_node /
# avl_insert / build_avl / subtree_at / subtree_at_trace / avl_to_list /
# check_avl_invariants / fib_tree_min_nodes / build_fibonacci_tree /
# build_case3_tree + successor/predecessor + COL_* + apply_style'ı IMPORT
# ETMEDEN kullanır.
#
# Notion'daki öğretim içeriği (görünür update() ```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 D10 gerekenler + D9 successor/predecessor gömülür (D1-D7 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) + apply_style
# ---------------------------------------------------------------------------
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"
def apply_style(ax):
"""Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için)."""
ax.set_facecolor(COL_WHITE)
ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8)
for spine in ax.spines.values():
spine.set_color(COL_SLATE_400)
ax.tick_params(colors=COL_TEXT)
ax.title.set_color(COL_TEXT)
ax.xaxis.label.set_color(COL_TEXT)
ax.yaxis.label.set_color(COL_TEXT)
return ax
# ---------------------------------------------------------------------------
# _engine.py D9 (L6) — successor/predecessor (avl_delete bunları kullanır)
# AVLNode da aynı parent/left/right alanlarını taşıdığından D9 yürüyüşleri çalışır.
# ---------------------------------------------------------------------------
def subtree_first(node):
"""Alt ağacın traversal sırasındaki İLK düğümü: sola gidebildiğin kadar git."""
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)."""
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
# ---------------------------------------------------------------------------
# _engine.py D10 (L7) — AVL: augmentation, rotasyon, denge
# ---------------------------------------------------------------------------
class AVLNode:
"""AVL düğümü (L7): BTNode + iki alt ağaç özelliği (height, size).
height = 1 + max(çocuk yükseklikleri) (boş çocuk = −1) [Demaine 43:33]
size = sol.size + sağ.size + 1 [Demaine 17:43]
"""
__slots__ = ("item", "left", "right", "parent", "height", "size")
def __init__(self, item):
self.item = item
self.left = None
self.right = None
self.parent = None
self.height = 0
self.size = 1
def __repr__(self):
return f"AVLNode({self.item!r}, h={self.height}, s={self.size})"
def _h(node):
"""Boş alt ağaç yüksekliği −1 konvansiyonu (yaprak = 0)."""
return node.height if node is not None else -1
def _s(node):
"""Boş alt ağaç boyutu 0."""
return node.size if node is not None else 0
def update_node(node):
"""Güncelleme kuralı (L7 §4/§9, O(1)): çocuklardan height + size."""
node.height = 1 + max(_h(node.left), _h(node.right))
node.size = 1 + _s(node.left) + _s(node.right)
def skew(node):
"""skew(node) = height(sağ) − height(sol) (L7 §7; işaret Notion konvansiyonu)."""
return _h(node.right) - _h(node.left)
def _replace_child(parent, old, new):
"""parent'ın old çocuğunu new ile değiştir (new None olabilir)."""
if parent is not None:
if parent.left is old:
parent.left = new
else:
parent.right = new
if new is not None:
new.parent = parent
def right_rotate(y):
"""right_rotate(y) (L7 §6): x = y.left yukarı, y aşağı; B = x.right, y'nin
soluna geçer. Traversal A,X,B,Y,C AYNEN korunur. O(1) + augmentation.
Döndürür: alt ağacın yeni kökü x."""
x = y.left
_replace_child(y.parent, y, x)
b = x.right
y.left = b
if b is not None:
b.parent = y
x.right = y
y.parent = x
update_node(y) # önce alçalan, sonra yükselen
update_node(x)
return x
def left_rotate(x):
"""Simetrik: y = x.right yukarı, x aşağı; B = y.left, x'in sağına geçer."""
y = x.right
_replace_child(x.parent, x, y)
b = y.left
x.right = b
if b is not None:
b.parent = x
y.left = x
x.parent = y
update_node(x)
update_node(y)
return y
def rebalance_node(x):
"""skew(x) = ±2 olan düğümü onar (L7 §10). Döndürür: yeni alt-kök.
skew(x) = +2 (sağa ağır), y = x.right:
Durum 1-2 — skew(y) ∈ {+1, 0}: tek left_rotate(x).
Durum 3 — skew(y) = −1: önce right_rotate(y), sonra left_rotate(x).
skew(x) = −2 simetrik.
"""
if skew(x) == 2:
y = x.right
if skew(y) < 0: # Durum 3
right_rotate(y)
return left_rotate(x)
if skew(x) == -2:
y = x.left
if skew(y) > 0: # Durum 3 (simetrik)
left_rotate(y)
return right_rotate(x)
return x
def maintain_up(node):
"""Yaprak değişiminden köke: her atada güncelleme kuralı + gerekirse
rebalance (L7 §10). O(h) = O(log n). Döndürür: (yeni) kök."""
last = node
while node is not None:
update_node(node)
if abs(skew(node)) == 2:
node = rebalance_node(node)
last = node
node = node.parent
return last
def avl_insert(root, k):
"""Set-AVL insert: BST inişiyle yaprak ekle + ata yolunda maintain_up.
Döndürür: yeni kök. O(log n)."""
new = AVLNode(k)
if root is None:
return new
node = root
while True:
if k < node.item:
if node.left is None:
node.left = new
new.parent = node
break
node = node.left
else:
if node.right is None:
node.right = new
new.parent = node
break
node = node.right
return maintain_up(new)
def build_avl(keys):
"""Anahtar listesinden (sırayla avl_insert) AVL kur — deterministik."""
root = None
for k in keys:
root = avl_insert(root, k)
return root
def avl_delete(root, k):
"""Set-AVL delete: düğümü bul, D9 item-takası ile yaprağa indir, kopar,
ata yolunda maintain_up. Döndürür: yeni kök (boşsa None). O(log n)."""
node = root
while node is not None and node.item != k:
node = node.left if k < node.item else node.right
if node is None:
return root
while not (node.left is None and node.right is None):
other = predecessor(node) if node.left is not None else successor(node)
node.item, other.item = other.item, node.item
node = other
parent = node.parent
_replace_child(parent, node, None)
node.parent = None
if parent is None:
return None
return maintain_up(parent)
def subtree_at(node, i):
"""Sıradaki i. düğüm (L7 §3): nₗ = sol.size ile boyut-temelli ikili arama.
i < nₗ → sol; i = nₗ → node; i > nₗ → sağ, i ← i − nₗ − 1. O(h).
"""
while True:
nl = _s(node.left)
if i < nl:
node = node.left
elif i == nl:
return node
else:
node = node.right
i -= nl + 1
def subtree_at_trace(node, i):
"""fig-subtree-at için: ziyaret yolu [(item, nₗ, i, karar), ...]."""
steps = []
while True:
nl = _s(node.left)
if i < nl:
steps.append({"item": node.item, "nl": nl, "i": i, "move": "sol"})
node = node.left
elif i == nl:
steps.append({"item": node.item, "nl": nl, "i": i, "move": "BULUNDU"})
return {"steps": steps, "result": node.item}
else:
steps.append({"item": node.item, "nl": nl, "i": i,
"move": f"sağ (i←{i}−{nl}−1={i - nl - 1})"})
node = node.right
i -= nl + 1
def avl_to_list(root):
"""In-order item listesi (tree_traversal'ın AVL kopyası — aynı mantık)."""
if root is None:
return []
return avl_to_list(root.left) + [root.item] + avl_to_list(root.right)
def check_avl_invariants(root):
"""Üç değişmezi birden doğrula: parent-child tutarlı + height/size kuralları
brute ile aynı + her düğümde |skew| ≤ 1."""
def rec(node):
if node is None:
return (True, -1, 0)
ok_l, hl, sl = rec(node.left)
ok_r, hr, sr = rec(node.right)
ok = ok_l and ok_r
for child in (node.left, node.right):
if child is not None and child.parent is not node:
ok = False
h, s = 1 + max(hl, hr), 1 + sl + sr
if node.height != h or node.size != s or abs(hr - hl) > 1:
ok = False
return (ok, h, s)
return rec(root)[0]
def fib_tree_min_nodes(h):
"""Nₕ = Nₕ₋₁ + Nₕ₋₂ + 1 (L7 §8): yükseklik h'li EN AZ düğümlü AVL.
N₋₁ = 0 (boş), N₀ = 1. Fibonacci-benzeri → üstel → h ≤ 2 log n."""
if h < 0:
return 0
a, b = 0, 1
for _ in range(h):
a, b = b, a + b + 1
return b
def build_fibonacci_tree(h):
"""En az dengeli yükseklik-dengeli ağaç (her düğümde sağ, soldan 1 yüksek);
item'lar in-order 0..Nₕ−1."""
counter = [0]
def rec(hh, parent):
if hh < 0:
return None
node = AVLNode(None)
node.parent = parent
node.left = rec(hh - 2, node)
node.item = counter[0]
counter[0] += 1
node.right = rec(hh - 1, node)
update_node(node)
return node
return rec(h, None)
def build_case3_tree():
"""Durum 3 deterministik senaryosu (L7 §10): skew(x)=+2, skew(y)=−1.
x=10 kök; çift rotasyon (right_rotate(30) → left_rotate(10)) → 20 kök,
dengeli, traversal [5,10,15,20,25,30,40] DEĞİŞMEZ."""
x = AVLNode(10)
n5 = AVLNode(5); n5.parent = x; x.left = n5
y = AVLNode(30); y.parent = x; x.right = y
z = AVLNode(20); z.parent = y; y.left = z
n40 = AVLNode(40); n40.parent = y; y.right = n40
n15 = AVLNode(15); n15.parent = z; z.left = n15
n25 = AVLNode(25); n25.parent = z; z.right = n25
for node in (n5, n15, n25, n40, z, n40, y, x):
update_node(node)
return x
```
## Geçen Dersten: O(h) İşlemler ve Bugünkü Hedef {#sec-gecen-ders}
Ders 9'da (L6) ikili ağaç düğümü `item` + `node.left`/`node.right`/`node.parent` tutuyordu; **yükseklik** (en uzun aşağı yoldaki kenar sayısı) tanımlandı; **traversal sırası** (sol → kök → sağ) örtük düzeni kodluyordu. subtree_first/last, predecessor/successor, insert/delete — hepsi **$O(h)$**.
Sorun: en kötü durumda $h$ lineerdir (yalnız sağ işaretçiler kullanılan zincir ağaç). Bugün $h = O(\log n)$ garanti edip tüm işlemleri **$O(\log n)$**'e indireceğiz — veri yapısını yeniden kurmadan, sadece dengeleyerek.
## Küme Ağaçları = İkili Arama Ağaçları (BST) {#sec-kume-bst}
Küme için traversal sırasını **artan anahtar** yaparsak, `subtree_find` bir **ikili arama** olur: kökten başla, aranan anahtar düğümünkinden küçükse `node.left`'e, büyükse `node.right`'e in, eşitse bulundu.
> *"set binary trees are called binary search trees, because they're the tree version of binary search."* — Demaine, 6:30
Bunu doğru kılan **BST özelliği**: bir düğümün sol alt ağacındaki tüm anahtarlar $<$ düğüm $<$ sağ alt ağacındaki tüm anahtarlar (özyinelemeli). Bu, traversal sırası tanımının (sol önce, sağ sonra) doğrudan sonucudur. find_prev/find_next: ağaçtan düşersen, son denenen yön sana komşuyu verir. **$O(h)$**.
## Dizi Ağaçları: subtree_at {#sec-dizi-subtree-at}
Dizi için traversal sırasını **sequence sırası** yaparız; ama "$i$. öğeyi getir" (`subtree_at`) için artık anahtar yok — *sıra numarasıyla* aramamız gerekir. Anahtar fikir: her düğümde **alt ağaç boyutu** `size`'ı bil.
**Çalışılan Örnek — subtree_at.** $n_\ell$ = `node.left.size` (sol alt ağaçtaki düğüm sayısı) olsun. $i$. öğeyi ararken:
- $i < n_\ell$ → öğe sol alt ağaçta → `subtree_at(node.left, i)`.
- $i = n_\ell$ → kökün indeksi tam $n_\ell$'dir → node'u döndür.
- $i > n_\ell$ → öğe sağ alt ağaçta → `subtree_at(node.right, i − nₗ − 1)` (sol için $n_\ell$, kök için 1 çıkar).
Bu, BST find'in *anahtar yerine boyut* kullanan ikizidir; **$O(h)$**. Bununla get_at/set_at (düğümü bul, item'ı oku/değiştir) ve — ilk kez! — insert_at/delete_at ($i$'yi bul, subtree_insert_before ile araya ekle) yapılır; tüm indeksler kendiliğinden güncellenir, çünkü indeks saklanmıyor.
@fig-subtree-at bunu somut bir örnekte gösterir: `build_avl(range(15))` mükemmel dengeli ağacında (kök $7$, $h = 3$) $i = 10$ aranır; yol $7 \to 11 \to 9 \to 10$ ile öğe bulunur.
```{python}
#| label: fig-subtree-at
#| fig-cap: "subtree_at — size ile boyut-temelli ikili arama, O(h) (L7 §3). Deterministik örnek `build_avl(range(15))`: kök 7, h = 3, size = 15. Aranan i = 10. Her yol düğümünün üstünde karar kutusu (motordan): **7** (nₗ = 7, i = 10) → i > nₗ → SAĞ, i ← 10 − 7 − 1 = 2; **11** (nₗ = 3, i = 2) → i < nₗ → SOL; **9** (nₗ = 1, i = 2) → i > nₗ → SAĞ, i ← 2 − 1 − 1 = 0; **10** (nₗ = 0, i = 0) → i = nₗ → BULUNDU (amber dolgu). Her düğümün yanında küçük slate size rozeti (s = N). BST find anahtar yerine BOYUT kullanır: nₗ = node.left.size. Her adım bir seviye iner → yol uzunluğu ≤ h = 3 → O(h)."
#| fig-width: 11.0
#| fig-height: 6.8
# fig-subtree-at (L7 §3): size-anotasyonlu ağaçta i. öğe arama yolu (üç durum).
# Veri MOTORDAN (build_avl(range(15)) / subtree_at_trace / subtree_at).
# COL_* / apply_style / plt gizli setup hücresinden (inline _engine + _viz).
_SA_R = 0.34
_SA_X_GAP = 1.18
_SA_Y_GAP = 2.05
# build_avl(range(15)) mükemmel dengeli → her item kendi in-order index'inde.
_SA_LEVEL = {
7: 0,
3: 1, 11: 1,
1: 2, 5: 2, 9: 2, 13: 2,
0: 3, 2: 3, 4: 3, 6: 3, 8: 3, 10: 3, 12: 3, 14: 3,
}
def _sa_coords(item, y_top):
return item * _SA_X_GAP, y_top - _SA_LEVEL[item] * _SA_Y_GAP
def _sa_draw_tree(ax, root, y_top, *, path_items, fill_item, sizes):
path_set = set(path_items)
path_edges = {tuple(sorted(e)) for e in zip(path_items, path_items[1:])}
def walk_edges(node):
for child in (node.left, node.right):
if child is not None:
px, py = _sa_coords(node.item, y_top)
cx, cy = _sa_coords(child.item, y_top)
hot = tuple(sorted((node.item, child.item))) in path_edges
ax.plot([px, cx], [py, cy],
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=3.0 if hot else 1.4,
zorder=2 if hot else 1, solid_capstyle="round")
walk_edges(child)
walk_edges(root)
for top_item, bot_item in zip(path_items, path_items[1:]):
tx, ty = _sa_coords(top_item, y_top)
bx, by = _sa_coords(bot_item, y_top)
ax.add_patch(FancyArrowPatch(
(tx, ty), (bx, by), arrowstyle="-|>", mutation_scale=18,
color=COL_AMBER_700, linewidth=3.0,
shrinkA=_SA_R * 72 * 0.50, shrinkB=_SA_R * 72 * 0.50, zorder=4))
def walk_nodes(node):
x, y = _sa_coords(node.item, y_top)
on_path = node.item in path_set
if node.item == fill_item:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 3.0, COL_AMBER_700
elif on_path:
fc, ec, lw, tcol = COL_WHITE, COL_ACCENT, 2.6, COL_AMBER_700
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.5, COL_TEXT
ax.add_patch(Circle((x, y), _SA_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, str(node.item), ha="center", va="center",
fontsize=12.5, color=tcol, weight="bold", zorder=6)
sval = sizes[node.item]
bw, bh = 0.62, 0.32
bx0 = x + _SA_R * 0.62
by0 = y - _SA_R - bh - 0.04
ax.add_patch(FancyBboxPatch(
(bx0, by0), bw, bh, boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.1, zorder=5))
ax.text(bx0 + bw * 0.5, by0 + bh * 0.5, f"s={sval}",
ha="center", va="center", fontsize=7.2,
color=COL_SLATE_500, weight="bold", zorder=6)
for child in (node.left, node.right):
if child is not None:
walk_nodes(child)
walk_nodes(root)
def _sa_decision_box(ax, item, y_top, text, found=False):
x, y = _sa_coords(item, y_top)
bw, bh = 1.55, 0.86
bx0 = x - bw * 0.5
by0 = y + _SA_R + 0.18
fc = COL_AMBER_100 if found else COL_WHITE
ec = COL_ACCENT if found else COL_AMBER_600
ax.add_patch(FancyBboxPatch(
(bx0, by0), bw, bh, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=fc, ec=ec, linewidth=2.0, zorder=7))
ax.text(x, by0 + bh * 0.5, text, ha="center", va="center",
fontsize=8.3, color=COL_AMBER_700, weight="bold", zorder=8,
linespacing=1.25)
ax.plot([x, x], [by0, y + _SA_R], color=COL_AMBER_600,
linewidth=1.0, linestyle=(0, (2, 2)), zorder=6)
r = build_avl(list(range(15)))
assert r.item == 7 and r.height == 3 and r.size == 15
assert avl_to_list(r) == list(range(15))
assert check_avl_invariants(r)
tr = subtree_at_trace(r, 10)
steps = tr["steps"]
path_items = [s["item"] for s in steps]
assert path_items == [7, 11, 9, 10]
fill_item = tr["result"]
assert fill_item == 10 and subtree_at(r, 10).item == 10
sizes = {}
def _sa_collect(n):
if n is None:
return
sizes[n.item] = n.size
_sa_collect(n.left)
_sa_collect(n.right)
_sa_collect(r)
fig, ax = plt.subplots(figsize=(11.0, 6.8))
fig.patch.set_facecolor(COL_WHITE)
y_top = 0.0
_sa_draw_tree(ax, r, y_top, path_items=path_items, fill_item=fill_item,
sizes=sizes)
for s in steps:
it, nl, i = s["item"], s["nl"], s["i"]
if s["move"] == "BULUNDU":
_sa_decision_box(ax, it, y_top, f"i={i}, nₗ={nl}\ni = nₗ → BULUNDU",
found=True)
elif s["move"] == "sol":
_sa_decision_box(ax, it, y_top, f"i={i}, nₗ={nl}\ni < nₗ → SOL")
else:
inew = i - nl - 1
_sa_decision_box(ax, it, y_top,
f"i={i}, nₗ={nl}\ni > nₗ → SAĞ (i←{inew})")
fx, fy = _sa_coords(fill_item, y_top)
ax.text(fx + _SA_R + 0.20, fy, "BULUNDU", ha="left", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=8)
fig.suptitle(
"subtree_at(kök, i=10) — size ile boyut-temelli ikili arama · O(h)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985)
ax.text(7 * _SA_X_GAP, y_top + 1.55,
"BST find anahtar yerine BOYUT kullanır: nₗ = node.left.size",
ha="center", va="center", fontsize=10.5, color=COL_PRIMARY,
weight="bold")
y_bot = y_top - 3 * _SA_Y_GAP
ax.text(7 * _SA_X_GAP, y_bot - 1.45,
"i < nₗ → sol · i = nₗ → BULUNDU · "
"i > nₗ → sağ, i ← i − nₗ − 1",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold")
ax.text(7 * _SA_X_GAP, y_bot - 1.90,
"her düğüm BİR seviye iner → yol uzunluğu ≤ yükseklik h = 3 · O(h)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic")
ax.set_xlim(-0.9, 14 * _SA_X_GAP + 0.9)
ax.set_ylim(y_bot - 2.4, y_top + 2.0)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Alt Ağaç Zenginleştirme (Subtree Augmentation) {#sec-augmentation-d10}
Peki `size`'ı nasıl $O(1)$'de biliriz? **Alt ağaç zenginleştirmesiyle**: her düğüm sabit sayıda ekstra alan tutar. Bir **alt ağaç özelliği (subtree property)**, düğümün *çocuklarının* özelliklerinden $O(1)$'de hesaplanabilen, "aşağı bakan" bir niceliktir.
> *"I'm going to define a subtree property to be something that can be computed from the properties of the node's children."* — Demaine, 16:10
`size` tam da böyledir:
$$\texttt{node.size} = \texttt{node.left.size} + \texttt{node.right.size} + 1$$
> *"node.size equals node.left.size plus node.right.size plus 1."* — Demaine, 17:43
Bu bir **güncelleme kuralıdır** ($O(1)$). `size` saklanır, özyinelemeli yeniden hesaplanmaz (`return node.size` → $O(1)$). Insert/delete sonunda bir **yaprak ekler/siler**; yalnızca o yaprağın **ataları** (ancestors) değişir → ata yolunu yukarı çıkıp her birinde güncelleme kuralını uygula, **$O(h)$**. Bu, tümevarımla doğrudur: alt çocuklar zaten güncelse, kural ile düğüm $O(1)$'de güncellenir.
@fig-augmentation iki panelde bunu gösterir: `build_avl(range(7))` (kök $3$, $h = 2$) ağacına $7$ eklendiğinde yalnız ata yolu $7 \to 6 \to 5 \to 3$ güncellenir; yolun dışındaki alt ağaçlar dokunulmaz kalır.
```{python}
#| label: fig-augmentation
#| fig-cap: "Alt ağaç zenginleştirme — yaprak değişimi yalnız ATALARI günceller, O(h) (L7 §4). **Sol panel:** insert öncesi `build_avl(range(7))` (kök 3, h = 2); her düğümün yanında size + height rozeti; altta O(1) güncelleme kuralı kutusu (node.size = sol.size + sağ.size + 1; node.height = 1 + max(sol.height, sağ.height)). **Sağ panel:** avl_insert(r, 7) sonrası; yeni yaprak 7 amber DOLGU; ata yolu 7 → 6 → 5 → 3 (yapraktan köke) amber KALIN kenar — yalnız bu düğümlerin rozetleri güncellendi. Yolun DIŞINDAki alt ağaçlar soluk + DOKUNULMAZ etiketi. Alt ağaç özelliği AŞAĞI bakar (size/height çocuklardan türer) → yalnız O(h) ata güncellenir (Demaine 16:10)."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-augmentation (L7 §4): yaprak insert → yalnız ATA yolu güncellenir.
# Veri MOTORDAN (build_avl(range(7)) / avl_insert / check_avl_invariants).
_AU_R = 0.34
_AU_X_GAP = 1.05
_AU_Y_GAP = 1.55
def _au_collect(node, depth, xpos, out):
if node is None:
return
_au_collect(node.left, depth + 1, xpos, out)
my_x = xpos[0]
xpos[0] += 1
out[node.item] = {"x": my_x, "depth": depth, "node": node}
_au_collect(node.right, depth + 1, xpos, out)
def _au_layout(root):
out = {}
_au_collect(root, 0, [0], out)
return out
def _au_coords(layout, item, x_off, y_top):
info = layout[item]
return x_off + info["x"] * _AU_X_GAP, y_top - info["depth"] * _AU_Y_GAP
def _au_draw_tree(ax, root, layout, x_off, y_top, *,
fill_item=None, path_items=None, faded_items=None,
amber_badge_items=None):
path_items = set(path_items or [])
faded_items = set(faded_items or [])
amber_badge_items = set(amber_badge_items or [])
def walk_edges(node):
if node is None:
return
for child in (node.left, node.right):
if child is not None:
px, py = _au_coords(layout, node.item, x_off, y_top)
cx, cy = _au_coords(layout, child.item, x_off, y_top)
on_path = (node.item in path_items and child.item in path_items)
faded = (node.item in faded_items or child.item in faded_items) \
and not on_path
if on_path:
col, lw, z = COL_ACCENT, 3.4, 3
elif faded:
col, lw, z = COL_SLATE_400, 1.2, 1
else:
col, lw, z = COL_SLATE_400, 1.6, 1
ax.plot([px, cx], [py, cy], color=col, linewidth=lw, zorder=z,
solid_capstyle="round", alpha=0.5 if faded else 1.0)
walk_edges(child)
walk_edges(root)
def walk_nodes(node):
if node is None:
return
x, y = _au_coords(layout, node.item, x_off, y_top)
faded = node.item in faded_items
if node.item == fill_item:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 3.0, COL_AMBER_700
elif node.item in path_items:
fc, ec, lw, tcol = COL_WHITE, COL_ACCENT, 2.8, COL_AMBER_700
elif faded:
fc, ec, lw, tcol = COL_WHITE, COL_SLATE_400, 1.3, COL_SLATE_500
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.8, COL_TEXT
ax.add_patch(Circle((x, y), _AU_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5, alpha=0.55 if faded else 1.0))
ax.text(x, y, str(node.item), ha="center", va="center",
fontsize=13, color=tcol, weight="bold", zorder=6,
alpha=0.6 if faded else 1.0)
badge_amber = node.item in amber_badge_items
bcol = COL_AMBER_700 if badge_amber else COL_SLATE_500
if faded:
bcol = COL_SLATE_400
ax.text(x + _AU_R + 0.10, y, f"s={node.size} h={node.height}",
ha="left", va="center", fontsize=8.2, color=bcol,
weight="bold" if badge_amber else "normal",
zorder=7, alpha=0.55 if faded else 1.0,
style="normal" if badge_amber else "italic")
walk_nodes(node.left)
walk_nodes(node.right)
walk_nodes(root)
r_pre = build_avl(list(range(7)))
assert avl_to_list(r_pre) == [0, 1, 2, 3, 4, 5, 6]
assert r_pre.item == 3 and r_pre.height == 2
assert check_avl_invariants(r_pre)
layout_pre = _au_layout(r_pre)
r2 = avl_insert(build_avl(list(range(7))), 7)
assert avl_to_list(r2) == [0, 1, 2, 3, 4, 5, 6, 7]
assert check_avl_invariants(r2)
layout_post = _au_layout(r2)
def _au_ancestor_path(root, leaf_item):
node, path = root, []
while node is not None:
path.append(node.item)
if node.item == leaf_item:
break
node = node.left if leaf_item < node.item else node.right
return path
path = _au_ancestor_path(r2, 7)
assert path == [3, 5, 6, 7]
path_set = set(path)
faded_post = set(layout_post.keys()) - path_set
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
pre_span = 6 * _AU_X_GAP
x_off_left = 0.0
x_off_right = pre_span + 3.4
y_top = 0.0
_au_draw_tree(ax, r_pre, layout_pre, x_off_left, y_top)
cx_l = x_off_left + 3 * _AU_X_GAP
ax.text(cx_l, y_top + 1.05, "Önce — 7 düğüm (kök 3, h=2)",
ha="center", va="center", fontsize=12, color=COL_TEXT, weight="bold")
rule_y = y_top - 2 * _AU_Y_GAP - 0.95
ax.add_patch(FancyBboxPatch(
(x_off_left - 0.55, rule_y - 0.62), pre_span + 1.1, 1.18,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=2))
ax.text(cx_l, rule_y + 0.30, "Güncelleme kuralı (her düğümde O(1)):",
ha="center", va="center", fontsize=9.5, color=COL_TEXT, weight="bold")
ax.text(cx_l, rule_y - 0.04, "node.size = sol.size + sağ.size + 1",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold")
ax.text(cx_l, rule_y - 0.36, "node.height = 1 + max(sol.height, sağ.height)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold")
_au_draw_tree(ax, r2, layout_post, x_off_right, y_top,
fill_item=7, path_items=path_set, faded_items=faded_post,
amber_badge_items=path_set)
cx_r = x_off_right + 3 * _AU_X_GAP
ax.text(cx_r, y_top + 1.05, "Sonra — insert(7): yeni yaprak",
ha="center", va="center", fontsize=12, color=COL_TEXT, weight="bold")
info_y = y_top - 3 * _AU_Y_GAP + 0.10
ax.text(cx_r, info_y + 0.05, "ata yolu 7 → 6 → 5 → 3 (yalnız bunlar güncellendi)",
ha="center", va="center", fontsize=9.8, color=COL_AMBER_700,
weight="bold")
ax.text(cx_r, info_y - 0.34, "yol DIŞI alt ağaçlar DOKUNULMAZ — özellik aşağı bakar",
ha="center", va="center", fontsize=8.8, color=COL_SLATE_500,
style="italic")
if 1 in layout_post:
fx, fy = _au_coords(layout_post, 1, x_off_right, y_top)
ax.text(fx, fy + _AU_R + 0.42, "DOKUNULMAZ", ha="center", va="bottom",
fontsize=8.5, color=COL_SLATE_400, weight="bold",
style="italic", zorder=8)
sep_x = (x_off_left + pre_span + x_off_right) * 0.5
ax.plot([sep_x, sep_x], [y_top - 3 * _AU_Y_GAP - 0.2, y_top + 0.8],
color=COL_SLATE_400, linewidth=1.0, linestyle=(0, (3, 3)), zorder=0)
fig.suptitle(
"Alt ağaç zenginleştirme — yaprak değişimi yalnız ATALARI günceller (O(h))",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
note_y = y_top - 3 * _AU_Y_GAP - 0.55
ax.text(sep_x, note_y,
"yalnız O(h) ata güncellenir · alt ağaç özelliği AŞAĞI bakar "
"(size/height çocuklardan türer) · Demaine 16:10",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=10)
ax.set_xlim(x_off_left - 0.9, x_off_right + pre_span + 1.6)
ax.set_ylim(note_y - 0.5, y_top + 1.45)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-tip title="Builder Notu — Order-Statistics: rank ve k. En Küçük"}
`size` zenginleştirmesi, dengeli ağacı bir **order-statistics tree**'ye çevirir: yalnız "$i$. öğe" değil, ters yönü de — bir öğenin **rank**'ı (kaçıncı sırada) ve "$k$. en küçük" sorguları $O(\log n)$'de yanıtlanır.
- **rank(x):** Kökten $x$'e inerken, her sola dönüşte o düğümün $n_\ell + 1$'ini (sol alt ağaç + düğüm kendisi) atlamış olursun; toplam atlanan, $x$'in sıra numarasıdır. Tam `subtree_at`'in tersi.
- **$k$. en küçük:** doğrudan `subtree_at(kök, k)` — @fig-subtree-at'teki yürüyüşün ta kendisi.
- **Pratik kullanım:** "medyanın altında kaç öğe var", "yüzdelik dilim", "şu fiyattan ucuz kaç ürün" gibi sorgular; bir sıralı dizide $O(n)$ olurdu, order-statistics tree'de $O(\log n)$. (Araya giren Problem Oturumu 4 tam bu tür zenginleştirme problemlerini işler.)
Tek cümle: *tek bir `size` alanı, ağacı hem "$i$. öğe"yi hem "bu öğe kaçıncı"yı $O(\log n)$'de bilen bir sıralama-istatistiği yapısına dönüştürür.*
:::
## Hangi Özellikler Tutulabilir? {#sec-tutulabilir}
Alt ağaç özelliği olan her şey: **toplam, çarpım, min, max, kare toplamı** — alt ağaçtaki düğümlerin herhangi bir alanı üzerinden. (`size` aslında "her düğüm için 1'in toplamı"dır.)
Ama **tutulamayanlar** vardır:
- **İndeks (index):** *global*'dir — başa bir düğüm eklersen *tüm* düğümlerin indeksi değişir. Bir düğümün indeksi, solundaki tüm düğümlere (alt ağaç dışı) bağlıdır.
- **Derinlik (depth):** benzer şekilde yukarı-bakan, alt ağaç özelliği değil.
> *"Index is not a subtree property, and that's why we can't maintain it — because it depends on all of the nodes in the tree."* — Demaine, 25:35
Kural: yalnızca **aşağı-bakan (alt ağaca özgü)** özellikler tutulabilir; global özellikler değil.
::: {.callout-tip title="Builder Notu — Yerel (Kompozisyonel) Olan Tutulur"}
Bu, veri yapısı tasarımının ötesine geçen bir ilke: *bir niceliği verimli güncel tutabilmen, onun yerel (kompozisyonel) olmasına bağlıdır.* Yerel = "yalnızca alt parçalardan hesaplanır"; global = "tüm bütüne bağlı".
- **Aşağı-bakan vs global:** `size`/`sum`/`max` çocuklardan $O(1)$'de türer → yaprak değişiminde yalnız $O(h)$ ata güncellenir. `index`/`depth` tüm ağaca bağlı → tek ekleme her şeyi kaydırır, $O(n)$.
- **Dağıtık sistem analojisi:** Bir ağaç-toplama (tree aggregation) veya MapReduce'da yalnız **birleştirilebilir (associative/composable)** agregalar — sum, count, min, max — kısmi sonuçlardan ucuza güncellenir; "global sıra numarası" gibi nicelikler her düğüme tüm veriyi gerektirir.
- **Genel ders:** "Bunu $O(\log n)$'de tutabilir miyim?" sorusunun cevabı, "bu nicelik çocuklarımdan hesaplanabilir mi?" sorusuyla aynıdır.
Tek cümle: *verimli bakım, yerelliğin (kompozisyonelliğin) bir sonucudur — global bir nicelik hiçbir akıllı işaretçi numarasıyla ucuza tutulamaz.*
:::
## Ağaç Rotasyonu {#sec-rotasyon}
Dengeyi sağlamak için yeni bir araç gerekir: **rotasyon**. Tek işi ağacı yeniden dengelemek; **traversal sırasını asla değiştirmemelidir** (traversal sırası temsil edilen veridir — dokunulmaz).
> *"a rotation... a tool for rebalancing the tree. So it should not change the data that's represented by the tree. ... Traversal order is sacrosanct."* — Demaine, 30:07
**Çalışılan Örnek — rotasyon.** Bir $y$ düğümü ve sol çocuğu $x$ düşün; alt ağaçlar $A$ ($x$'in solu), $B$ ($x$'in sağı), $C$ ($y$'nin sağı). **right_rotate(y)**: $x$ yukarı, $y$ aşağı geçer; $B$, $x$'ten kopup $y$'nin soluna bağlanır. Her iki çizimde de traversal sırası **$A, X, B, Y, C$** kalır (üçgenler özyinelemeli). Yani rotasyon sırayı korur ama derinlikleri değiştirir: $x$ yukarı (sığlaşır), $y$ aşağı (derinleşir), bu da yeniden dengeleme imkânı verir. (Simetriği **left_rotate(x)**.) Aynı ağaç düzeni üstel sayıda farklı ağaçla temsil edilebilir; rotasyon bu fazlalığı kullanır.
@fig-rotation iki paneli yan yana koyar (öncesi/sonrası); alttaki in-order şerit $A, X, B, Y, C$ her iki panelde aynen aynı kalır.
```{python}
#| label: fig-rotation
#| fig-cap: "right_rotate — yapı değişir, traversal sırası KORUNUR (A, X, B, Y, C) (L7 §6, İMZA figür). **Sol panel (öncesi):** kök Y, sol çocuğu X; alt ağaçlar A = X.left, B = X.right (amber dolgu = yer değiştirecek), C = Y.right. Kavisli amber ok right_rotate(Y)'yi gösterir. **Sağ panel (sonrası):** kök X (amber çerçeve); B artık X'in sağından Y'nin SOLUNA taşındı (amber taşıma oku). HER iki panelin altında AYNI in-order şeridi A | X | B | Y | C; ortada SIRA KORUNUR rozeti + eşittir işareti. Rotasyon = O(1) işaretçi takası + augmentation güncelle; in-order dizilim kutsaldır (Demaine 30:07). Motor doğrulaması: right_rotate öncesi avl_to_list = sonrası avl_to_list = [A, X, B, Y, C]."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-rotation (L7 §6 İMZA): right_rotate(y) öncesi/sonrası; traversal KORUNUR.
# Veri MOTORDAN (AVLNode elle kurulur + right_rotate + avl_to_list ASSERT).
_RT_R = 0.34
_RT_X_GAP = 1.00
_RT_Y_GAP = 1.20
_RT_INORDER = ["A", "X", "B", "Y", "C"]
_RT_INORDER_X = {item: k for k, item in enumerate(_RT_INORDER)}
_RT_LEVEL_BEFORE = {"Y": 0, "X": 1, "C": 1, "A": 2, "B": 2}
_RT_LEVEL_AFTER = {"X": 0, "A": 1, "Y": 1, "B": 2, "C": 2}
_RT_EDGES_BEFORE = [("Y", "X"), ("Y", "C"), ("X", "A"), ("X", "B")]
_RT_EDGES_AFTER = [("X", "A"), ("X", "Y"), ("Y", "B"), ("Y", "C")]
def _rt_build_tree():
y = AVLNode("Y")
x = AVLNode("X"); x.parent = y; y.left = x
c = AVLNode("C"); c.parent = y; y.right = c
a = AVLNode("A"); a.parent = x; x.left = a
b = AVLNode("B"); b.parent = x; x.right = b
for node in (a, b, c, x, y):
update_node(node)
return y, x, a, b, c
def _rt_coords(item, levels, x_off, y_top):
return x_off + _RT_INORDER_X[item] * _RT_X_GAP, y_top - levels[item] * _RT_Y_GAP
def _rt_node_style(item, fill_item, frame_item):
if item == fill_item:
return COL_AMBER_100, COL_ACCENT, 2.8, COL_AMBER_700
if item == frame_item:
return COL_WHITE, COL_ACCENT, 2.8, COL_AMBER_700
return COL_BG, COL_PRIMARY, 1.7, COL_TEXT
def _rt_draw_panel(ax, levels, edges, x_off, y_top, *, fill_item, frame_item,
moved_edge=None):
moved = tuple(moved_edge) if moved_edge else None
for (top_item, bot_item) in edges:
tx, ty = _rt_coords(top_item, levels, x_off, y_top)
bx, by = _rt_coords(bot_item, levels, x_off, y_top)
hot = (moved is not None and (top_item, bot_item) == moved)
ax.plot([tx, bx], [ty, by],
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=3.0 if hot else 1.6,
zorder=2 if hot else 1, solid_capstyle="round")
if moved is not None:
tx, ty = _rt_coords(moved[0], levels, x_off, y_top)
bx, by = _rt_coords(moved[1], levels, x_off, y_top)
ax.add_patch(FancyArrowPatch(
(tx, ty), (bx, by), arrowstyle="-|>", mutation_scale=16,
color=COL_AMBER_700, linewidth=2.6,
shrinkA=_RT_R * 72 * 0.50, shrinkB=_RT_R * 72 * 0.50, zorder=4))
for item in _RT_INORDER:
x, y = _rt_coords(item, levels, x_off, y_top)
fc, ec, lw, tcol = _rt_node_style(item, fill_item, frame_item)
ax.add_patch(Circle((x, y), _RT_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, item, ha="center", va="center",
fontsize=13, color=tcol, weight="bold", zorder=6)
def _rt_draw_strip(ax, x_off, y_strip, *, fill_item, frame_item):
sw = _RT_X_GAP
for k, item in enumerate(_RT_INORDER):
x = x_off + k * sw
if item == fill_item:
fc, ec, tcol = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
elif item == frame_item:
fc, ec, tcol = COL_WHITE, COL_ACCENT, COL_AMBER_700
else:
fc, ec, tcol = COL_BG, COL_PRIMARY, COL_TEXT
ax.add_patch(plt.Rectangle(
(x - sw * 0.40, y_strip - 0.27), sw * 0.80, 0.54,
facecolor=fc, edgecolor=ec, linewidth=1.8, zorder=3))
ax.text(x, y_strip, item, ha="center", va="center",
fontsize=11.5, color=tcol, weight="bold", zorder=5)
ax.text(x_off - sw * 0.72, y_strip, "in-order", ha="right", va="center",
fontsize=9, color=COL_SLATE_500, weight="bold", zorder=5)
y_, x_, a_, b_, c_ = _rt_build_tree()
before = avl_to_list(y_)
assert before == ["A", "X", "B", "Y", "C"]
new_root = right_rotate(y_)
after = avl_to_list(new_root)
assert after == ["A", "X", "B", "Y", "C"] and before == after
assert new_root is x_ and new_root.left is a_ and new_root.right is y_
assert y_.left is b_ and y_.right is c_
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
panel_span = (len(_RT_INORDER) - 1) * _RT_X_GAP
x_off_left = 0.0
x_off_right = panel_span + 3.0
y_top = 0.0
y_strip = y_top - 2 * _RT_Y_GAP - 0.95
_rt_draw_panel(ax, _RT_LEVEL_BEFORE, _RT_EDGES_BEFORE, x_off_left, y_top,
fill_item="B", frame_item="X")
cx_l = x_off_left + 2 * _RT_X_GAP
ax.text(cx_l, y_top + 0.95, "Rotasyon ÖNCESİ — kök Y",
ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold")
yx, yy = _rt_coords("Y", _RT_LEVEL_BEFORE, x_off_left, y_top)
xx, xy = _rt_coords("X", _RT_LEVEL_BEFORE, x_off_left, y_top)
ax.add_patch(FancyArrowPatch(
(yx + _RT_R + 0.10, yy + 0.18), (xx + _RT_R + 0.06, xy + 0.30),
arrowstyle="-|>", mutation_scale=18, color=COL_AMBER_600,
linewidth=2.8, zorder=7, connectionstyle="arc3,rad=-0.55"))
ax.text(cx_l, y_top - _RT_Y_GAP - 0.10, "right_rotate(Y)",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=8)
_rt_draw_strip(ax, x_off_left, y_strip, fill_item="B", frame_item="X")
_rt_draw_panel(ax, _RT_LEVEL_AFTER, _RT_EDGES_AFTER, x_off_right, y_top,
fill_item="B", frame_item="X", moved_edge=("Y", "B"))
cx_r = x_off_right + 2 * _RT_X_GAP
ax.text(cx_r, y_top + 0.95, "Rotasyon SONRASI — kök X",
ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold")
ax.text(cx_r, y_top - _RT_Y_GAP - 0.10, "B X'in sağından → Y'nin SOLUNA",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=8)
_rt_draw_strip(ax, x_off_right, y_strip, fill_item="B", frame_item="X")
mid_x = (x_off_left + panel_span + x_off_right) * 0.5
for dy in (0.12, -0.12):
ax.plot([mid_x - 0.30, mid_x + 0.30], [y_strip + dy, y_strip + dy],
color=COL_AMBER_700, linewidth=3.0, zorder=6, solid_capstyle="round")
ax.text(mid_x, y_strip + 0.62, "SIRA\nKORUNUR", ha="center", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=8)
sep_x = mid_x
ax.plot([sep_x, sep_x], [y_top - 2 * _RT_Y_GAP - 0.3, y_top + 0.7],
color=COL_SLATE_400, linewidth=1.0, linestyle=(0, (3, 3)), zorder=0)
fig.suptitle(
"right_rotate — yapı değişir, traversal sırası KORUNUR (A, X, B, Y, C)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975)
ax.text(mid_x, y_strip - 0.92,
"rotasyon = O(1) işaretçi takası + augmentation güncelle · "
"in-order dizilim kutsaldır (Demaine 30:07)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=8)
ax.set_xlim(x_off_left - 1.3, x_off_right + panel_span + 1.1)
ax.set_ylim(y_strip - 1.35, y_top + 1.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-tip title="Builder Notu — Rotasyon: Tüm Dengeli Ağaçların Ortak İlkeli"}
Rotasyon, AVL'ye özgü değil — **tüm kendini-dengeleyen ağaçların** ortak ilkel (primitive) işlemidir. "Sırayı bozmadan derinlik değiştir" mekanizması her yerde aynıdır; ağaçlar yalnızca *ne zaman* döndüreceklerine dair kuralda ayrışır.
- **red-black tree:** Renk kuralları + rotasyon; çoğu standart kütüphane `map`/`set`'i (örneğin C++ STL, Java TreeMap) red-black ağacıdır.
- **splay tree:** Her erişimde erişilen düğümü rotasyonlarla köke taşır — "son kullanılan hızlı" (self-adjusting).
- **treap:** Rastgele öncelik + BST anahtarı; rotasyonla heap-özelliği korunur.
Hepsinde değişmez aynı: rotasyon $O(1)$'dir ve traversal sırasını korur; yalnız hangi düğümde tetiklendiğinin politikası farklıdır.
Tek cümle: *rotasyonu öğrenmek tek bir ağacı değil, kendini-dengeleyen ağaç ailesinin tamamını öğrenmektir — fark, kuralda; ilkel hep aynı.*
:::
## AVL / Yükseklik Dengesi {#sec-avl-skew}
Hangi denge kuralı? Her düğüm için **skew** tanımla:
$$\text{skew}(\text{node}) = \text{height}(\text{node.right}) - \text{height}(\text{node.left})$$
**AVL kuralı:** her düğümde skew $\in \{-1, 0, +1\}$ — yani sol ve sağ alt ağaç yükseklikleri en fazla 1 fark eder.
> *"skew of the node — I want this to always be minus 1, 0, or plus 1."* — Demaine, 35:11
@fig-avl-skew skew tanımını dört mini ağaç üzerinde gösterir: üçü kural içinde ($-1, 0, +1$), biri ihlal ($+2$).
```{python}
#| label: fig-avl-skew
#| fig-cap: "AVL kuralı — her düğümde skew ∈ {−1, 0, +1} (L7 §7; Demaine 35:11). Dört mini ağaç (skew = h(sağ) − h(sol), motordan okunur): **(a)** sol 1 yüksek → skew = 0 − 1 = −1, AVL-OK; **(b)** iki taraf eşit → skew = 0 − 0 = 0, AVL-OK; **(c)** sağ 1 yüksek → skew = 1 − 0 = +1, AVL-OK; **(d)** sağ 2 yüksek → skew = 1 − (−1) = +2, İHLAL (kalın slate çerçeve) → rotasyon gerek. İlk üç panel amber ONAY çerçevesi, dördüncü kalın slate çerçeve. Yükseklikler height alanından okunur (augmentation) → skew O(1); |skew| = 2 olunca ata yolunda rotasyon onarır."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-avl-skew (L7 §7): skew = h(sağ) − h(sol) dört örnek (−1, 0, +1 OK; +2 İHLAL).
# Veri MOTORDAN (AVLNode elle + update_node BOTTOM-UP + skew ASSERT).
_SK_R = 0.27
_SK_Y_GAP = 1.05
def _sk_leaf(k):
n = AVLNode(k)
update_node(n)
return n
def _sk_join(k, left, right):
n = AVLNode(k)
n.left = left
n.right = right
if left is not None:
left.parent = n
if right is not None:
right.parent = n
update_node(n)
return n
def _sk_tree_neg1():
n2 = _sk_join(2, _sk_leaf(1), _sk_leaf(3))
root = _sk_join(4, n2, _sk_leaf(6))
layout = {4: (0.0, 0), 2: (-1.0, 1), 6: (1.0, 1), 1: (-1.6, 2), 3: (-0.4, 2)}
return root, layout
def _sk_tree_zero():
root = _sk_join(4, _sk_leaf(2), _sk_leaf(6))
layout = {4: (0.0, 0), 2: (-1.0, 1), 6: (1.0, 1)}
return root, layout
def _sk_tree_pos1():
n6 = _sk_join(6, _sk_leaf(5), _sk_leaf(7))
root = _sk_join(4, _sk_leaf(2), n6)
layout = {4: (0.0, 0), 2: (-1.0, 1), 6: (1.0, 1), 5: (0.4, 2), 7: (1.6, 2)}
return root, layout
def _sk_tree_pos2():
n4 = _sk_join(4, None, _sk_leaf(6))
root = _sk_join(2, None, n4)
layout = {2: (-0.7, 0), 4: (0.1, 1), 6: (0.9, 2)}
return root, layout
def _sk_draw_mini_tree(ax, root, layout, x_off, y_top):
def xy(item):
xr, lvl = layout[item]
return x_off + xr, y_top - lvl * _SK_Y_GAP
def walk_edges(node):
for child in (node.left, node.right):
if child is not None:
px, py = xy(node.item)
cx, cy = xy(child.item)
ax.plot([px, cx], [py, cy], color=COL_SLATE_400,
linewidth=1.7, zorder=1, solid_capstyle="round")
walk_edges(child)
walk_edges(root)
def walk_nodes(node):
x, y = xy(node.item)
ax.add_patch(Circle((x, y), _SK_R, facecolor=COL_BG, edgecolor=COL_PRIMARY,
linewidth=1.7, zorder=4))
ax.text(x, y, str(node.item), ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold", zorder=5)
for child in (node.left, node.right):
if child is not None:
walk_nodes(child)
walk_nodes(root)
def _sk_draw_panel(ax, root, layout, sk, *, ok, panel_x_center, y_top,
title, frame_x0, frame_x1, frame_y0, frame_y1):
if ok:
fc, ec, lw = COL_WHITE, COL_ACCENT, 2.2
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 3.2
ax.add_patch(FancyBboxPatch(
(frame_x0, frame_y0), frame_x1 - frame_x0, frame_y1 - frame_y0,
boxstyle="round,pad=0.02,rounding_size=0.12",
fc=fc, ec=ec, linewidth=lw, zorder=0))
ax.text(panel_x_center, frame_y1 - 0.30, title, ha="center", va="center",
fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6)
_sk_draw_mini_tree(ax, root, layout, panel_x_center, y_top)
hr = root.right.height if root.right is not None else -1
hl = root.left.height if root.left is not None else -1
hr_str = str(hr) if hr >= 0 else f"({hr})"
hl_str = str(hl) if hl >= 0 else f"({hl})"
sk_str = f"+{sk}" if sk > 0 else str(sk)
ax.text(panel_x_center, frame_y0 + 0.74,
f"skew = h(sağ) − h(sol) = {hr_str} − {hl_str} = {sk_str}",
ha="center", va="center", fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=6)
if ok:
ax.text(panel_x_center, frame_y0 + 0.34,
"AVL-OK skew ∈ {−1, 0, +1}", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_600, weight="bold", zorder=6)
else:
ax.text(panel_x_center, frame_y0 + 0.34,
"İHLAL |skew| = 2 → rotasyon gerek", ha="center",
va="center", fontsize=8.5, color=COL_PRIMARY, weight="bold",
zorder=6)
a_root, a_lay = _sk_tree_neg1()
b_root, b_lay = _sk_tree_zero()
c_root, c_lay = _sk_tree_pos1()
d_root, d_lay = _sk_tree_pos2()
sk_a, sk_b, sk_c, sk_d = skew(a_root), skew(b_root), skew(c_root), skew(d_root)
assert (sk_a, sk_b, sk_c, sk_d) == (-1, 0, 1, 2)
assert all(abs(skew(t)) <= 1 for t in (a_root, b_root, c_root))
assert abs(skew(d_root)) == 2
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
panel_w = 3.4
gap = 0.45
frame_y0 = 0.0
frame_y1 = 4.85
y_top = frame_y1 - 1.05
panels = [
(a_root, a_lay, sk_a, True, "(a) sol 1 yüksek"),
(b_root, b_lay, sk_b, True, "(b) eşit"),
(c_root, c_lay, sk_c, True, "(c) sağ 1 yüksek"),
(d_root, d_lay, sk_d, False, "(d) sağ 2 yüksek"),
]
for idx, (root, lay, sk, ok, title) in enumerate(panels):
fx0 = idx * (panel_w + gap)
fx1 = fx0 + panel_w
cx = (fx0 + fx1) * 0.5
_sk_draw_panel(ax, root, lay, sk, ok=ok, panel_x_center=cx, y_top=y_top,
title=title, frame_x0=fx0, frame_x1=fx1,
frame_y0=frame_y0, frame_y1=frame_y1)
total_w = 4 * panel_w + 3 * gap
fig.suptitle(
"AVL kuralı — her düğümde skew ∈ {−1, 0, +1} (Demaine 35:11)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975)
ax.text(total_w * 0.5, frame_y0 - 0.55,
"yükseklikler height alanından okunur (augmentation) → skew O(1) · "
"|skew| = 2 olunca ata yolunda rotasyon onarır",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic")
ax.set_xlim(-0.4, total_w + 0.4)
ax.set_ylim(frame_y0 - 1.05, frame_y1 + 0.55)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Yükseklik Dengesi → Denge {#sec-yukseklik-denge}
**Çalışılan Örnek — neden $h \le 2 \log n$?** En *az* dengeli yükseklik-dengeli ağacı düşün: her düğümde sağ, soldan 1 yüksek. Yükseklik $h$ olan böyle bir ağaçtaki minimum düğüm sayısı $N_h$:
$$N_h = N_{h-1} + N_{h-2} + 1$$
Bu **Fibonacci benzeri** bir yinelemedir ($+1$ olmadan tam Fibonacci); Fibonacci sayıları altın oran kuvvetiyle, yani **üstel** büyür. Üstel alt sınırı basitçe görmek için: $N_{h-1} \ge N_{h-2}$ olduğundan $N_h > 2 \cdot N_{h-2}$; bu da $N_h \ge 2^{h/2}$ verir.
> *"It's like Fibonacci numbers... Fibonacci numbers grow as a golden ratio to the n... this is exponential."* — Demaine, 39:48
$N_h$ düğüm sayısı $h$'de üstel olduğundan, $h$ düğüm sayısında **logaritmiktir**: $h \le 2 \log n$. Yani AVL ağaçları her zaman dengelidir (gereken seviye sayısının en çok iki katı).
> *"h is at most 2 log n. So AVL trees are always quite balanced."* — Demaine, 42:09
@fig-fibonacci-height bunu iki panelde gösterir: solda `build_fibonacci_tree(4)` ($h = 4$, $n = N_4 = 12$), sağda $N_h$ dizisinin $2^{h/2}$ alt sınırına karşı üstel büyümesi.
```{python}
#| label: fig-fibonacci-height
#| fig-cap: "En az dengeli AVL = Fibonacci ağacı → yükseklik h ≤ 2 log n (L7 §8; Demaine 42:09). **Sol panel:** build_fibonacci_tree(4) — h = 4, n = N₄ = 12; her düğümde sağ alt ağaç soldan TAM 1 yüksek (en az dengeli yükseklik-dengeli ağaç, sağ-ağır kademeli); in-order 0..11; en derin yol (sağ omurga, h + 1 = 5 düğüm) amber vurgulu. **Sağ panel (semilog):** Nₕ noktaları (motor dizisi [1, 2, 4, 7, 12, 20, 33, 54], h = 0..7) + alt sınır 2^(h/2) (amber kesikli); aradaki taralı bölge ÜSTEL büyümeyi gösterir; her h için Nₕ ≥ 2^(h/2). Nₕ = Nₕ₋₁ + Nₕ₋₂ + 1 (Fibonacci-benzeri) → düğüm sayısı h'de ÜSTEL → tersi: yükseklik logaritmik, h ≤ 2 log n."
#| fig-width: 11.0
#| fig-height: 6.4
# fig-fibonacci-height (L7 §8): Fibonacci ağaç (h=4) + Nₕ vs 2^(h/2) semilog.
# Veri MOTORDAN (build_fibonacci_tree(4) / fib_tree_min_nodes / check_avl_invariants).
_FH_R = 0.32
_FH_X_GAP = 0.78
_FH_Y_GAP = 1.05
def _fh_layout(root):
order = []
def ino(n):
if n is None:
return
ino(n.left)
order.append(n.item)
ino(n.right)
ino(root)
xpos = {v: i for i, v in enumerate(order)}
depth = {}
def dd(n, d=0):
if n is None:
return
depth[n.item] = d
dd(n.left, d + 1)
dd(n.right, d + 1)
dd(root)
parent = {}
def pp(n):
if n is None:
return
for c in (n.left, n.right):
if c is not None:
parent[c.item] = n.item
pp(c)
pp(root)
def _hh(n):
return n.height if n is not None else -1
deepest = []
n = root
while n is not None:
deepest.append(n.item)
n = n.right if _hh(n.right) >= _hh(n.left) else n.left
return xpos, depth, parent, deepest
def _fh_coords(item, xpos, depth):
return xpos[item] * _FH_X_GAP, -depth[item] * _FH_Y_GAP
def _fh_draw_tree(ax, root):
xpos, depth, parent, deepest = _fh_layout(root)
deepest_set = set(deepest)
deepest_edges = {tuple(sorted((deepest[i], deepest[i + 1])))
for i in range(len(deepest) - 1)}
root_item = deepest[0]
for child, par in parent.items():
cx, cy = _fh_coords(child, xpos, depth)
px, py = _fh_coords(par, xpos, depth)
hot = tuple(sorted((child, par))) in deepest_edges
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")
for item in xpos:
x, y = _fh_coords(item, xpos, depth)
on_path = item in deepest_set
is_root = (item == root_item)
if is_root:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.8
elif on_path:
fc, ec, lw = COL_WHITE, COL_ACCENT, 2.4
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 1.6
ax.add_patch(Circle((x, y), _FH_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
tcol = COL_AMBER_700 if (on_path or is_root) else COL_TEXT
ax.text(x, y, str(item), ha="center", va="center",
fontsize=10.5, color=tcol, weight="bold", zorder=6)
rx, ry = _fh_coords(root_item, xpos, depth)
ax.text(rx - _FH_R - 0.20, ry + 0.02,
f"kök:\nh={root.height}, n=N₄={root.size}", ha="right", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=7,
linespacing=1.25)
leaf = deepest[-1]
lx, ly = _fh_coords(leaf, xpos, depth)
ax.text(lx, ly - _FH_R - 0.20,
f"en derin yol\n= h+1 = {len(deepest)} düğüm",
ha="center", va="top", fontsize=8.5,
color=COL_AMBER_700, weight="bold", zorder=7, linespacing=1.2)
max_depth = max(depth.values())
ax.text((len(xpos) - 1) * _FH_X_GAP * 0.5, 0.62,
"En az dengeli AVL — her düğümde SAĞ alt ağaç soldan 1 yüksek",
ha="center", va="center", fontsize=10, color=COL_TEXT, weight="bold")
ax.text((len(xpos) - 1) * _FH_X_GAP * 0.5, -max_depth * _FH_Y_GAP - 1.05,
"(in-order 0..11 · sağ-ağır kademeli yapı = Fibonacci ağacı)",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic")
ax.set_xlim(-0.9, (len(xpos) - 1) * _FH_X_GAP + 0.9)
ax.set_ylim(-max_depth * _FH_Y_GAP - 1.45, 1.0)
ax.set_aspect("equal")
ax.axis("off")
def _fh_draw_growth(ax, hs, nh_vals):
apply_style(ax)
lower = [2.0 ** (h / 2.0) for h in hs]
ax.semilogy(hs, lower, color=COL_ACCENT, linewidth=2.2, linestyle="--",
marker=None, zorder=3, label=r"alt sınır $2^{h/2}$")
ax.semilogy(hs, nh_vals, color=COL_PRIMARY, linewidth=2.2, marker="o",
markersize=6, markerfacecolor=COL_AMBER_100,
markeredgecolor=COL_PRIMARY, zorder=5,
label=r"$N_h = N_{h-1}+N_{h-2}+1$")
ax.fill_between(hs, lower, nh_vals, color=COL_AMBER_300, alpha=0.30,
hatch="///", edgecolor=COL_AMBER_600, linewidth=0.0, zorder=1)
mid = len(hs) // 2 + 1
ax.text(hs[mid], math.sqrt(lower[mid] * nh_vals[mid]) * 1.05, "ÜSTEL",
ha="center", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", rotation=14, zorder=6)
for h, v in zip(hs, nh_vals):
ax.annotate(str(v), (h, v), textcoords="offset points",
xytext=(0, 8), ha="center", fontsize=8.5,
color=COL_TEXT, weight="bold", zorder=6)
ax.set_xlabel("yükseklik h")
ax.set_ylabel("en az düğüm sayısı Nₕ (log ölçek)")
ax.set_title("En az dengeli AVL üstel büyür → h ≤ 2 log n",
color=COL_TEXT, fontsize=11)
ax.set_xticks(hs)
ax.set_xlim(-0.3, hs[-1] + 0.3)
ax.legend(loc="upper left", fontsize=9, framealpha=0.92)
seq = [fib_tree_min_nodes(h) for h in range(8)]
assert seq == [1, 2, 4, 7, 12, 20, 33, 54]
ft = build_fibonacci_tree(4)
assert ft.height == 4 and ft.size == fib_tree_min_nodes(4) == 12
assert avl_to_list(ft) == list(range(12))
assert check_avl_invariants(ft)
for _hh in range(8):
assert fib_tree_min_nodes(_hh) >= 2.0 ** (_hh / 2.0)
hs = list(range(8))
nh_vals = [fib_tree_min_nodes(h) for h in hs]
fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.0, 6.4),
gridspec_kw={"width_ratios": [1.18, 1.0]})
fig.patch.set_facecolor(COL_WHITE)
_fh_draw_tree(axL, ft)
_fh_draw_growth(axR, hs, nh_vals)
fig.suptitle(
"En az dengeli AVL = Fibonacci ağacı → yükseklik h ≤ 2 log n",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985)
box = FancyBboxPatch(
(0.085, 0.015), 0.83, 0.085,
boxstyle="round,pad=0.01,rounding_size=0.012",
transform=fig.transFigure, facecolor=COL_BG, edgecolor=COL_ACCENT,
linewidth=1.8, zorder=0, clip_on=False)
fig.add_artist(box)
fig.text(0.5, 0.058,
"Nₕ = Nₕ₋₁ + Nₕ₋₂ + 1 (Fibonacci-benzeri) → düğüm sayısı h'de "
"ÜSTEL → h ≤ 2 log n",
ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold")
fig.text(0.5, 0.030,
"h adımda düğüm sayısı en az ikiye katlanır (her 2 seviyede) — "
"tersi: yükseklik logaritmik (Demaine 42:09)",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic")
fig.subplots_adjust(left=0.055, right=0.975, top=0.90, bottom=0.16, wspace=0.20)
plt.show()
```
::: {.callout-tip title="Builder Notu — Üstel Düğüm = Logaritmik Yükseklik"}
Bu, analiz disiplininin saf bir örneğidir: *bir yapının yükseklik garantisi, "en kötü durumda en az kaç düğüm gerekir" sorusunu cevaplamaktan gelir.*
- **Mantık zinciri:** "yükseklik $h$ için minimum düğüm $N_h$ üstel" ⟹ "$n$ düğüm en çok logaritmik yükseklik üretir". Üstel alt sınır (düğüm tarafında) doğrudan logaritmik üst sınıra (yükseklik tarafında) çevrilir.
- **Aynı kalıp her yerde:** ikili arama ağacının $\Omega(\log n)$ karşılaştırma alt sınırı (karar ağacı yaprak sayısı $\ge n+1$), heap'in $\log n$ yüksekliği, B-tree'nin $\log_B n$ derinliği — hepsi "az düğümle çok yükseklik yapılamaz" argümanının çeşitlemeleridir.
- **Builder dersi:** Bir veri yapısının hız garantisini ispatlamak istiyorsan, çoğu zaman doğrudan zamanı değil, **boyut/yükseklik arasındaki üstel ilişkiyi** sınırlarsın.
Tek cümle: *"$h \le 2 \log n$" bir hesaplama değil, bir sayma argümanıdır — en az dengeli ağacın bile üstel düğüm istemesi, yüksekliği logaritmaya hapseder.*
:::
## Yükseklik de Bir Alt Ağaç Özelliği {#sec-yukseklik-ozellik}
Dengeyi kontrol etmek için her düğümün yüksekliğini bilmeliyiz. İyi haber: **yükseklik bir alt ağaç özelliğidir**:
$$\texttt{node.height} = 1 + \max(\texttt{node.left.height}, \texttt{node.right.height})$$
> *"node.height equals 1 plus max of node.left.height and node.right.height."* — Demaine, 43:33
Bu da $O(1)$ güncelleme kuralıdır → her düğümün yüksekliğini (ve dolayısıyla skew'ini) zenginleştirmeyle tutabiliriz. (Rotasyon sırasında da etkilenen düğümlerin yükseklik/size alanları güncellenmelidir.)
## Rotasyonlarla Dengeyi Koruma {#sec-denge-koruma}
Insert/delete bir yaprak ekler/siler → bazı ataların skew'i $\pm 2$ olabilir (denge bozulur). Ata yolunu **alttan yukarı** kontrol et, **en alttaki dengesiz düğümü** $x$ bul (skew $= \pm 2$). Yaprak değişimi yüksekliği yalnızca 1 değiştirdiğinden, bozulma da tam $\pm 2$'dir. $y = x$'in (yüksek taraftaki) çocuğu olsun; üç durum:
- **Durum 1-2 (skew(y) = +1 veya 0):** Tek rotasyon ($x$ üzerinde) dengeyi geri getirir.
- **Durum 3 (skew(y) = −1):** Tek rotasyon işi kötüleştirir; **çift rotasyon** gerekir (önce $z = y$'nin çocuğu üzerinde, sonra $x$ üzerinde). Ezberlenmesi gereken tek özel durum budur.
Her düzeltme $O(1)$ (sabit sayıda işaretçi); ama bir düzeltme kökün yüksekliğini değiştirebileceğinden, yukarı çıkıp parent'ı da kontrol ederiz (ve zenginleştirmeleri güncelleriz). Toplam **$O(h) = O(\log n)$** sonra yükseklik dengesi geri gelir; böylece tüm işlemler **$O(\log n)$** olur.
@fig-rebalance-case3 Durum 3'ü deterministik bir senaryoda ($x = 10$, $y = 30$, $z = 20$; skew(x) $= +2$, skew(y) $= -1$) üç karede gösterir: tek rotasyonun neden yetmediği, sonra çift rotasyonun ($z$ sonra $x$) dengeyi nasıl geri getirdiği — traversal $[5, 10, 15, 20, 25, 30, 40]$ üç karede de değişmez.
```{python}
#| label: fig-rebalance-case3
#| fig-cap: "Durum 3 — tek rotasyon yetmez: çift rotasyon, right_rotate(30) → left_rotate(10) (L7 §10, İMZA figür). Deterministik build_case3_tree (motordan): skew(x = 10) = +2, skew(y = 30) = −1. **Kare 1 (başlangıç):** x = 10 kök, skew = +2 (kalın slate çerçeve = İHLAL); sağ çocuk y = 30, skew = −1; x SAĞA ağır ama y SOLA ağır → tek rotasyon yetmez. **Kare 2 (adım 1):** right_rotate(y = 30) sonrası — z = 20 yukarı geldi, 30 onun SAĞINA indi; artık 10 ve sağ çocuk 20 aynı yöne ağır. **Kare 3 (adım 2):** left_rotate(x = 10) sonrası — z = 20 KÖK (amber dolgu), 10 ve 30 çocukları, ağaç dengeli (DENGE GERİ GELDİ). HER karenin altında AYNI in-order şeridi [5, 10, 15, 20, 25, 30, 40]. Tek left_rotate(10) işi KÖTÜLEŞTİRİRDİ — ezberlenecek tek özel durum (Demaine Durum 3); motor doğrulaması: rebalance_node sonrası kök 20, check_avl_invariants True."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-rebalance-case3 (L7 §10 İMZA): Durum 3 çift rotasyon, 3 kare.
# Veri MOTORDAN (build_case3_tree / right_rotate / rebalance_node / avl_to_list).
_RB_R = 0.30
_RB_X_GAP = 0.78
_RB_Y_GAP = 1.20
_RB_INORDER = [5, 10, 15, 20, 25, 30, 40]
_RB_XPOS = {v: i for i, v in enumerate(_RB_INORDER)}
def _rb_coords(item, depth, x_off, y_top):
return x_off + _RB_XPOS[item] * _RB_X_GAP, y_top - depth * _RB_Y_GAP
def _rb_walk(node, depth, acc, depths):
depths[node.item] = depth
for child in (node.left, node.right):
if child is not None:
acc.append((node.item, child.item))
_rb_walk(child, depth + 1, acc, depths)
def _rb_draw_tree(ax, root, x_off, y_top, *,
fill_items=None, frame_items=None, hot_edges=None):
fill_items = set(fill_items or [])
frame_items = set(frame_items or [])
hot_edges = set(hot_edges or [])
edges = []
depths = {}
_rb_walk(root, 0, edges, depths)
for (pa, ch) in edges:
px, py = _rb_coords(pa, depths[pa], x_off, y_top)
cx, cy = _rb_coords(ch, depths[ch], x_off, y_top)
hot = frozenset((pa, ch)) in hot_edges
ax.plot([px, cx], [py, cy],
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=3.0 if hot else 1.6,
zorder=2 if hot else 1, solid_capstyle="round")
for item, depth in depths.items():
x, y = _rb_coords(item, depth, x_off, y_top)
if item in fill_items:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.8, COL_AMBER_700
elif item in frame_items:
fc, ec, lw, tcol = COL_WHITE, COL_PRIMARY, 3.0, COL_TEXT
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.6, COL_TEXT
ax.add_patch(Circle((x, y), _RB_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, str(item), ha="center", va="center",
fontsize=11, color=tcol, weight="bold", zorder=6)
return depths
def _rb_skew_label(ax, item, depths, x_off, y_top, text, color):
x, y = _rb_coords(item, depths[item], x_off, y_top)
ax.text(x + _RB_R + 0.10, y + _RB_R + 0.04, text, ha="left", va="bottom",
fontsize=8.5, color=color, weight="bold", zorder=7)
def _rb_rotation_arrow(ax, item_top, item_to, depths, x_off, y_top, label):
tx, ty = _rb_coords(item_top, depths[item_top], x_off, y_top)
bx, by = _rb_coords(item_to, depths[item_to], x_off, y_top)
ax.add_patch(FancyArrowPatch(
(tx, ty), (bx, by), arrowstyle="-|>", mutation_scale=16,
color=COL_AMBER_700, linewidth=2.6, zorder=8,
shrinkA=_RB_R * 64, shrinkB=_RB_R * 64,
connectionstyle="arc3,rad=-0.4"))
mx, my = (tx + bx) * 0.5, (ty + by) * 0.5
ax.text(mx, my + 0.28, label, ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=9)
def _rb_strip(ax, values, x_off, y_strip, *, tag=None):
sw = _RB_X_GAP
for k, v in enumerate(values):
x = x_off + k * sw
ax.add_patch(FancyBboxPatch(
(x, y_strip), sw * 0.86, 0.46, boxstyle="square,pad=0.0",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.3, zorder=3))
ax.text(x + sw * 0.43, y_strip + 0.23, str(v), ha="center", va="center",
fontsize=8.5, color=COL_TEXT, weight="bold", zorder=5)
if tag is not None:
ax.text(x_off + len(values) * sw * 0.5 - sw * 0.07, y_strip - 0.26, tag,
ha="center", va="center", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=5)
def _rb_title(ax, x_center, y_title, text, sub=None):
ax.text(x_center, y_title, text, ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=10)
if sub is not None:
ax.text(x_center, y_title - 0.36, sub, ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=10)
src = build_case3_tree()
sk_x = skew(src)
sk_y = skew(src.right)
before = avl_to_list(src)
assert sk_x == 2 and sk_y == -1 and before == [5, 10, 15, 20, 25, 30, 40]
t1 = build_case3_tree()
t2 = build_case3_tree(); right_rotate(t2.right)
assert t2.item == 10 and t2.right.item == 20 and t2.right.right.item == 30
assert avl_to_list(t2) == before
t3 = rebalance_node(build_case3_tree())
after = avl_to_list(t3)
assert t3.item == 20 and after == before and check_avl_invariants(t3)
assert t3.left.item == 10 and t3.right.item == 30
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
panel_span = (len(_RB_INORDER) - 1) * _RB_X_GAP
gap_between = 1.9
x_off1 = 0.0
x_off2 = panel_span + gap_between
x_off3 = 2 * (panel_span + gap_between)
y_top = 0.0
cx1 = x_off1 + panel_span * 0.5
cx2 = x_off2 + panel_span * 0.5
cx3 = x_off3 + panel_span * 0.5
y_title = y_top + 1.95
y_note = y_top + 1.02
y_strip = y_top - 3 * _RB_Y_GAP - 0.90
d1 = _rb_draw_tree(ax, t1, x_off1, y_top,
frame_items={10}, hot_edges={frozenset((10, 30))})
_rb_skew_label(ax, 10, d1, x_off1, y_top, f"skew=+{sk_x} (İHLAL)", COL_AMBER_700)
_rb_skew_label(ax, 30, d1, x_off1, y_top, f"skew={sk_y}", COL_SLATE_500)
_rb_title(ax, cx1, y_title, "Kare 1 — başlangıç",
sub=f"x=10 SAĞA ağır (skew=+{sk_x}) · ama y=30 SOLA ağır (skew={sk_y})")
ax.text(cx1, y_note, "Durum 3: x sağa ağır AMA y sola ağır\n→ tek rotasyon yetmez",
ha="center", va="center", fontsize=8.0, color=COL_AMBER_700,
weight="bold", zorder=10, linespacing=1.3)
_rb_strip(ax, before, x_off1, y_strip, tag="in-order (sıra korunur)")
d2 = _rb_draw_tree(ax, t2, x_off2, y_top,
fill_items={20},
hot_edges={frozenset((20, 30)), frozenset((10, 20))})
_rb_rotation_arrow(ax, 30, 20, d2, x_off2, y_top, "")
_rb_title(ax, cx2, y_title, "Kare 2 — adım 1: right_rotate(y=30)",
sub="z=20 yukarı geldi · 30 onun SAĞINA indi")
ax.text(cx2, y_note,
"artık 10 ve sağ çocuk 20 aynı yöne (sağa) ağır\n→ tek left_rotate hazır",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=10, linespacing=1.3)
_rb_strip(ax, avl_to_list(t2), x_off2, y_strip, tag="in-order (sıra korunur)")
d3 = _rb_draw_tree(ax, t3, x_off3, y_top,
fill_items={20},
hot_edges={frozenset((20, 10)), frozenset((20, 30))})
_rb_title(ax, cx3, y_title, "Kare 3 — adım 2: left_rotate(x=10)",
sub="z=20 KÖK · 10 ve 30 çocukları · ağaç dengeli")
ax.add_patch(FancyBboxPatch(
(cx3 - 1.55, y_note - 0.23), 3.1, 0.46,
boxstyle="round,pad=0.04,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=9))
ax.text(cx3, y_note, "DENGE GERİ GELDİ ✓", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=10)
_rb_strip(ax, after, x_off3, y_strip, tag="in-order (sıra korunur)")
for sep_x in (x_off1 + panel_span + gap_between * 0.5,
x_off2 + panel_span + gap_between * 0.5):
ax.plot([sep_x, sep_x], [y_strip - 0.2, y_title + 0.25],
color=COL_SLATE_400, linewidth=1.0, linestyle=(0, (3, 3)), zorder=0)
fig.suptitle(
"Durum 3 — tek rotasyon yetmez: çift rotasyon "
"(right_rotate(30) → left_rotate(10))",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ax.text((x_off1 + x_off3 + panel_span) * 0.5, y_strip - 0.78,
"tek left_rotate(10) işi KÖTÜLEŞTİRİRDİ — ezberlenecek tek özel durum "
"(Demaine Durum 3) · traversal [5,10,15,20,25,30,40] üç karede de DEĞİŞMEZ",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=10)
ax.set_xlim(x_off1 - 0.8, x_off3 + panel_span + 0.8)
ax.set_ylim(y_strip - 1.15, y_title + 0.5)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Bu Dersin Özeti {#sec-ozet-d10}
1. **Dizi ağacı**: `subtree_at` ile $i$. öğe; $n_\ell$ = `node.left.size` ile boyut-temelli ikili arama; $O(h)$.
2. **Alt ağaç zenginleştirme**: çocuklardan $O(1)$ hesaplanan özellik (`size`, `height`); insert/delete sonrası ata yolunu güncelle.
3. **Tutulabilir**: sum/min/max/size (aşağı-bakan); **tutulamaz**: index/depth (global).
4. **Rotasyon**: traversal sırasını koruyarak ($A, X, B, Y, C$) yeniden dengeleme aracı.
5. **AVL / skew** $\in \{-1, 0, +1\}$: yükseklik dengesi.
6. **Yükseklik dengesi → $h \le 2 \log n$**: $N_h$ Fibonacci-benzeri, üstel; $h$ logaritmik.
7. **Dengeyi koru**: en alttaki dengesiz düğümde 1 veya 2 rotasyon; $O(\log n)$.
::: {.callout-important title="Tek Bir Cümle"}
İkili ağaca `size`/`height` zenginleştirmesi ekleyip, AVL skew kuralını rotasyonla korursak, $h = O(\log n)$ garanti olur ve tüm sequence/set işlemleri $O(\log n)$'e iner.
:::
## Kontrol Soruları {#sec-sorular-d10}
::: {.callout-note collapse="true" title="Soru 1: İndeks (index) neden bir alt ağaç özelliği değildir, ama size öyledir?"}
**Cevap:**
`size` *aşağı bakar*: bir düğümün boyutu yalnızca çocuklarının boyutlarından (`node.left.size + node.right.size + 1`) hesaplanır; başka bir yere düğüm eklemek bu alt ağacı değiştirmez. İndeks ise *globaldir*: bir düğümün indeksi, solundaki tüm düğümlere (alt ağaç dışındakiler dahil) bağlıdır; başa tek bir ekleme tüm indeksleri kaydırır. Sadece aşağı-bakan özellikler, ata yolunu $O(h)$'de güncelleyerek korunabilir.
:::
::: {.callout-note collapse="true" title="Soru 2: Rotasyon traversal sırasını nasıl korur? right_rotate örneğiyle açıkla."}
**Cevap:**
$y$'nin sol çocuğu $x$, alt ağaçlar $A$ ($x$'in solu), $B$ ($x$'in sağı), $C$ ($y$'nin sağı) olsun. Rotasyon öncesi traversal: $A, X, B, Y, C$. `right_rotate(y)` sonrası $x$ yukarı, $y$ aşağı geçer; $B$, $y$'nin soluna bağlanır — ama traversal yine $A, X, B, Y, C$'dir. Sıra korunduğu için BST/sequence anlamı bozulmaz; yalnızca düğümlerin *derinlikleri* değişir, bu da dengeleme imkânı verir.
:::
::: {.callout-note collapse="true" title="Soru 3: AVL ağacında h ≤ 2 log n olduğunu kabaca nasıl gösteririz?"}
**Cevap:**
En az dengeli AVL ağacında (her düğüm skew $\pm 1$) yükseklik $h$ için minimum düğüm $N_h = N_{h-1} + N_{h-2} + 1$ (Fibonacci benzeri). $N_{h-1} \ge N_{h-2}$ olduğundan $N_h > 2 \cdot N_{h-2}$ → $N_h \ge 2^{h/2}$. Düğüm sayısı $h$'de üstel olduğundan, $h$ düğüm sayısında logaritmiktir: $h \le 2 \log n$. Yani en kötü AVL ağacı bile, optimumun en çok iki katı yüksekliktedir.
:::
::: {.callout-note collapse="true" title="Soru 4: Bir insert sonrası dengesizlik (skew = ±2) neden yalnızca ata yolunda aranır ve neden en fazla 1-2 rotasyon yeter?"}
**Cevap:**
Yükseklik bir alt ağaç özelliği olduğundan, bir yaprak eklendiğinde yalnızca o yaprağın **ataları**nın yüksekliği (ve skew'i) değişebilir — diğer alt ağaçlar dokunulmaz. Bu ata yolu $O(\log n)$ uzunluğundadır. Yaprak ekleme yüksekliği yalnızca 1 değiştirir, dolayısıyla bozulma tam $\pm 2$'dir; en alttaki dengesiz düğümde tek (Durum 1-2) ya da çift (Durum 3) rotasyon dengeyi geri getirir. Yukarı çıkarken her atayı kontrol ederiz, ama her biri sabit sayıda rotasyon ister → $O(\log n)$.
:::
## Egzersizler {#sec-egzersizler-d10}
**Egzersiz 1.** Bir dizi ağacında `subtree_at(node, i)` algoritmasını, $n_\ell$ = `node.left.size` kullanarak elle bir örnek üzerinde yürüt ($i < n_\ell$, $i = n_\ell$, $i > n_\ell$ üç durumunu da göster).
**Egzersiz 2.** `node.size` güncelleme kuralının insert (yaprak ekleme) sonrası neden yalnızca $O(h)$ atayı etkilediğini tümevarımla göster.
**Egzersiz 3.** "Alt ağaçtaki maksimum anahtar" bir alt ağaç özelliği midir? Güncelleme kuralını yaz. "Alt ağaçtaki ikinci en küçük anahtar" için ne olur?
**Egzersiz 4.** Python'da bir AVL düğümü için `height` ve `skew` güncellemesini yaz:
```python
def update(node):
lh = node.left.height if node.left else -1
rh = node.right.height if node.right else -1
node.height = 1 + max(lh, rh)
node.skew = rh - lh
```
**Egzersiz 5.** AVL'de Durum 3 (skew(y) = −1) neden tek rotasyonla çözülmez? Çift rotasyonun (önce $z$ üzerinde, sonra $x$ üzerinde) traversal sırasını koruduğunu, iki tekil rotasyona indirgenerek olduğunu açıkla.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-d10}
**Ders 12 (L8): İkili Yığınlar (Binary Heaps)**
Erik Demaine ile, **öncelik kuyruğu (priority queue)** arayüzüne ve onu çözen **ikili yığına** geçiyoruz: en büyük (veya en küçük) öğeyi $O(\log n)$'de çek/ekle. AVL'nin tam gücüne gerek olmayan, diziye gömülü zarif bir dengeli-ağaç. (Not: ders akışında araya **Problem Oturumu 4** girer — kitap düzeninde bu, araya giren **Ders 11 (PS4)**'tür; İkili Yığınlar onu izleyen **Ders 12**'dir.)
::: {.callout-warning title="Ders 12 (L8) Öncesi Yapılacak"}
- Bu dersin egzersizlerini, özellikle **Egzersiz 4**'ü (AVL update) çöz.
- Üç fikri (subtree_at, augmentation, rotation) ve nasıl $O(\log n)$ verdiklerini ezberden anlat.
- Ana cümleyi tekrar oku: *"AVL skew kuralını rotasyonla korursak, $h = O(\log n)$ garanti olur."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d10}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **subtree_at(node, i)** | $i$. öğe; $n_\ell$ ile boyut-temelli ikili arama; $O(h)$ | Böl. 3 |
| **Alt ağaç özelliği** | Çocuklardan $O(1)$ hesaplanan, aşağı-bakan nicelik | Böl. 4 |
| **size güncelleme** | `node.size = node.left.size + node.right.size + 1` | Böl. 4 |
| **Tutulamaz** | index, depth (global; tüm ağaca bağlı) | Böl. 5 |
| **Rotasyon** | Traversal'ı ($A, X, B, Y, C$) koruyan dengeleme | Böl. 6 |
| **skew** | height(sağ) − height(sol); AVL: skew $\in \{-1, 0, +1\}$ | Böl. 7 |
| **Yükseklik dengesi** | $N_h$ Fibonacci-benzeri üstel → $h \le 2 \log n$ | Böl. 8 |
| **Dengeyi koru** | En alttaki dengesizde 1-2 rotasyon; $O(\log n)$ | Böl. 10 |
## Builder ve OMSCS Bağlantıları {#sec-baglantilar-d10}
::: {.callout-tip title="6 köprü"}
Bu ders, "dengeyi nasıl garanti ederiz ve zenginleştirme ile ne kazanırız" sezgisini kurar — köprülerin özeti:
1. **Dengeli ağaç (AVL/red-black)** → veritabanı indeksleri ve dosya sistemleri (B-tree, B+-tree): disk-dostu denge; çoğu SQL motorunun varsayılan indeksi bir dengeli ağaçtır (hash/GIN gibi özel türler ayrı uzmanlık).
2. **Subtree augmentation (`size`)** → order-statistics tree: "rank(x)" ve "$k$. en küçük" sorguları $O(\log n)$.
3. **Rotasyon** → tüm kendini-dengeleyen ağaçların (red-black, splay, treap) ortak ilkel işlemi.
4. **Aşağı-bakan vs global özellik** → genel tasarım: bir niceliği verimli tutmak, onun yerel (kompozisyonel) olmasına bağlıdır.
5. **Fibonacci → log yükseklik** → analiz disiplini: bir yapının garantisi, en kötü durum boyutunu (üstel düğüm) sınırlamaktan gelir.
6. **Traversal sırası = değişmez** → her ağaç işleminin doğruluğu, korunan bir değişmezle (sıra, BST özelliği) ispatlanır.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
İkili ağaç tek başına $O(h)$'dir; onu güçlü kılan iki ekleme — `size`/`height` **zenginleştirmesi** ($i$. öğe, denge bilgisi) ve **rotasyon** (sırayı bozmadan dengeleme). AVL skew kuralı bunları birleştirip $h = O(\log n)$ garanti eder; gerisi her yerde $O(\log n)$'dir.
:::
