BST property ve in-order traversal
| İşlem | Sorted array | Linked list | Balanced BST |
|---|---|---|---|
| Search | $O(\log n)$ | $O(n)$ | $O(\log n)$ |
| Insert | $O(n)$ | $O(1)$ | $O(\log n)$ |
| Delete | $O(n)$ | $O(n)$ | $O(\log n)$ |
Sorted array'e 4.5'i insert etmek için ondan sonra gelen bütün elemanları birer kaydırırsın. Linked list'e insert tek adım, ama 4.5'i search etmek için listeyi baştan sona gezersin. Balanced bir BST ikisinin de iyi yanını alır.
Her node bir key ve üç pointer taşır: left child, right child ve parent. Olmayan child NIL'dir. Bu derste key'ler birbirinden farklı.
BST property: her $x$ node'u için, $x$'in left subtree'sindeki bütün key'ler $\text{key}(x)$'ten küçük, right subtree'sindeki bütün key'ler büyüktür.
Height: root'tan en uzak leaf'e giden path'teki edge sayısı. Aşağıdaki tree'nin height'ı 3 (5 → 3 → 2 → 1).
Slayt 16'daki tree. Bu derste her çizimde node'lar yatayda in-order sırasına göre dizilir: soldan sağa okuyunca 1 2 3 4 5 7 8.
S5.5 midterm review'daki soru: "Is this a BST?"
Her parent-child çifti doğru görünüyor: 1 < 4. Ama 1, 3'ün right subtree'sinde, yani 3'ten büyük olmalıydı. BST değil. BST property bütün subtree için geçerli; tek child'a bakmak yetmez. Çizimde de görünüyor: 1 yatayda yanlış yerde, in-order sırası 2 3 1 4 5 7 8 çıkıyor.
In-order traversal
Önce left subtree'yi yazdır, sonra node'u, sonra right subtree'yi. Oynat'a bas: output kendiliğinden sorted çıkıyor.
- In-order traversal bir BST'nin key'lerini sorted sırada verir: $x$'ten önce left subtree'nin tamamı (hepsi küçük), sonra $x$, sonra right subtree (hepsi büyük) yazılır.
- Running time $O(n)$: her node bir kez ziyaret edilir.
- Notlardaki benzetme: her node, kendi subtree'si için QuickSort'taki pivot gibi. Solunda $A_<$, sağında $A_>$ var.
Bir BST'de $B$, $A$'nın left child'ı; $C$ de $B$'nin right child'ı. Hangisi doğru?
Search ve insert
Search, tree üzerinde binary search'tür: aradığın sayıyı node'un key'iyle compare et; küçükse sola, büyükse sağa in. Bir işlem seç ve oynat.
- search($i$): root'tan başla. $\text{key}(x) = i$ ise $x$'i döndür. $i < \text{key}(x)$ ise sola, büyükse sağa git. Gideceğin child NIL ise son node'u döndür.
- insert($i$): $x = $ search($i$). $i < \text{key}(x)$ ise yeni node $x$'in left child'ı, değilse right child'ı olur. Yeni node hep bir leaf olarak eklenir.
- Running time: path üzerindeki her node'da constant iş var, path en fazla $h+1$ node. İkisi de $O(h)$.
7: $7 > 5$ sağa, $7 < 9$ sola, $7 > 6$ sağa, NIL. 7, 6'nın right child'ı olur. 8 de (tek başına insert edilirse) aynı yere gider.
- Bulunamayınca dönen node, değerce en yakın node olmayabilir. Notlardaki örnek: root 5, left child'ı 2. search(4) 2'yi döndürür, oysa 5 daha yakın (Remark 8).
- Aynı key'ler farklı sırayla insert edilirse farklı tree'ler çıkar. "Bu sayılarla tek bir BST vardır" yanlış (slayt 21).
- "BST'de search $O(\log n)$" sadece tree balanced ise doğru. Genel cevap $O(h)$.
Pre-lecture tree'sine ($T$) 8 insert edilince 8 nerede durur?
Delete: üç case
Leaf'i silmek kolay: kopar at. Tek child'ı varsa child yukarı çıkar. İki child'ı varsa birinin onun yerine geçmesi gerek. Sırayı bozmayacak tek aday, sorted sırada hemen arkasından gelen key: successor.
- Child yok: parent'ın o pointer'ı NIL olur.
- Tek child $c$: $c$, $x$'in yerine yükselir (parent'ın pointer'ı $c$'yi gösterir, $c$'nin parent'ı güncellenir).
- İki child: successor $z$'yi bul: right child'a bir adım in, sonra NIL'e kadar hep sola. $z$'nin left child'ı yoktur. $z$'nin right child'ı varsa onu $z$'nin eski yerine bağla. Sonra $z$'yi $x$'in yerine koy: $x$'in left ve right subtree'leri $z$'nin olur.
Running time: bir iki search ve $O(1)$ pointer işi, toplam $O(h)$.
3'ün iki child'ı var. Successor: sağa bir adım (4), sola gidilecek yer yok, $z = 4$. 4, 3'ün yerine geçer. 4'ü eski yerinden silmek ise case 1: leaf olduğu için kopar.
- Successor her zaman right child değildir: right child'dan sonra sola inmeye devam edersin.
- Successor'ın left child'ı yoktur (olsaydı o daha küçük bir aday olurdu), ama right child'ı olabilir. Onu bağlamayı unutursan o subtree'yi kaybedersin.
- Successor yerine predecessor (left subtree'nin en sağı) da kullanılabilir; notlar bunu da doğru sayar. Sınavda hangisini kullandığını yaz.
Tree: root 4; 4'ün child'ları 2 (1, 3) ve 7; 7'nin child'ları 5 ve 8; 5'in right child'ı 6. Successor ile 4 silinince ne olur?
Height: log n ile n arası
Bütün işlemler $O(h)$, yani her şey height'a bağlı. Aşağıdaki BST laboratuvarında bir insertion sırası seç ya da kendin yaz. Tree her insert'ten sonra yeniden çizilir; yandaki grafik height'ı alttan $\lfloor \log_2 n \rfloor$, üstten $n - 1$ bound'uyla karşılaştırır.
Önce tahmin et: $n = 7$ için sıralı sırada son height ve toplam comparison sayısı kaç olur? Zigzag sırası (1, 7, 2, 6, …) daha kısa bir tree verir mi?
$n$ node'lu bir binary tree için $\lfloor \log_2 n \rfloor \le h \le n - 1$.
- Lower bound: depth $d$'de en fazla $2^d$ node var. Height $h$ ise toplam en fazla $1 + 2 + \dots + 2^h = 2^{h+1} - 1$ node olur, yani $n \le 2^{h+1}-1$ ve $h \ge \log_2(n+1) - 1$.
- Upper bound: her node'un tek child'ı varsa tree bir path'tir, $h = n - 1$. Sorted sırayla insert tam olarak bunu yapar.
- Bu yüzden genel BST'de search, insert, delete worst case'te $\Theta(n)$.
Key'ler random sırayla insert edilirse expected average depth $O(\log n)$ olur (Section 4 Problem 2). Analiz QuickSort'unkiyle aynı: root, random seçilmiş bir pivot gibi davranır. Ama input'u biz seçmiyoruz. Worst case garantisi için tree'yi balanced tutmamız gerekir.
Slaytlardaki fikirler: (0) tree çok uzarsa baştan kur; bu sık sık $\Omega(n)$ demek, iyi değil. (1) Rotation ile parçaları yerel olarak yeniden as. (2) Balance yerine geçen, korunması kolay bir property (proxy for balance) bul. Red-black tree bu ikisini birleştirir.
$n$ node'lu bir BST'nin height'ı için hangisi her zaman doğru? (L7 concept check)
Lucky, BST property'sini koruyan bir "luckyTree" yaptığını söylüyor: insert $O(1)$, search ve delete $O(\log n)$, deterministic, her türlü comparable object ile çalışıyor. Lucky'nin yanıldığını, lower bound'u bilinen bir problemi bu yapıyla çözerek kanıtla.
İpucu 1
Lecture 6'da lower bound'u bilinen problem hangisiydi? Comparison-based bir algoritma onu $\Omega(\cdot)$'den hızlı yapamaz.
İpucu 2
Bir BST'den key'leri sorted sırada çıkarmanın $O(n)$'lik yolunu bu bölümün başında gördün.
İpucu 3
$n$ elemanı tek tek luckyInsert ile ekle. Toplam running time'ı say ve hangi lower bound'la çeliştiğini söyle.
Çözümü göster
LuckySort($A$): boş bir luckyTree kur. $A$'nın her elemanını luckyInsert ile ekle: $n \cdot O(1) = O(n)$. Sonra luckyTree.root()'tan in-order traversal yap: $O(n)$. BST property korunduğu için output sorted olur.
Running time'ı toplam $O(n)$ olan, deterministic ve elemanlara yalnızca comparison ile erişen bir sorting algorithm elde ettik (luckyTree her comparable object ile çalışıyor, yani elemanların içine bakamaz). Lecture 6'daki decision tree argümanı, her deterministic comparison-based sorting algorithm için worst case'in $\Omega(n\log n)$ olduğunu söyler. Contradiction: luckyTree var olamaz.
Not: traversal hiç comparison yapmaz; bütün bilgi insert sırasında yapılan comparison'lardan gelir. Search ve delete'in hızına hiç ihtiyaç olmadı.
Boş BST’ye 2,1,7,3,6,4,5,8 sırasıyla insert et. Rebalancing yok. Height kaç?
İpucu
Çözümü göster
En uzun yol 2→7→3→6→4→5; 6 düğüm, 5 kenar. Height 5. Bu sıradan BST; red-black balancing yapılmıyor.
Red-black tree property'leri
Perfect balance'ı korumak çok pahalı. Onun yerine biraz daha gevşek bir şey isteriz: black node'lar tam balanced olsun, red node'lar da seyrek dağılsın ki path'leri çok uzatamasın. Bu kadarı height'ı $O(\log n)$'de tutmaya yetiyor ve insert/delete sırasında korunabiliyor.
Red-black tree, şu beş property'yi sağlayan bir BST'dir:
- Her node ya red ya black'tir.
- Root black'tir.
- NIL'ler black'tir. (Leaf'ler artık NIL'ler; çizilmeseler de sayılırlar.)
- Red bir node'un iki child'ı da black'tir. (Art arda iki red yok.)
- Her $x$ node'u için, $x$'ten NIL'lere giden bütün path'lerde aynı sayıda black node vardır.
Black-height $b(x)$: $x$'ten herhangi bir NIL'e giden path'teki black node sayısı, $x$ hariç, NIL dahil. Property 5 sayesinde hangi path'i seçtiğin fark etmez.
Notlardaki Örnek 14'ün şekli, key'ler eklendi. Küçük kareler NIL, mavi etiketler $b(x)$. Kontrol: 4'ten her NIL'e 2 black node var (örneğin 4 → 7 → 8 → 9 → NIL path'inde 8 ve NIL).
- $b(x)$ sayarken $x$'in kendisi sayılmaz, NIL sayılır. NIL'in black-height'ı 0, iki child'ı da NIL olan bir node'unki 1.
- Property 4 tek yönlü: black bir node'un child'ları da black olabilir. Bütün node'ları black olan bir perfect binary tree geçerli bir red-black tree'dir.
- Renkler ne kadar doğru olursa olsun, tree önce BST olmalı.
Bir red-black tree'de $b(\text{root}) = 3$. Root'tan bir NIL'e giden path en fazla kaç edge olabilir?
Bu tree red-black mi?
Sınavda ve concept check'te en çok sorulan şey bu. Hep aynı sırayla kontrol et, hiçbir property'yi atlama.
- BST mi? Soldan sağa (in-order) oku, sorted mı?
- Root black mi?
- Art arda red var mı? Her red node'un child'larına bak.
- Black sayıları: en alttan yukarı her node için sol ve sağdan gelen black sayısını hesapla; eşit değilse property 5 bozuk. Tek child'lı node'lara özellikle bak: boş taraf tek bir black NIL'dir.
Tarifi bir validity checker üzerinde dene. Checker yukarıdaki sırayla ilerler ve ilk bozulan şartta durur: hangi property olduğunu yazar, suçlu node'u turuncu halkayla, property 5'te de farklı sayıda black taşıyan iki path'i kalın çizgiyle gösterir. Bir node'a tıklayınca rengi red ile black arasında değişir.
Önce tahmin et: bir tree seç; ▶|'e basmadan önce ilk bozulan property'yi ve root'un black-height'ını $b(\text{root})$ söyle.
L7 slayt 51 ve S5.5: hangisi geçerli bir red-black tree? (NIL'ler çizilmedi.)
L7 concept check: hangisi geçerli bir red-black tree?
Coloring laboratuvarı: HW4 Problem 1
Bir node'a tıkla, rengi değişsin. Kontrol her tıklamada gerçek property'lerle yeniden çalışır: bozulan property'leri listeler, tree geçerli olunca her node'un $b(x)$ değerini yazar. NIL'ler küçük kareler olarak çizildi.
Üç tree şekli verilmiş. Her biri için node'lar red/black boyanıp geçerli bir red-black tree elde edilebiliyorsa bir coloring ver; edilemiyorsa "No such red-black tree" yaz. Yukarıdaki laboratuvarda ilk üç seçenek bu tree'ler (key'ler in-order sırasıyla 1, 2, 3, … verildi).
İpucu 1
Her tree'de root'tan NIL'e giden en kısa ve en uzun path'i bul. Root'tan sonraki node'ları say, NIL dahil. Tek child'lı node'ların boş tarafı çok kısa bir path'tir.
İpucu 2
Bütün path'lerde black sayısı aynı: $b$. Kısa path $s$ node ise $b \le s$. Uzun path $L$ node ise en az yarısı black: $b \ge \lceil L/2 \rceil$. $\lceil L/2 \rceil > s$ ise coloring yoktur.
İpucu 3
Coloring varsa kısa path'leri tamamen black yap, red node'ları uzun path'lere art arda gelmeyecek şekilde serp. Sonra her tek child'lı node'u kontrol et.
Çözümü göster
Tree 1: en kısa path 3 node (örneğin root → 11 → 10 → NIL), en uzun 5 node (root → 6 → 4 → 2 → 1 → NIL). $\lceil 5/2 \rceil = 3 \le 3$, yani $b = 3$ ve kısa path'ler tamamen black olmalı. Uzun path'te 6 black (kısa path 9 → 6 → 8 → NIL'de olduğu için), 4 red, 2 black, 1 ve 3 red. 8'in tek child'ı 7 red olmalı (8'in boş sağ tarafında tek black NIL var). Coloring tektir:
Tree 2: 11'in sağı boş: root → 11 → NIL path'i 2 node, yani $b \le 2$. En uzun path yine 5 node, $b \ge 3$. Contradiction: No such red-black tree.
Tree 3: en kısa 3, en uzun 4 node: $\lceil 4/2 \rceil = 2 \le 3$. Birçok coloring var. Biri: $b = 3$, kısa path'ler black, uzun path'lerdeki 2 ve 10 red.
Section 4, soru 7: bu BST red-black tree olacak şekilde boyanabilir mi?
Proof: height ≤ 2 log(n+1)
Unbalanced bir red-black tree kurmaya çalış. Root'tan her NIL'e $b$ black var. En kısa path tamamen black: $b$ edge. En uzun path black'lerin arasına birer red sıkıştırır: en fazla $2b$ edge. Yani path'ler birbirinden en fazla 2 kat farklı. Bu yüzden tree "yeterince balanced".
Her $x$ için, $x$'in subtree'sinde ($x$ dahil) en az $2^{b(x)} - 1$ tane NIL olmayan node vardır. Induction, $x$'in height'ı üzerine.
- Base case: $x$ = NIL. $b(x) = 0$, $2^0 - 1 = 0$ node. ✓
- Child'ların black-height'ı: child black ise $x$'ten sayarken o child da sayılmıştı, kendi sayımından düşer: $b(\text{child}) = b(x) - 1$. Red ise hiçbir tarafa katkısı yok: $b(\text{child}) = b(x)$. Her iki durumda da $b(\text{child}) \ge b(x) - 1$.
- Inductive step: child'ların height'ı $x$'inkinden küçük, yani inductive hypothesis onlara uygulanır. $d(x)$ subtree'deki node sayısı olsun: $$d(x) = 1 + d(\ell) + d(r) \ge 1 + \left(2^{b(x)-1} - 1\right) + \left(2^{b(x)-1} - 1\right) = 2^{b(x)} - 1. \checkmark$$
| $b(x)$ | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| en az node $2^{b(x)}-1$ | 1 | 3 | 7 | 15 | 31 |
Root'tan en derin node'a, oradan da NIL'e inen path'i al. Root'tan sonra bu path'te $h + 1$ node var (NIL dahil). Property 4'e göre her red node'un hemen altındaki node black'tir; en alttaki NIL de black. Her red'i altındaki black'le eşleştir: farklı red'ler farklı black'lere gider, yani red sayısı ≤ black sayısı. O hâlde bu path'te en az $(h+1)/2$ black var ve bu sayı $b(r)$'dir (property 5): $$b(r) \ge \frac{h+1}{2} \ge \frac h2.$$
Lemma'yı root'a uygula, sonra Adım 2'yi kullan: $$n \;\ge\; 2^{b(r)} - 1 \;\ge\; 2^{h/2} - 1 \;\Longrightarrow\; n+1 \ge 2^{h/2} \;\Longrightarrow\; h \le 2\log_2(n+1).$$ Yani $h = O(\log n)$. Bölüm 4'teki lower bound ile birlikte $h = \Theta(\log n)$.
$n = 10^6$: $2\log_2(10^6 + 1) \approx 39{,}86$, yani height en fazla 39. Perfectly balanced bir tree'de bu 19 olurdu, sorted sırayla insert edilmiş düz BST'de ise $999\,999$.
- Inductive hypothesis child'lara uygulanıyor. Bunun için child'ların $b$ değerinin en az $b(x)-1$ olduğunu göstermeden geçme. Puanın yarısı bu cümlede.
- Lemma node'ları renkten bağımsız sayar: "en az $2^b - 1$ black node" yazma.
- Bound $2\log_2(n+1)$, $\log_2 n$ değil. Red-black tree perfectly balanced değildir; height'ı yalnızca $\Theta(\log n)$'dir.
"Prove that a red-black tree with $n$ nodes has height $O(\log n)$." (S5.5 ve slayt 82: "neden balanced olduğunu bilmelisiniz.")
İpucu 1
İki parça: (i) black-height'ı $b$ olan bir subtree'de en az kaç node var? (ii) Bir path'in en az ne kadarı black?
İpucu 2
(i)'yi height üzerine induction ile, (ii)'yi property 4 ile göster; sonra $n \ge 2^{b(r)}-1$ inequality'sini $h$ cinsinden yaz.
Kâğıda yazılacak hâli
Definition. $b(x)$: $x$'ten bir NIL'e giden path'teki black node sayısı ($x$ hariç, NIL dahil). Property 5 sayesinde well-defined.
Claim. $x$'in subtree'sinde en az $2^{b(x)}-1$ node var. Proof (height üzerine induction): NIL için $0 \ge 2^0 - 1$. Internal node $x$'in her child'ı $c$ için $b(c) \in \{b(x)-1,\ b(x)\}$, yani $b(c) \ge b(x)-1$; inductive hypothesis'ten $d(c) \ge 2^{b(x)-1}-1$. Böylece $d(x) \ge 1 + 2(2^{b(x)-1}-1) = 2^{b(x)}-1$.
Claim. $b(r) \ge h/2$. Root'tan en uzun NIL path'inde root'tan sonra $h+1$ node var. Property 4: red node'ların hemen altındaki node'lar black ve birbirinden farklı, son node olan NIL de black. Dolayısıyla node'ların en az yarısı black: $b(r) \ge (h+1)/2 \ge h/2$.
Conclusion. $n \ge 2^{b(r)}-1 \ge 2^{h/2}-1$, yani $h \le 2\log_2(n+1) = O(\log n)$. ∎
Lemma'nın inductive step'inde "her child için $b(\text{child}) \ge b(x) - 1$" neden doğru?
Rotation ve O(log n) işlemler
Insert ya da delete bir property'yi bozarsa red-black tree onu yerel düzeltmelerle onarır: recoloring ve rotation. Rotation bir node'u parent'ının yerine çıkarır. Oynat: node'lar yatayda hiç yer değiştirmiyor, sadece yukarı aşağı kayıyor.
- Right rotation ($x$'te): $x(y(\alpha, \beta), \gamma) \;\to\; y(\alpha, x(\beta, \gamma))$. Left rotation ($y$'de) bunun tersi.
- BST property korunur: önce de sonra da $\alpha < y < \beta < x < \gamma$. Yer değiştiren tek subtree $\beta$; o da $y$ ile $x$ arasındaki değerleri tuttuğu için iki yerde de doğru tarafta.
- Running time $O(1)$: subtree'lerin içinde ne olduğu önemsiz, sadece birkaç pointer değişir.
Red-black tree'de insert/delete'in case analizi (recolor, hangi case'te hangi rotation) bu derste sorulmuyor: L7 slayt 56 ve 82, S5.5 "Do not need to know how insertion/deletion etc works". Bilmen gereken:
- Beş property ve bir tree'nin geçerli olup olmadığını kontrol etmek.
- Property'lerin neden $h \le 2\log_2(n+1)$ verdiği (Bölüm 8).
- Property'lerin insert/delete sırasında $O(\log n)$ running time'da korunabildiği. Fikir tek cümle: yeni node red eklenir (black sayıları bozulmaz), bu yüzden sadece property 4 (ya da yeni node root ise property 2) bozulabilir; recoloring ve en fazla birkaç rotation'la yukarı doğru düzeltilir, path boyu $O(h)$.
| İşlem | Sorted array | Linked list | Düz BST | Red-black tree |
|---|---|---|---|---|
| Search | $O(\log n)$ | $O(n)$ | $O(h)$, worst $O(n)$ | $O(\log n)$ |
| Insert | $O(n)$ | $O(1)$ | $O(h)$, worst $O(n)$ | $O(\log n)$ |
| Delete | $O(n)$ | $O(n)$ | $O(h)$, worst $O(n)$ | $O(\log n)$ |
| Sorted output | $O(n)$ | sorted değil | $O(n)$ in-order | $O(n)$ in-order |
Right rotation neden BST property'sini bozmaz?
Sınavda nasıl soruluyor
2019-20, 2020-21 (iki vize ve cevaplı kâğıt), 2023-24 vize fotoğrafları ve pratik vizede BST ya da red-black tree sorusu yok. Lecture 7'nin heap kısmı bir kez, 2019-20 finalinde çıktı (aşağıda). Bu dönem kapsam Lecture 1–7 ve HW1–4 (Midterm Study Guide, 28.10.2026), yani sorular büyük ihtimalle CS161 tarzında olacak:
- "Is this a BST / a red-black tree?" (Bölüm 1, 6) ve "bu tree'yi boya" (Bölüm 7).
- Search/insert/delete'i bir tree üzerinde izle; iki child'lı delete (Bölüm 2, 3).
- Running time'ların $O(h)$ olması, sorted sırayla insert'te $h = n-1$ (Bölüm 4).
- Height proof'u (Bölüm 8) ve Lucky tipi lower bound argümanı (Bölüm 4).
Lecture 7'nin ilk yarısı heap. Binary min-heap: complete binary tree (son level hariç her level dolu, son level sola yaslı) ve her node'un key'i altındaki bütün key'lerden küçük. Insert ve extract-min $O(\log n)$, ama belirli bir key'i search etmek $\Theta(n)$. BST'de ise sol < node < sağ.
Section 4 ısınma: key'i 2025 olan elemanı $O(\log n)$'de bulmak sadece red-black tree ile olur. En küçüğü bulmak ikisiyle de olur. Median ise subtree size'ları tutulmazsa ikisiyle de bulunamaz.
Sorted olmayan bir array'de her eleman, sorted array'deki yerinden en fazla $k$ uzakta. Algorithm ilk $k+1$ elemandan bir min-heap kuruyor, sonra her adımda heap'ten en küçüğü çıkarıp output'a yazıyor ve kalan elemanlardan birini heap'e ekliyor. "Provide a tight asymptotic upper bound."
Kâğıtta "size k−1" yazıyor; doğru pencere $k+1$ eleman, aşağıdaki çözüm buna göre.
İpucu 1
Heap'te aynı anda en fazla kaç eleman var? O boyuttaki bir heap'te insert ya da extract-min'in running time'ı ne?
İpucu 2
Kaç kez extract-min + insert yapılıyor? Başlangıçtaki heap'i kurmanın maliyetini de ekle.
Çözümü göster
Heap size hiçbir zaman $k+1$'i geçmez, yani her insert ve extract-min $O(\log k)$. İlk heap'i kurmak en fazla $O(k\log k)$ (tek tek insert ile). Sonra $n$ kez extract-min ve (eleman kaldıkça) insert: $O(n\log k)$. Toplam $O(k\log k + n\log k) = O(n\log k)$, çünkü $k < n$.
Neden doğru: sorted array'deki $i$. eleman input'ta $i-k \ldots i+k$ aralığında. $i$. adımda heap, $i+k$'ye kadar okunmuş ve henüz çıkarılmamış elemanları tutar, dolayısıyla $i$. en küçük oradadır.
Özel durumlar: $k$ constant ise $O(n)$; $k \approx n$ ise $O(n\log n)$, HeapSort ile aynı.
Her node'da bir $(x, y)$ noktası, üç child var. Hiçbir iki nokta aynı $x$'i ya da aynı $y$'yi paylaşmıyor. $u = (x, y)$ için: left subtree'de $x_L < x,\ y_L < y$; middle subtree'de $x_M > x,\ y_M < y$; right subtree'de $x_R > x,\ y_R > y$. (5.1) Her nokta kümesi için böyle bir tree vardır, ispatla. (5.2) Her kümede height'ı $O(\log n)$ olan bir tree var mı?
İpucu 1 (5.1)
Hiçbir subtree'ye sığmayan bölge hangisi? $x' < x$ ve $y' > y$ olan bir nokta $u$'nun altında duramaz. Root'u öyle seç ki böyle nokta olmasın.
İpucu 2 (5.1)
En küçük $x$'li noktayı root yap. Diğerleri nereye düşer? Sonra $n$ üzerine induction.
İpucu 3 (5.2)
Ödevdeki ipucu: her tree'nin path olmak zorunda kaldığı bir dizilim bul. $x$ arttıkça $y$'nin azaldığı noktaları dene.
Çözümü göster
5.1 ($n$ üzerine induction). $n = 0$: boş tree. $n \ge 1$: $u$ en küçük $x$'li nokta olsun. Diğer her noktanın $x$'i daha büyük; $y$'si ya küçük (middle kümeye) ya büyük (right kümeye). Left küme boş. Her iki küme $n$'den az nokta içerir; inductive hypothesis'ten her biri için bir ternary search tree var. Bunları $u$'nun middle ve right child'ı olarak as. $u$ için üç koşul kümelerin tanımından, subtree'lerdeki node'lar için inductive hypothesis'ten sağlanır. ∎
5.2 Yanlış. Noktalar $(i,\, n-i)$, $i = 1, \dots, n$ olsun: $x$ büyüdükçe $y$ küçülüyor. Bir $u$ node'unun altındaki bir $p$ noktası left subtree'de olamaz ($x_p < x$ ise $y_p > y$), right subtree'de de olamaz ($x_p > x$ ise $y_p < y$). Demek ki her node'un en fazla bir child'ı var (middle), tree bir path ve height'ı $n - 1 = \Theta(n)$. Hangi tree'yi kurarsan kur sonuç bu. ∎
Section 4: "Bu data structure'da average case hızlı, worst case yavaş." Red-black tree mi, heap mi, ikisi mi, hiçbiri mi?
Son kontrol
Kâğıt kalemle çöz, sonra cevaba bak.
Aynı key'lerden oluşan iki farklı BST'nin kesinlikle ortak olan özelliği hangisi?
Bir red-black tree'de root'tan bir NIL'e giden bir path 100 edge. Başka bir root-NIL path'i kaç edge olabilir? (Concept check)
$n$ node'lu bir red-black tree'nin root'u sorted sırada $i$. eleman. $i$ hakkında ne söylenebilir? (Concept check)
İki child'lı $x$ silinirken successor nasıl bulunur?
Hangisi yanlış?