---
title: "Problem Oturumu 4"
subtitle: "Ders 9-10'un uygulaması: AVL ağaçlarının dört uygulaması — çift rotasyonlu silme, öncelik kuyruğu ve kayan pencere, çoklu yapı ve cross-linking, iç içe ağaçlar ve rank sorgusu"
---
::: {.callout-note title="Oturum bilgisi"}
- **Ku'nun videosu:** [YouTube — Problem Session 4](https://www.youtube.com/watch?v=MAyraVVYB64) (≈60 dk)
- **OCW sayfası:** [MIT 6.006 Problem Session 4](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/problem-session-4/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 11 (Problem Oturumu 4)
- **Hoca:** Jason Ku
- **Okuma süresi:** ≈26 dk
:::
## Bu Problem Oturumu Ne Hakkında? {#sec-hakkinda-d11}
Dördüncü problem oturumu (Jason Ku) **ikili ağaçların** (AVL) uygulamalarına odaklanır; yanında bir de **ikili yığın (binary heap)** önizlemesi yapar. Yığın henüz işlenmedi — Problem 2'de bir **kara kutu** olarak kullanılır ve onu açan ders, kitap düzeninde bu oturumu izleyen **Ders 12 (L8)**'dir. Bu hafta Demaine'in set/sequence veri yapısı tablosu tamamlandı; AVL ağacı hemen her işlemde **$O(\log n)$** ile dengeli bir performans verir.
> *"Welcome to our fourth problem session. We're going to be talking about binary trees mostly, today."* — Ku, 0:21
Tüm oturuma damga vuran genel ders şudur (@fig-concept-map): her veri yapısı probleminde önce **ne sakladığını** ve hangi **değişmezleri (invariant)** koruduğunu söyle; sonra dinamik işlemler bu değişmezleri korur, sorgular onlara dayanır. Dört problem birer "İfade → Yaklaşım → Çözüm → Karmaşıklık" akışıyla işlenir.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Problem Oturumu 4'ün kavram haritası: kök (PS4) dört probleme dallanır ve ortadaki ortak ilke düğümü her dördünü birden yönlendirir. Problem 1 sequence AVL'de çift rotasyonlu silme yapar (height ve size birlikte); Problem 2 mutlak değerce en güçlü k görüşü öncelik kuyruğuyla, sonra log n bellekle kayan pencerede bulur; Problem 3 müzayedede çoklu yapıyı cross-linking ile bağlar ve toplamı zenginleştirme olarak tutar; Problem 4 oyuncu performanslarını iç içe ağaçlarda tutup k. en yükseği rank sorgusuyla çeker. Ortadaki ilke — önce ne sakladığını, sonra hangi değişmezleri koruduğunu söyle — Ku'nun her probleme aynı kapıdan girmesini sağlar."
flowchart TD
R["Problem Oturumu 4<br/>(Ders 9-10 uygulaması)"] --> P1["Problem 1<br/>Sequence AVL silme<br/>(çift rotasyon)"]
R --> P2["Problem 2<br/>En güçlü görüşler<br/>(öncelik kuyruğu + kayan pencere)"]
R --> P3["Problem 3<br/>Müzayede<br/>(çoklu yapı + cross-linking)"]
R --> P4["Problem 4<br/>Receiver roster<br/>(iç içe ağaç + rank)"]
CORE["Ortak ilke:<br/>önce NE saklıyorsun<br/>sonra hangi DEĞİŞMEZ korunuyor"]
CORE -.-> P1
CORE -.-> P2
CORE -.-> P3
CORE -.-> P4
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef prob fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef core fill:#fcd34d,stroke:#b45309,stroke-width:2px,color:#1f2937
class R root
class P1,P2,P3,P4 prob
class CORE core
```
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 11 (PS4) motoru (_engine_PS4.py) + D9/D10 AVL altyapısı
# (_engine.py) + Slate+Amber sabitleri (_viz.py). Bu hücre gizlidir
# (#| echo: false). Aşağıdaki TÜM figür hücreleri bu hücrede tanımlanan
# sınıf/fonksiyonları (avl_insert_counting, seq_avl_delete_at, TopKTree,
# AuctionHouse, build_fibonacci_tree, fib_tree_min_nodes ...) + COL_*
# globallerini IMPORT ETMEDEN kullanır. Notion'daki öğretim içeriği (görünür
# display python blokları) 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/§11). Standalone testte
# savefig kullanılır; Quarto render'da jupyter inline backend'i ayarlar.
#
# Dosyadan import YOK: tüm AVL altyapısı + 4 problem sınıfı burada self-contained
# inline'dır → render dizininden bağımsız (kurs paritesi: PS3/08 emsali, düz INLINE).
# ============================================================================
from fractions import Fraction
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyArrowPatch, FancyBboxPatch
from matplotlib.path import Path
from matplotlib.patches import PathPatch
# ---------------------------------------------------------------------------
# _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 (aktif düğüm / yeni öğe / parmak)
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / callout / kutu dolgusu
# Türev amber tonları
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)
# Türev slate tonları
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# ===========================================================================
# D9/D10 AVL ALTYAPISI (_engine.py'den birebir; PS4 motoru bunları import eder,
# burada INLINE). AVLNode + güncelleme/skew/rotasyon/rebalance + insert/delete +
# subtree yardımcıları + predecessor/successor + Fibonacci ağacı.
# ===========================================================================
class AVLNode:
"""AVL düğümü (L7): item + parent/left/right + (height, size)."""
__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 _h(node):
"""Boş alt ağaç yüksekliği −1 (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ı (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)."""
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):
"""x = y.left yukarı, y aşağı; B = x.right, y'nin soluna geçer. O(1)."""
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)
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. Durum 3 (zor): çift rotasyon."""
if skew(x) == 2:
y = x.right
if skew(y) < 0: # Durum 3 — önce sağ çocukta ters rotasyon
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 subtree_first(node):
"""Alt ağacın traversal sırasındaki İLK düğümü (sola sonuna dek). O(h)."""
while node.left is not None:
node = node.left
return node
def subtree_last(node):
"""Alt ağacın traversal sırasındaki SON düğümü (sağa sonuna dek). O(h)."""
while node.right is not None:
node = node.right
return node
def successor(node):
"""Traversal sırasında node'dan SONRAKİ düğüm. 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):
"""Traversal sırasında node'dan Ö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 maintain_up(node):
"""Yaprak değişiminden köke: güncelleme + gerekirse rebalance. O(log n)."""
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. 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 avl_delete(root, k):
"""Set-AVL delete: bul, item-takasla yaprağa indir, kopar, maintain_up. 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: nₗ = sol.size ile boyut-temelli ikili arama. 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 avl_to_list(root):
"""In-order item listesi."""
if root is None:
return []
return avl_to_list(root.left) + [root.item] + avl_to_list(root.right)
def fib_tree_min_nodes(h):
"""Nₕ = Nₕ₋₁ + Nₕ₋₂ + 1: yükseklik h'li EN AZ düğümlü AVL."""
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ç; 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)
# ===========================================================================
# _engine_PS4.py — PS4 problem motoru (D9/D10 üstüne; INLINE).
# ===========================================================================
# --- Problem 1: sequence AVL silme + rebalance OLAYI sayımı (Ku 24:34) ---
def maintain_up_counting(node):
"""maintain_up'ın sayaçlı kopyası: kaç düğümde |skew|=2 onarımı yapıldı?
Döndürür: (yeni kök, rebalance olay sayısı)."""
events = 0
last = node
while node is not None:
update_node(node)
if abs(skew(node)) == 2:
node = rebalance_node(node)
events += 1
last = node
node = node.parent
return last, events
def seq_avl_delete_at(root, i):
"""Sequence-AVL delete_at(i): subtree_at ile bul, item-takasla yaprağa indir,
kopar, ata yolunda dengele. O(log n). Döndürür: (kök, silinen, olay sayısı)."""
node = subtree_at(root, i)
removed = node.item
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
if parent is not None:
if parent.left is node:
parent.left = None
else:
parent.right = None
node.parent = None
new_root, events = maintain_up_counting(parent)
return new_root, removed, events
return None, removed, 0
def avl_insert_counting(root, k):
"""avl_insert'in sayaçlı kopyası: (yeni kök, rebalance olay sayısı).
Ku iddiasının tanığı: olay sayısı HER insert'te ≤ 1."""
new = AVLNode(k)
if root is None:
return new, 0
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_counting(new)
# --- Problem 2: priority queue / binary heap (kara kutu) + k-en-iyi AVL ---
class TopKTree:
"""k-en-iyi KAYAN set-AVL (log n bellek): kapasite k; her yeni öğe eklenir,
taşarsa EN KÜÇÜK silinir. DEĞİŞMEZ (Ku 48:14): ağaç her an, o ana kadar
İŞLENENLERİN en büyük k tanesini tutar."""
def __init__(self, k):
self.k = k
self.root = None
self.n = 0
def process(self, value):
self.root = avl_insert(self.root, value)
self.n += 1
if self.n > self.k:
smallest = subtree_first(self.root).item
self.root = avl_delete(self.root, smallest)
self.n -= 1
def contents(self):
return avl_to_list(self.root)
# --- Problem 3: müzayede: çoklu yapı + cross-linking + total ---
def bst_contains(root, key):
"""set-AVL üyelik testi (BST find, O(log n))."""
node = root
while node is not None:
if key == node.item:
return True
node = node.left if key < node.item else node.right
return False
class AuctionHouse:
"""new_bid/update_bid O(log n), get_revenue O(1). Dört bileşen (Ku 1:07:08):
bids sözlüğü + topk set-AVL + rest set-AVL + total zenginleştirmesi."""
def __init__(self, k):
self.k = k
self.bids = {}
self.topk = None
self.rest = None
self.topk_n = 0
self.total = 0
def _topk_insert(self, key):
self.topk = avl_insert(self.topk, key)
self.topk_n += 1
self.total += key[0]
def _topk_delete(self, key):
self.topk = avl_delete(self.topk, key)
self.topk_n -= 1
self.total -= key[0]
def _rebalance_sets(self):
while self.topk_n > self.k:
mn = subtree_first(self.topk).item
self._topk_delete(mn)
self.rest = avl_insert(self.rest, mn)
while self.topk_n < self.k and self.rest is not None:
mx = subtree_last(self.rest).item
self.rest = avl_delete(self.rest, mx)
self._topk_insert(mx)
while (self.topk is not None and self.rest is not None
and subtree_first(self.topk).item < subtree_last(self.rest).item):
lo = subtree_first(self.topk).item
hi = subtree_last(self.rest).item
self._topk_delete(lo)
self.rest = avl_delete(self.rest, hi)
self.rest = avl_insert(self.rest, lo)
self._topk_insert(hi)
def new_bid(self, bidder, amount):
if bidder in self.bids:
old = (self.bids[bidder], bidder)
if self.topk is not None and bst_contains(self.topk, old):
self._topk_delete(old)
else:
self.rest = avl_delete(self.rest, old)
self.bids[bidder] = amount
self._topk_insert((amount, bidder))
self._rebalance_sets()
update_bid = new_bid
def get_revenue(self):
return self.total
# --- Problem 4: receiver roster: iç içe yapı + çapraz-çarpım + rank ---
class Roster:
"""Oyuncu performansı = puan/oyun (Fraction = exact çapraz çarpım). k. en
yüksek performans O(log n): perf set-AVL'sinde size-rank → subtree_at."""
def __init__(self):
self.players = {}
self.perf = None
self.perf_n = 0
def _perf_key(self, pid):
p = self.players[pid]
ngames = len(p["games"])
if ngames == 0:
return None
return (Fraction(p["points"], ngames), pid)
def _detach(self, pid):
key = self._perf_key(pid)
if key is not None:
self.perf = avl_delete(self.perf, key)
self.perf_n -= 1
def _attach(self, pid):
key = self._perf_key(pid)
if key is not None:
self.perf = avl_insert(self.perf, key)
self.perf_n += 1
def add_game(self, pid, game_id, points):
if pid not in self.players:
self.players[pid] = {"points": 0, "games": {}}
self._detach(pid)
self.players[pid]["games"][game_id] = points
self.players[pid]["points"] += points
self._attach(pid)
def kth_best(self, k):
return subtree_at(self.perf, self.perf_n - k).item
```
## Problem 1: Sequence AVL — delete_at ve Çift Rotasyon {#sec-problem-1-d11}
**İfade.** Bir **sequence AVL ağacında** `delete_at(8)` (sıradaki 8. öğeyi sil) işlemini yürüt; sonucu yükseklik-dengeli tut.
::: {.callout-tip title="Yaklaşım — İki augmentation: height denge için, size sıra-indeksi için"}
Sequence AVL ağacı **iki** alanla zenginleştirilir: `height` (rotasyonlarda dengeyi kontrol için) ve `size` (sıra-indeksiyle arama için). 8. öğeyi `subtree_at` ile bul (her düğümde sol alt ağaç boyutuna bakarak in), sil, sonra ata yolunu yukarı çıkıp dengeyi rotasyonlarla onar. İki augmentation aynı düğümde yaşar ama farklı işe yarar: `size` *nereye ineceğini*, `height` *nasıl dengeleyeceğini* söyler.
:::
> *"Sequence AVL trees... are augmented by two things... I need to store heights... and the sequence requires me to store their subtree numbers."* — Ku, 10:29
**Çözüm.** Silme sonrası bir düğüm dengesizleşir (skew ±2). Bu, AVL'nin **zor durumudur** (Ders 10 Durum 3): düğüm sağa ağır ama sağ çocuğu sola ağır. Tek rotasyon işi tersine bozar; **çift rotasyon** gerekir — önce sağ çocukta sağ-rotasyon, sonra düğümde sol-rotasyon.
> *"I am badly skewed to the right but my right subtree is skewed to the left — I have to do a right rotation here, and then do a rotation."* — Ku, 15:53
Her rotasyonda yalnızca etkilenen 2-3 düğümün zenginleştirmesi (`height`, `size`) çocuklardan yeniden hesaplanır. Verilen ağaç bir **Fibonacci ağacıdır** — belli düğüm sayısı için en yüksek (en az dengeli) AVL; bu yüzden silme **logaritmik sayıda** rotasyon gerektirebilir. İlginç fark: insert her zaman *tek* bir denge işlemiyle (≤ 2 rotasyon içeren bir olay) düzelir; delete ata yolu boyunca log n ayrı olay isteyebilir.
> *"in a delete operation, it's possible that you have to do a logarithmic number of these rotations... An insertion operation will always re-balance after one re-balance operation."* — Ku, 24:34
@fig-delete-rotations bu farkı motordan **gerçek** verilerle gösterir: 400 rastgele ekleme boyunca her ekleme en çok **1 olayla** kapanır (sol panel); buna karşılık bir Fibonacci ağacında (h = 7, n = 54) en soldaki yaprağı silmek ata yolu boyunca tam **3 ardışık olay** doğurur (sağ panel) — silmenin kademeli (cascade) onarım yapabildiğinin somut tanığı. İkisi de toplam $O(\log n)$ zamandır, çünkü her olay $O(1)$'dir; fark, *olay sayısındadır*.
**Karmaşıklık.** `delete_at` **$O(\log n)$** (subtree_at ile bul + ata yolunda $O(\log n)$ rotasyon, her rotasyon $O(1)$).
```{python}
#| label: fig-delete-rotations
#| fig-cap: "AVL onarımı — insert TEK olay vs delete LOG N olay (Ku 24:34) — Problem 1 İMZA. SOL panel INSERT: küçük bir AVL'ye ekleme kökte skew=+2 (slate çerçeve, İHLAL) doğurur; TEK right_rotate olayıyla (amber yıldız) dengelenir — ekleme her zaman O(1) olayla kapanır. SAĞ panel DELETE: Fibonacci ağacı (h=7, n=54; mümkün en az dengeli AVL, her düğümde sağ alt-ağaç soldan tam 1 yüksek) sembolik kademe şeması; en soldaki yaprak silinince (kesik amber daire) ata yolu boyunca motordan GERÇEK 3 ardışık seviyede skew=±2 doğar → 3 amber yıldız (3 olay). Alt şerit: insert O(1) olay, delete O(log n) olay — ama her olay O(1) olduğundan ikisi de toplam O(log n) zaman; fark olay SAYISINDADIR. Sol paneldeki 400 rastgele eklemenin hiçbiri 1 olayı aşmaz (motor tanığı)."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-delete-rotations — PS4 Problem 1 İMZA: insert TEK olay vs delete LOG N olay.
# Veri MOTORDAN: avl_insert_counting (400 random insert, max olay ≤1) +
# seq_avl_delete_at(build_fibonacci_tree(7), 0) → 3 olay. Setup globalleri:
# plt, Circle, FancyArrowPatch, FancyBboxPatch, Path, PathPatch, COL_*,
# avl_insert_counting, seq_avl_delete_at, build_fibonacci_tree, fib_tree_min_nodes.
import random as _random
_R = 0.26
def _gather_engine_data():
"""ASSERT 1 (400 random insert, her olay ≤1) + ASSERT 2 (fib delete = 3 olay)."""
rng = _random.Random(11)
keys = rng.sample(range(5000), 400)
root = None
insert_max_ev = 0
insert_total_ev = 0
for k in keys:
root, ev = avl_insert_counting(root, k)
insert_max_ev = max(insert_max_ev, ev)
insert_total_ev += ev
h = 7
n = fib_tree_min_nodes(h)
fib = build_fibonacci_tree(h)
_nr, _rm, delete_events = seq_avl_delete_at(fib, 0)
return {
"insert_keys": len(keys), "insert_max_ev": insert_max_ev,
"insert_total_ev": insert_total_ev,
"fib_h": h, "fib_n": n, "delete_events": delete_events,
}
def _node(ax, x, y, label, *, fill=False, frame=False, r=_R, fs=10):
if fill:
fc, ec, lw, tc = COL_AMBER_100, COL_ACCENT, 2.6, COL_AMBER_700
elif frame:
fc, ec, lw, tc = COL_WHITE, COL_PRIMARY, 3.0, COL_TEXT
else:
fc, ec, lw, tc = COL_BG, COL_PRIMARY, 1.6, COL_TEXT
ax.add_patch(Circle((x, y), r, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=6))
if label is not None:
ax.text(x, y, str(label), ha="center", va="center",
fontsize=fs, color=tc, weight="bold", zorder=7)
def _edge(ax, x0, y0, x1, y1, *, hot=False):
ax.plot([x0, x1], [y0, y1],
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=3.0 if hot else 1.6,
zorder=3 if hot else 2, solid_capstyle="round")
def _star(ax, x, y, *, size=0.20, label=None):
ax.text(x, y, "★", ha="center", va="center", fontsize=15.5,
color=COL_ACCENT, weight="bold", zorder=9)
ax.add_patch(Circle((x, y), size, facecolor="none", edgecolor=COL_AMBER_700,
linewidth=1.6, zorder=8))
if label is not None:
ax.text(x + size + 0.06, y, label, ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=9)
def _draw_insert_panel(ax, x_off, y_top):
gx = 0.95
gy = 1.10
ya = y_top
n30 = (x_off + 1.3 * gx, ya)
n20 = (x_off + 0.7 * gx, ya - gy)
n10 = (x_off + 0.1 * gx, ya - 2 * gy)
_edge(ax, *n30, *n20, hot=True)
_edge(ax, *n20, *n10, hot=True)
_node(ax, *n30, 30, frame=True)
_node(ax, *n20, 20)
_node(ax, *n10, 10, fill=True)
ax.text(n30[0] + _R + 0.06, n30[1] + _R - 0.02, "skew=+2",
ha="left", va="bottom", fontsize=8, color=COL_AMBER_700,
weight="bold", zorder=9)
ax.text(n10[0], n10[1] - _R - 0.16, "YENİ", ha="center", va="top",
fontsize=7.5, color=COL_AMBER_700, weight="bold", zorder=9)
ax.text((n30[0] + n10[0]) * 0.5, ya + _R + 0.30, "ekleme sonrası",
ha="center", va="bottom", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=9)
arr_y = ya - gy
ax_from = n30[0] + gx + 0.10
ax_to = ax_from + 1.05
ax.add_patch(FancyArrowPatch(
(ax_from, arr_y), (ax_to, arr_y), arrowstyle="-|>", mutation_scale=16,
color=COL_AMBER_700, linewidth=2.4, zorder=8))
_star(ax, (ax_from + ax_to) * 0.5, arr_y + 0.40)
ax.text((ax_from + ax_to) * 0.5, arr_y + 0.74, "1 olay",
ha="center", va="bottom", fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=9)
ax.text((ax_from + ax_to) * 0.5, arr_y - 0.30, "right_rotate",
ha="center", va="top", fontsize=7.5, color=COL_SLATE_500,
style="italic", zorder=9)
xb = ax_to + 0.55
m20 = (xb + 0.7 * gx, ya - 0.5 * gy)
m10 = (xb + 0.2 * gx, ya - 1.5 * gy)
m30 = (xb + 1.2 * gx, ya - 1.5 * gy)
_edge(ax, *m20, *m10)
_edge(ax, *m20, *m30)
_node(ax, *m20, 20, fill=True)
_node(ax, *m10, 10)
_node(ax, *m30, 30)
ax.text(m20[0], ya + _R + 0.30, "dengeli ✓", ha="center", va="bottom",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=9)
return n10[0] - _R, m30[0] + _R
def _draw_delete_panel(ax, x_off, y_top, delete_events):
levels = delete_events + 2
gy = 0.82
spine = []
x0 = x_off + 3.1
for d in range(levels + 1):
x = x0 - d * 0.62
y = y_top - d * gy
spine.append((x, y))
def _triangle(cx, cy, w, hh, label=None, hot=False):
verts = [(cx, cy + 0.10), (cx + w * 0.5, cy - hh),
(cx - w * 0.5, cy - hh), (cx, cy + 0.10)]
codes = [Path.MOVETO, Path.LINETO, Path.LINETO, Path.CLOSEPOLY]
ax.add_patch(PathPatch(
Path(verts, codes),
facecolor=COL_AMBER_100 if hot else COL_BG,
edgecolor=COL_ACCENT if hot else COL_SLATE_400,
linewidth=1.8 if hot else 1.3, zorder=2))
if label is not None:
ax.text(cx, cy - hh * 0.58, label, ha="center", va="center",
fontsize=7, color=COL_SLATE_500, zorder=4)
for d in range(levels):
x, y = spine[d]
nx, ny = spine[d + 1]
_edge(ax, x, y, nx, ny, hot=True)
tx, ty = x + 0.95, y - gy * 0.55
_edge(ax, x, y, tx, ty + 0.30)
_triangle(tx, ty + 0.30, 1.05, 0.85,
label=("h−%d" % (d + 1)) if d < 3 else None)
for d in range(levels + 1):
x, y = spine[d]
is_leaf = (d == levels)
if is_leaf:
ax.add_patch(Circle((x, y), _R, facecolor=COL_WHITE,
edgecolor=COL_AMBER_700, linewidth=2.2,
linestyle=(0, (3, 2)), zorder=6))
ax.text(x, y, "✕", ha="center", va="center", fontsize=10,
color=COL_AMBER_700, weight="bold", zorder=7)
ax.text(x - _R - 0.10, y, "yaprak sil", ha="right", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=8)
elif d == 0:
_node(ax, x, y, None, frame=False)
ax.text(x + _R + 0.08, y + _R, "kök", ha="left", va="bottom",
fontsize=8, color=COL_SLATE_500, zorder=8)
else:
_node(ax, x, y, None, frame=True)
for j in range(delete_events):
d = levels - 1 - j
x, y = spine[d]
_star(ax, x - 0.42, y, label=None)
ax.text(spine[levels // 2][0] - 1.55, spine[levels // 2][1] + 0.05,
"ata yolu boyunca\n%d ardışık olay" % delete_events,
ha="right", va="center", fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=9, linespacing=1.3)
ax.text(spine[levels - 1][0] - 1.55, spine[levels - 1][1] - gy * 0.55,
"yol uzunluğu = ağaç yüksekliği\n≈ log n → ≤ log n olay",
ha="right", va="center", fontsize=8.5, color=COL_TEXT,
weight="bold", zorder=9, linespacing=1.3)
left_x = min(p[0] for p in spine) - _R - 0.2
right_x = x0 + 1.6
return left_x, right_x
_data = _gather_engine_data()
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
y_top = 0.0
ins_l, ins_r = _draw_insert_panel(ax, 0.0, y_top - 0.2)
del_off = ins_r + 1.3
del_l, del_r = _draw_delete_panel(ax, del_off, y_top + 0.1, _data["delete_events"])
ins_cx = (ins_l + ins_r) * 0.5
del_cx = (del_l + del_r) * 0.5
y_title = y_top + 0.95
ax.text(ins_cx, y_title, "INSERT — TEK denge olayı",
ha="center", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=10)
ax.text(ins_cx, y_title - 0.34,
"ekleme her zaman tek olayla düzelir (≤ 2 rotasyon) → O(1) olay",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=10)
ax.text(del_cx, y_title, "DELETE — LOG N denge olayı",
ha="center", va="center", fontsize=11.5, color=COL_TEXT,
weight="bold", zorder=10)
ax.text(del_cx, y_title - 0.34,
"Fibonacci ağacı (h=%d, n=%d) tanığı → ata yolunda %d olay"
% (_data["fib_h"], _data["fib_n"], _data["delete_events"]),
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=10)
sep_x = (ins_r + del_l) * 0.5
y_low = y_top - 5.4
ax.plot([sep_x, sep_x], [y_low + 0.4, y_title + 0.2],
color=COL_SLATE_400, linewidth=1.0, linestyle=(0, (3, 3)), zorder=0)
strip_y = y_low + 0.55
strip_l = ins_l - 0.1
strip_r = del_r + 0.1
ax.add_patch(FancyBboxPatch(
(strip_l, strip_y - 0.05), strip_r - strip_l, 0.92,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.4, zorder=1))
cs_cx = (strip_l + strip_r) * 0.5
ax.text(cs_cx, strip_y + 0.58,
"insert: O(1) olay | delete: O(log n) olay — "
"ama HER olay O(1) → ikisi de toplam O(log n) zaman",
ha="center", va="center", fontsize=9.5, color=COL_TEXT,
weight="bold", zorder=4)
ax.text(cs_cx, strip_y + 0.18,
"Fibonacci ağacı = mümkün en az dengeli AVL (her düğümde sağ alt-ağaç "
"soldan tam 1 yüksek, skew +1) → delete cascade'inin worst-case tanığı",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=4)
fig.suptitle(
"AVL onarımı — insert TEK olay vs delete LOG N olay (Ku 24:34)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.985)
ax.set_xlim(strip_l - 0.5, strip_r + 0.5)
ax.set_ylim(y_low, y_title + 0.55)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Problem 2: En Güçlü Görüşler {#sec-problem-2-d11}
**İfade.** "Fick Nury" (Nick Fury), n kahramanın görüşlerini (güçlü-pozitif veya güçlü-negatif) içeren *salt-okunur* bir diziden, **mutlak değerce en güçlü log n** kahramanı bulmak ister. (a) doğrusal zamanda. (b) en fazla **log n ek bellek** kısıtıyla.
::: {.callout-tip title="Yaklaşım — (a) build O(n) yığın; (b) sabit-boyutlu küme + kayan pencere"}
(a) **Öncelik kuyruğu (priority queue)** — ikili yığının çözdüğü arayüz; build ve delete_max sunar. Yığın bu oturumda **kara kutu**dur (Ders 12'de açılır). (b) bellek kısıtı çıktı boyutuna (log n) bağlı bir yapıyı zorlar: en fazla log n öğelik bir set AVL ağacı + **kayan pencere** ile akışı bir kez gez, her an top-k'yı tut.
:::
> *"It's implementing what we call a priority queue interface... delete_max."* — Ku, 29:14
**Çözüm.**
**(a) İkili yığınla:** Tüm görüşlerin *mutlak değerini* bir diziye kopyala, ikili yığın olarak **build** et — $O(n)$. Sonra **delete_max**'i log n kez çağır — en güçlü log n görüşü çeker.
> *"a binary heap does build in linear time and delete_max in log n time."* — Ku, 35:13
İkili yığının zarafeti: build $O(n)$ (set AVL'nin $O(n \log n)$'inden iyi), delete_max $O(\log n)$. Toplam $O(n + \log n \cdot \log n)$ = $O(n + \log^2 n)$ = **$O(n)$** ($\log^2 n \ll n$).
```python
def strongest_opinions_heap(opinions, k): # (a) yığınla — O(n)
h = MaxHeap([abs(x) for x in opinions]) # build: O(n) (heapify)
return [h.delete_max() for _ in range(k)] # k = log n çekiş — O(log²n)
```
**(b) log n bellek + kayan pencere:** En fazla log n öğelik bir **set AVL ağacı** tut (yüksekliği log log n). İlk log n öğeyle doldur; sonra kalan her öğe için: ekle, sonra **en küçüğü** sil. Değişmez: ağaç her an *o ana kadar görülen* k = log n en güçlü görüşü tutar.
> *"the invariant I'm maintaining here is that my thing always has the k largest opinions of the ones that I've processed so far."* — Ku, 48:14
```python
class TopKTree: # (b) kayan pencere — O(log n) bellek
def process(self, value): # akıştan tek öğe
self.root = avl_insert(self.root, value)
self.n += 1
if self.n > self.k: # taştıysa
smallest = subtree_first(self.root).item
self.root = avl_delete(self.root, smallest) # en küçüğü düşür
self.n -= 1
```
@fig-topk-sliding bu izi akış $[5, 1, 8, 3, 9, 2, 7]$ ve k = 3 üzerinde motordan **gerçek** çalıştırarak gösterir: ağaç içeriği adım adım $[5] \to [1,5] \to [1,5,8] \to [3,5,8] \to [5,8,9] \to [5,8,9] \to [7,8,9]$ olur. Her adımda değişmez tutar — ağaç, o ana kadar görülenlerin tam olarak top-3'üdür (akışın 6. öğesi olan 2, mevcut minimum 5'ten küçük olduğundan girip hemen çıkar; içerik değişmez).
**Karmaşıklık.** (a) **$O(n)$** (ikili yığın). (b) **$O(n \log \log n)$** zaman (her öğe için log log n yükseklikli ağaca insert/delete), yalnızca **$O(\log n)$** bellek.
```{python}
#| label: fig-topk-sliding
#| fig-cap: "k-en-iyi kayan set-AVL + DEĞİŞMEZ (Ku 48:14) — Problem 2b İMZA. Akış $[5,1,8,3,9,2,7]$, k=3 motordan GERÇEK çalıştırılır. Üstte akış şeridi; altında 7 adım satırı: her satır o adımdan sonra ağaç içeriğini (sıralı mini-set), düşen öğeyi (gri daire + üzeri çizgi) ve kalıcı giren öğeyi (amber daire) gösterir. Sağdaki amber rozet DEĞİŞMEZİ doğrular: ağaç her an o ana kadar görülenlerin top-3'üdür (hepsi ✓). Akışın 6. öğesi olan 2, mevcut minimum 5'ten küçük olduğundan girip hemen çıkar → içerik [5,8,9] değişmez. Alt amber kutu: bellek O(k)=O(log n), öğe başına maliyet O(log k)=O(log log n)."
#| fig-width: 10.6
#| fig-height: 7.0
# fig-topk-sliding — PS4 Problem 2b İMZA: k-en-iyi kayan set-AVL + değişmez.
# Veri MOTORDAN: TopKTree(3) akış [5,1,8,3,9,2,7]. Düşen/giren önceki-sonraki
# içerik farkından türetilir. Setup globalleri: plt, Circle, FancyBboxPatch,
# COL_*, TopKTree.
_STREAM_CW, _STREAM_CH = 0.92, 0.74
_SET_CW, _SET_CH = 0.78, 0.62
_ROW_GAP = 1.18
_RC = 0.27
def _topk_trace(stream, k):
t = TopKTree(k)
prev = []
steps = []
for v in stream:
t.process(v)
cur = list(t.contents())
dropped_set = set(prev) - set(cur)
entered_set = set(cur) - set(prev)
steps.append({
"value": v, "contents": cur,
"dropped": next(iter(dropped_set)) if dropped_set else None,
"entered": next(iter(entered_set)) if entered_set else None,
})
prev = cur
return steps
def _stream_strip(ax, stream, y, x0):
for k, v in enumerate(stream):
x = x0 + k * _STREAM_CW
fc, ec, lw, tcol = COL_AMBER_300, COL_AMBER_600, 1.4, COL_TEXT
ax.add_patch(FancyBboxPatch(
(x, y), _STREAM_CW * 0.92, _STREAM_CH, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=3))
cx, cy = x + _STREAM_CW * 0.46, y + _STREAM_CH * 0.5
ax.text(cx, cy, str(v), ha="center", va="center",
fontsize=12.5, color=tcol, weight="bold", zorder=5)
ax.text(cx, y - 0.20, str(k), ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, zorder=5)
ax.text(x0 - 0.42, y + _STREAM_CH * 0.5, "akış", ha="right", va="center",
fontsize=10, color=COL_TEXT, weight="bold", zorder=5)
def _mini_set(ax, values, x0, y):
centers = []
for k, v in enumerate(values):
x = x0 + k * _SET_CW
ax.add_patch(FancyBboxPatch(
(x, y), _SET_CW * 0.90, _SET_CH, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=3))
cx, cy = x + _SET_CW * 0.45, y + _SET_CH * 0.5
centers.append((cx, cy))
ax.text(cx, cy, str(v), ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold", zorder=5)
return centers
def _drop_in_marker(ax, x, y, value, kind):
if kind == "drop":
fc, ec, tcol = COL_WHITE, COL_SLATE_400, COL_SLATE_500
else:
fc, ec, tcol = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
ax.add_patch(Circle((x, y), _RC, facecolor=fc, edgecolor=ec,
linewidth=2.4, zorder=6))
ax.text(x, y, str(value), ha="center", va="center",
fontsize=10, color=tcol, weight="bold", zorder=7)
if kind == "drop":
ax.plot([x - _RC * 0.78, x + _RC * 0.78], [y, y],
color=COL_AMBER_700, linewidth=2.0, zorder=8)
_stream = [5, 1, 8, 3, 9, 2, 7]
_k = 3
_steps = _topk_trace(_stream, _k)
fig, ax = plt.subplots(figsize=(10.6, 7.0))
fig.patch.set_facecolor(COL_WHITE)
x0 = 0.0
n_str = len(_stream)
str_right = x0 + n_str * _STREAM_CW
y_stream = 0.0
_stream_strip(ax, _stream, y_stream, x0)
set_x0 = x0 + 0.30
drop_x = set_x0 + _k * _SET_CW + 0.55
enter_x = drop_x + 0.95
badge_x = enter_x + 0.95
y_first = y_stream - 1.35
row_ys = [y_first - r * _ROW_GAP for r in range(len(_steps))]
stream_cx = [x0 + j * _STREAM_CW + _STREAM_CW * 0.46 for j in range(n_str)]
for r, st in enumerate(_steps):
y = row_ys[r]
v = st["value"]
contents = st["contents"]
dropped = st["dropped"]
entered = st["entered"]
ax.text(set_x0 - 0.45, y + _SET_CH * 0.5, f"{v} gelir",
ha="right", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=5)
sx = stream_cx[r]
ax.plot([sx, sx], [y_stream - 0.06, y + _SET_CH + 0.10],
color=COL_AMBER_300, linewidth=1.0, linestyle=(0, (2, 3)), zorder=0)
centers = _mini_set(ax, contents, set_x0, y)
if entered is not None and entered in contents:
ci = contents.index(entered)
cx, cy = centers[ci]
ax.add_patch(FancyBboxPatch(
(set_x0 + ci * _SET_CW - 0.01, y - 0.01),
_SET_CW * 0.90 + 0.02, _SET_CH + 0.02,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=4))
ax.text(cx, cy, str(entered), ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=5)
cy_mid = y + _SET_CH * 0.5
if dropped is not None:
_drop_in_marker(ax, drop_x, cy_mid, dropped, "drop")
else:
ax.text(drop_x, cy_mid, "—", ha="center", va="center",
fontsize=11, color=COL_SLATE_400, zorder=5)
if entered is not None:
_drop_in_marker(ax, enter_x, cy_mid, entered, "enter")
else:
ax.text(enter_x, cy_mid, "—", ha="center", va="center",
fontsize=11, color=COL_SLATE_400, zorder=5)
seen_so_far = _stream[:r + 1]
expected_topk = sorted(seen_so_far)[-_k:]
ok = (contents == expected_topk)
ax.add_patch(FancyBboxPatch(
(badge_x, cy_mid - 0.27), 1.55, 0.54,
boxstyle="round,pad=0.03,rounding_size=0.08",
fc=COL_AMBER_100 if ok else COL_WHITE,
ec=COL_ACCENT if ok else COL_SLATE_400, linewidth=2.0, zorder=4))
ax.text(badge_x + 0.16, cy_mid, "✓ top-3" if ok else "✗",
ha="left", va="center", fontsize=9.5,
color=COL_AMBER_700 if ok else COL_SLATE_500,
weight="bold", zorder=5)
y_head = y_first + _SET_CH + 0.36
ax.text(set_x0 + (_k * _SET_CW) * 0.5 - _SET_CW * 0.05, y_head,
"ağaç içeriği (sıralı)", ha="center", va="center",
fontsize=9, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(drop_x, y_head, "düşen", ha="center", va="center",
fontsize=9, color=COL_SLATE_500, weight="bold", zorder=5)
ax.text(enter_x, y_head, "giren", ha="center", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(badge_x + 0.16, y_head, "değişmez", ha="left", va="center",
fontsize=9, color=COL_PRIMARY, weight="bold", zorder=5)
y_box = row_ys[-1] - _ROW_GAP * 0.95
box_left = set_x0 - 0.55
box_right = badge_x + 1.55
box_w = box_right - box_left
ax.add_patch(FancyBboxPatch(
(box_left, y_box - 0.05), box_w, 0.86,
boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
ax.text(box_left + box_w * 0.5, y_box + 0.55,
"DEĞİŞMEZ — ağaç her an o ana kadar İŞLENENLERİN en büyük k tanesini tutar"
" (Ku 48:14)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(box_left + box_w * 0.5, y_box + 0.20,
"bellek O(k) = O(log n) · öğe başına maliyet O(log k) = O(log log n)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=4)
fig.suptitle(
"k-en-iyi kayan set-AVL: ekle, taşarsa en küçüğü düşür → her an top-k",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(str_right * 0.5, y_stream + _STREAM_CH + 0.40,
"akış [5, 1, 8, 3, 9, 2, 7] · k = 3 · TopKTree.process(v): "
"avl_insert sonra n>k ise en küçüğü sil",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(box_left - 0.4, max(box_right, str_right) + 0.4)
ax.set_ylim(y_box - 0.5, y_stream + _STREAM_CH + 0.9)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Problem 3: Müzayede — Çoklu Yapı ve Cross-Linking {#sec-problem-3-d11}
**İfade.** Bir müzayedede teklif verenler (benzersiz bidder ID + tamsayı teklif). new_bid ve update_bid **$O(\log n)$**; ihale kapanınca **en yüksek k teklifin toplamı** (get_revenue) **$O(1)$**. (k önceden sabittir.)
::: {.callout-tip title="Yaklaşım — İki anahtar → çoklu yapı; önce ne saklanır ve hangi değişmez korunur"}
İki "anahtar" var: bidder ID (arama için) ve teklif (sıralama için) → tek bir ağaç yetmez, birden çok veri yapısı gerekir. Her zamanki gibi önce **ne saklandığını ve hangi değişmezin korunduğunu** netleştir: en yüksek k teklif bir kümede, geri kalanlar başka bir kümede, toplam ayrı bir sayıda. Yapıları bağlayan şey **cross-linking**'tir.
:::
**Çözüm.** Dört bileşen:
1. **Sözlük (set AVL), bidder ID anahtarlı:** bir teklifçiyi bul; her düğüm, teklifçinin diğer yapılardaki yerine bir **işaretçi** tutar (cross-linking).
2. **k-en-yüksek set AVL** (teklif anahtarlı): şu anki en yüksek k teklif.
3. **(n−k)-kalan set AVL** (teklif anahtarlı): geri kalanlar.
4. **`total` (t)**: k-en-yüksek kümesinin toplamı — bir sayı zenginleştirmesi.
new_bid: yeni teklif, k-en-yüksek'in minimumundan büyükse, o minimumu (n−k)'ye taşı ve yeniyi k-en-yüksek'e koy; değilse doğrudan (n−k)'ye. Her hareket `total`'ı $O(1)$ günceller. get_revenue sadece `total`'ı döndürür — **$O(1)$**.
> *"This is called cross-linking."* — Ku, 1:07:08
```python
def new_bid(self, bidder, amount): # O(log n)
if bidder in self.bids: # cross-link: sözlük O(1) bulur
old = (self.bids[bidder], bidder) # eski anahtarı sil (O(log n))
...
self.bids[bidder] = amount
self._topk_insert((amount, bidder)) # yeni anahtar (O(log n))
self._rebalance_sets() # topk ↔ rest sınırını koru
def get_revenue(self):
return self.total # zenginleştirme → O(1)
```
@fig-auction-crosslink dört bileşeni ve cross-link'leri motordan **gerçek** bir senaryoyla gösterir: k = 2 ile A:100, B:300, C:200 teklifleri girilince topk = {300, 200}, rest = {100}, revenue = 500. Sonra A'nın teklifi 400'e güncellenince A'nın eski kaydı (100) rest'ten **silinir**, (400, A) topk'ye girer, taşan minimum (200, C) rest'e iner ve revenue **700** olur — her adım `total`'ı $O(1)$ günceller.
**Karmaşıklık.** new_bid/update_bid **$O(\log n)$** (sabit sayıda AVL işlemi); get_revenue **$O(1)$** (değişmez `total`).
```{python}
#| label: fig-auction-crosslink
#| fig-cap: "Müzayede: çoklu yapı + cross-linking + total zenginleştirmesi → get_revenue() O(1) — Problem 3 İMZA. Dört bileşen güncelleme SONRASI durumda (motordan GERÇEK): (1) bids sözlüğü bidder→güncel teklif (A→400, B→300, C→200); (2) topk set-AVL en yüksek k=2 {(400,A),(300,B)}; (3) rest set-AVL kalan {(200,C)}; (4) total = 700 amber kutu. İnce kesikli çift yönlü oklar CROSS-LINK'tir: sözlükteki her bidder ilgili ağaç anahtarına bağlı → güncellemede sözlük O(1) bulur, ağaç O(log n) sil+ekle, total O(1) güncellenir. Alttaki zaman çizgisi MOTOR GERÇEĞİ: 3 teklif → revenue 500; update_bid(A, 100→400) → (100,A) rest'ten silinir, (400,A) topk'ye girer, (200,C) rest'e iner → revenue 700."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-auction-crosslink — PS4 Problem 3 İMZA: çoklu yapı + cross-linking + total.
# Veri MOTORDAN: AuctionHouse(2), 3 teklif → revenue 500, update_bid(A,400) →
# revenue 700. Setup globalleri: plt, Circle, FancyBboxPatch, FancyArrowPatch,
# COL_*, AuctionHouse, avl_to_list.
def _component_box(ax, x, y, w, h, title, *, fc=COL_BG, ec=COL_PRIMARY,
title_color=COL_TEXT, lw=2.0):
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=fc, ec=ec, linewidth=lw, zorder=2))
ax.text(x + w * 0.5, y + h + 0.16, title, ha="center", va="bottom",
fontsize=10.5, color=title_color, weight="bold", zorder=6)
return x + w * 0.5, y + h * 0.5
def _avl_node(ax, x, y, label, *, r=0.34, fill=False):
if fill:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.6
else:
fc, ec, tcol, lw = COL_WHITE, COL_PRIMARY, COL_TEXT, 1.8
ax.add_patch(Circle((x, y), r, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, label, ha="center", va="center", fontsize=9.5,
color=tcol, weight="bold", zorder=6)
return x, y
# --- motor verisi (figür yalnız bunu çizer) ---
_ah = AuctionHouse(2)
_ah.new_bid("A", 100)
_ah.new_bid("B", 300)
_ah.new_bid("C", 200)
_rev_before = _ah.get_revenue() # 500
_ah.update_bid("A", 400)
_rev_after = _ah.get_revenue() # 700
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
# (1) SOL: bids sözlüğü
dict_x, dict_y, dict_w = 0.0, 3.0, 2.7
rows = [("A", 400), ("B", 300), ("C", 200)]
row_h = 0.62
dict_h = row_h * len(rows) + 0.30
dcx, _ = _component_box(ax, dict_x, dict_y, dict_w, dict_h,
"1 · bids sözlüğü", fc=COL_BG, ec=COL_PRIMARY)
dict_row_y = {}
for r, (bidder, amount) in enumerate(rows):
ry = dict_y + dict_h - 0.15 - (r + 0.5) * row_h
dict_row_y[bidder] = ry
ax.text(dict_x + 0.28, ry, f"{bidder}", ha="left", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=6)
ax.text(dict_x + 0.78, ry, "→", ha="center", va="center",
fontsize=10, color=COL_SLATE_500, zorder=6)
ax.text(dict_x + dict_w - 0.28, ry, f"{amount}", ha="right", va="center",
fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(dcx, dict_y - 0.30, "bidder → güncel teklif",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=6)
# (2) ORTA-ÜST: topk set-AVL (en yüksek k=2)
topk_x, topk_y, topk_w, topk_h = 3.9, 4.55, 3.5, 1.65
tcx, tcy = _component_box(ax, topk_x, topk_y, topk_w, topk_h,
"2 · topk set-AVL (en yüksek k=2)",
fc=COL_AMBER_100, ec=COL_ACCENT,
title_color=COL_AMBER_700, lw=2.4)
root_xy = (topk_x + topk_w * 0.62, topk_y + topk_h * 0.66)
childL_xy = (topk_x + topk_w * 0.30, topk_y + topk_h * 0.30)
ax.plot([root_xy[0], childL_xy[0]], [root_xy[1], childL_xy[1]],
color=COL_ACCENT, linewidth=2.0, zorder=3, solid_capstyle="round")
n_400 = _avl_node(ax, *root_xy, "400,A", fill=True)
n_300 = _avl_node(ax, *childL_xy, "300,B", fill=True)
# (3) ORTA-ALT: rest set-AVL (kalan)
rest_x, rest_y, rest_w, rest_h = 3.9, 2.05, 3.5, 1.35
rcx, rcy = _component_box(ax, rest_x, rest_y, rest_w, rest_h,
"3 · rest set-AVL (kalan)",
fc=COL_BG, ec=COL_PRIMARY)
rest_node_xy = (rest_x + rest_w * 0.5, rest_y + rest_h * 0.5)
n_200 = _avl_node(ax, *rest_node_xy, "200,C", fill=False)
# (4) SAĞ: total = 700
tot_x, tot_y, tot_w, tot_h = 8.5, 3.3, 2.5, 1.9
ax.add_patch(FancyBboxPatch(
(tot_x, tot_y), tot_w, tot_h, boxstyle="round,pad=0.03,rounding_size=0.12",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=3.0, zorder=2))
ax.text(tot_x + tot_w * 0.5, tot_y + tot_h + 0.16, "4 · total (zenginleştirme)",
ha="center", va="bottom", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(tot_x + tot_w * 0.5, tot_y + tot_h * 0.62, f"{_rev_after}",
ha="center", va="center", fontsize=30, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(tot_x + tot_w * 0.5, tot_y + tot_h * 0.24, "= topk toplamı",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=6)
ax.add_patch(FancyArrowPatch(
(tcx + topk_w * 0.5 + 0.05, tcy), (tot_x - 0.05, tot_y + tot_h * 0.5),
arrowstyle="-|>", mutation_scale=16, color=COL_AMBER_600,
linewidth=2.4, zorder=4, connectionstyle="arc3,rad=-0.12"))
ax.text((tcx + topk_w * 0.5 + tot_x) * 0.5 + 0.05, tot_y + tot_h * 0.5 + 0.55,
"get_revenue()\n→ O(1)", ha="center", va="center", fontsize=9,
color=COL_AMBER_700, weight="bold", zorder=7, linespacing=1.15)
# CROSS-LINK okları
cross = [("A", n_400), ("B", n_300), ("C", n_200)]
for bidder, (nx, ny) in cross:
ry = dict_row_y[bidder]
ax.add_patch(FancyArrowPatch(
(dict_x + dict_w + 0.02, ry), (nx - 0.36, ny),
arrowstyle="<|-|>", mutation_scale=9, color=COL_SLATE_500,
linewidth=1.1, linestyle=(0, (3, 2)), zorder=1,
connectionstyle="arc3,rad=0.06"))
ax.text(dict_x + dict_w + 0.55, dict_y + dict_h + 0.05,
"cross-link (çift yönlü)", ha="left", va="bottom", fontsize=8,
color=COL_SLATE_500, style="italic", zorder=6, rotation=8)
# ALT: zaman çizgisi (MOTOR GERÇEĞİ)
tl_y = 0.55
tl_x0, tl_x1 = 0.0, 11.0
ax.plot([tl_x0, tl_x1], [tl_y, tl_y], color=COL_SLATE_400,
linewidth=1.6, zorder=1)
def _tl_event(cx, title, body, delta, *, accent=False):
col = COL_AMBER_700 if accent else COL_PRIMARY
ax.add_patch(Circle((cx, tl_y), 0.07, facecolor=col,
edgecolor=COL_WHITE, linewidth=1.2, zorder=4))
ax.text(cx, tl_y + 0.95, title, ha="center", va="center",
fontsize=9.5, color=col, weight="bold", zorder=5)
ax.text(cx, tl_y + 0.50, body, ha="center", va="center",
fontsize=8.3, color=COL_TEXT, zorder=5, linespacing=1.2)
dcol = COL_AMBER_700 if accent else COL_SLATE_500
ax.text(cx, tl_y - 0.40, delta, ha="center", va="center",
fontsize=8.5, color=dcol, weight="bold", zorder=5)
ev1_x, ev2_x, ev3_x = 1.7, 5.5, 9.4
_tl_event(ev1_x, "① 3 teklif",
"A:100 B:300 C:200\ntopk={300,200} rest={100}",
"total: 0 +=300 +=200 → 500")
_tl_event(ev2_x, "② revenue",
"get_revenue() = 500\n(topk toplamı, O(1))",
"total = 500")
_tl_event(ev3_x, "③ update_bid(A, 100→400)",
"(100,A) rest'te → SİLİNİR · (400,A)→topk\ntopk taşar → (200,C) rest'e iner",
"total: 500 −200(C dışarı) +400(A) → 700",
accent=True)
for axa, axb in ((ev1_x, ev2_x), (ev2_x, ev3_x)):
ax.add_patch(FancyArrowPatch(
(axa + 0.55, tl_y), (axb - 0.55, tl_y), arrowstyle="-|>",
mutation_scale=12, color=COL_SLATE_400, linewidth=1.4, zorder=2))
ax.add_patch(FancyBboxPatch(
(ev3_x - 1.45, tl_y - 1.18), 2.9, 0.42,
boxstyle="round,pad=0.03,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=3))
ax.text(ev3_x, tl_y - 0.97, "topk={400,300} rest={200} total=700",
ha="center", va="center", fontsize=8.3, color=COL_AMBER_700,
weight="bold", zorder=5)
fig.suptitle(
"Müzayede: çoklu yapı + cross-linking + total zenginleştirmesi → "
"get_revenue() O(1)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ax.text(5.5, 6.55,
"new_bid / update_bid: sözlük O(1) bulur · ağaç O(log n) sil+ekle · "
"total O(1) güncellenir (update = sil + ekle)",
ha="center", va="center", fontsize=8.8, color=COL_SLATE_500,
style="italic", zorder=6)
ax.plot([tl_x0, tl_x1], [1.85, 1.85], color=COL_SLATE_400,
linewidth=1.0, linestyle=(0, (3, 3)), zorder=0)
ax.set_xlim(-0.5, 11.4)
ax.set_ylim(tl_y - 1.55, 6.85)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-tip title="Builder Notu — cross-linking = veritabanı ikincil indeksi / foreign key"}
Cross-linking, veritabanı dünyasındaki **ikincil indeks (secondary index)** ve **foreign key** ile birebir örtüşür. Bir tablo birincil anahtarıyla (bidder ID) saklanırken, sık sorgulanan başka bir alan (teklif) üzerine ayrı bir indeks kurulur; ikincil indeks **aynı kaydı farklı bir anahtarla** bulmanı sağlar — tıpkı buradaki teklif-anahtarlı topk/rest ağaçlarının sözlükteki aynı teklifçiye bir işaretçiyle bağlanması gibi. Veri tek yerde tutulur, ona iki ayrı yoldan erişilir; güncellemede her iki yapı da senkron tutulmalıdır (foreign key bütünlüğü). Bu, "aynı veriyi iki anahtarla aranabilir kılmanın" maliyeti ve gücüdür.
:::
## Problem 4: Receiver Roster — İç İçe Ağaçlar ve Rank Sorgusu {#sec-problem-4-d11}
**İfade.** Bir futbol koçu, oyuncuların **k. en yüksek performansını** (= ortalama puan = puan/oyun, bir *rasyonel*) **$O(\log n)$**'de sorgulamak ister. Veriler dinamik güncellenir (oyun ekle/sil).
::: {.callout-tip title="Yaklaşım — Rasyonel için çapraz çarpım; rank için size augmentation"}
Performans rasyoneldir → bölme (kayan nokta hatası) yerine **çapraz çarpım** ile karşılaştır: $w_1/f_1$ ile $w_2/f_2$'yi kıyaslarken bölmek yerine $w_1 \cdot f_2$ ile $w_2 \cdot f_1$'i karşılaştır (paydalar pozitif olduğundan işaret korunur; motorda `Fraction` bunun exact eşdeğeridir). k. en büyüğü (rank sorgusu) bulmak için ise `size` zenginleştirmesi gerekir — sequence ağacının `subtree_at`'iyle aynı mekanizma.
:::
**Çözüm.** İç içe bir yapı kurulur:
1. **Set AVL (receiver ID anahtarlı):** oyuncuları bul.
2. Her oyuncuyla **iç içe bir set AVL (game ID anahtarlı):** o oyuncunun oyunları (bir oyunu $O(\log n)$'de silmek için liste değil ağaç).
3. Her oyuncuda iki sayı zenginleştirmesi: **toplam puan** ve **oyun sayısı** → performans (puan/oyun) çapraz-çarpımla karşılaştırılır.
4. **Performansa göre set AVL** (çapraz-çarpım komparatörü) + **`size` zenginleştirmesi**: bu, sequence ağacının `subtree_at`'iyle aynı **rank-find** işlemini verir — k. en büyük performansı $O(\log n)$'de bulur. (Ders 10'daki `subtree_at` ile aynı mekanizma: sondan k. öğe = in-order'da indeks n−k.)
5. Cross-linking işaretçileri (bir oyuncunun performans ağacındaki yeri).
> *"you can think of the size augmentation finding-rank as a one-sided range query."* — Ku, 1:29:19
```python
def kth_best(self, k): # k. en yüksek performans — O(log n)
# size-rank: in-order'da sondan k. = indeks n−k (Ders 10'daki subtree_at)
return subtree_at(self.perf, self.perf_n - k).item
def _perf_key(self, pid): # rasyonel anahtar: çapraz çarpım = Fraction
p = self.players[pid]
return (Fraction(p["points"], len(p["games"])), pid) # exact, bölme YOK
```
**Karmaşıklık.** Tüm güncellemeler ve k. en yüksek sorgusu **$O(\log n)$** (iç içe aramalar log n × log n değil, çünkü oyun sayısı toplamı n).
## Ne Öğrendik? {#sec-ne-ogrendik-d11}
::: {.callout-important title="Altı Taşınabilir Araç"}
Bu oturum, Ders 9-10'un AVL teorisini dört somut problemde uyguladı ve altı taşınabilir araç kazandırdı:
1. **Sequence AVL = height + size:** indeksle arama (`subtree_at`) ve denge birlikte; çift rotasyon (Durum 3) ezberlenir.
2. **Priority queue / binary heap:** build $O(n)$ + delete_max $O(\log n)$ — set AVL'nin $O(n \log n)$ build'inden üstün (önizleme).
3. **Kayan pencere + değişmez:** sabit boyutlu (log n) yapıyla "o ana kadarki en iyi k" tutmak; az bellek.
4. **Çoklu yapı + cross-linking:** aynı veriyi farklı anahtarlarla iki/üç ağaçta tutup işaretçilerle bağlamak.
5. **Augmentation ile $O(1)$ sorgu:** bir toplamı (`total`) zenginleştirmeyle tutup sorguyu sabit zamana indirmek.
6. **`size` augmentation = rank sorgusu:** k. en büyük / "kaç tanesi büyük" (one-sided range query) — sequence `subtree_at`'in seti.
:::
::: {.callout-tip title="Builder Notu — kayan pencere = streaming leaderboard"}
Problem 2'nin (b) şıkkı, modern sistemlerin **streaming leaderboard** (akış sıralaması) deseninin tam kalbidir: sonsuz bir olay akışında (oyun skorları, satışlar, beğeniler) "şu ana kadarki en iyi k" sabit boyutlu bir yapıda tutulur ve her yeni olayda sıfırdan değil artımlı güncellenir — yeni öğe girer, eşik altına düşen en küçük çıkar. Tüm geçmişi bellekte tutmak yerine yalnızca $O(\log n)$ öğe saklamak, milyarlarca olaylık akışları sabit bellekle işlenebilir kılar; değişmez ("yapı her an o ana kadarki top-k") da sonucun doğruluğunu garanti eder.
:::
## Sonraki {#sec-sonraki-d11}
::: {.callout-warning title="Ders 12 (L8) — İkili Yığınlar (Binary Heaps)"}
Sırada **Ders 12 (L8): İkili Yığınlar (Binary Heaps)** var — Erik Demaine ile, bu oturumda Problem 2'de kara kutu olarak kullandığımız **öncelik kuyruğunu** açıyoruz: ikili yığın, diziye gömülü bir tam-ağaçla build $O(n)$ ve delete_max $O(\log n)$ verir. (Not: Notion kaynağı bu dersi "Ders 8 (L8)" diye anar, ama kitap düzeninde L8 = Ders 12'dir.) Bu oturumdaki augmentation ve invariant sezgileri, yığının "tahtadan-aşağı" (heapify) mantığını anlamana yarayacak.
:::
