====== 5 - Binární vyhledávací strom (BVS) ======
/*
<WRAP info> Toto cvičení prochází úpravou, zatím využijte následující zdroje.

{{:courses:a4b33alg:cviceni07upd.pdf|pdf}},
{{:courses:a4b33alg:cviceni_05.pdf|pdf}},
{{:courses:a4b33alg:cviceni5resene.pdf| pdf}},


{{:courses:a4b33alg:cviceni5code.zip| zip}},
[[https://drive.google.com/file/d/1FC-c9nUnRNhSBF_bVsdkMZzKCjsJDRP4/view|kódy cv. út 12:45, 16:15]]
</WRAP>
*/

==== Připomenutí teorie ====

Přednáška 5 v oddíle [[courses:b4b33alg:prednasky|Přednášky]].

{{ :courses:b4b33alg:cviceni:05_bst.svg| 400}}
Binární vyhledávací strom (Binary Search Tree - BST) je binární strom, který splňuje v každém uzlu podmínku, že všechny klíče v levém podstromu mají nižší hodnotu než klíč uzlu a v pravém podstromu jsou klíče hodnoty vyšší.

=== Operace ===
**Vyhledávání (''find'')** probíhá podobně jako v půlení intervalu, akorát místo vybírání prostředního indexu nahlížíme do kořene (pod)stromu.

**Vkládání (''insert'')** probíhá podobně, hledáme prvek který chceme přidat, jakmile dojdeme na konec stromu (list / chybějící větev), přidáme prvek na správnou stranu.

**Odstraňování (''delete'')** je nejsložitější, protože musíme opravit strukturu stromu. Nalezneme uzel s nejmenším klíčem v pravém podstromu (nebo nejvyšším v levém), smažeme ten uzel, a přesuneme jeho klíč do uzlu který mažeme.


==== Řešené úlohy ====

**Řešená úloha 1:**

Čísla z následující posloupnosti postupně vkládejte do prázdného binárního vyhledávacího stromu (BVS), který nevyvažujte. Jak bude vypadat takto vytvořený BVS?

10,  16,  5,  17,  4,  15,  3,  1,  23,  13,  2,  11

++++ Výsledný strom (rozbalit)|
{{ :courses:b4b33alg:cviceni:05_1_sol1.svg |}}
++++

Z něj pak postupně odstraňte první tři prvky (10, 16, 5). Jak bude vypadat výsledný BVS?

++++ Strom(y) po odstranění (rozbalit)|
<WRAP column 30%>
{{ :courses:b4b33alg:cviceni:05_1_sol2_1.svg |}}
</WRAP>
<WRAP column 30%>
{{ :courses:b4b33alg:cviceni:05_1_sol2_2.svg |}}
</WRAP>
<WRAP column 30%>
{{ :courses:b4b33alg:cviceni:05_1_sol2_3.svg |}}
</WRAP>
<WRAP clear>
</WRAP>
++++

-----

**Řešená úloha 2:**
Jaká je složitost operace ''insert'' v obecném BVS s $n$ uzly a hloubkou $d$? Vyjádřete nejprve pomocí $d$ a převeďte na funkci s neznámou $n$.

++++ Odpověď (rozbalit)|
Platí $\Theta\left( d \right)$ tedy pro obecný BVS je složitost $\mathrm{O}\left( n \right)$.
++++

Jaká je složitost operace ''find'' a ''delete''?
++++ Odpověď (rozbalit)|
Je stejná.
++++


A co pro vyvážený BVS?
++++ Odpověď (rozbalit)|
Pro vyvážený BVS je složitost těchto operací $\mathrm{O}\left( \log(n) \right)$.
++++

-----

**Řešená úloha 3:**
Předpokládejme, že binární vyhledávací strom obsahuje přirozená čísla mezi 1 a 1000.
Která z následujících sekvencí navštívených uzlů nemůže nastat, pokud hledáne klíč 363?

**a)** 2, 252, 401, 398, 330, 363 \\
**b)** 399, 387, 219, 266, 382, 381, 278, 363 \\
**c)** 3, 923, 220, 911, 244, 898, 258, 362, 363 \\
**d)** 4, 924, 278, 347, 621, 299, 392, 358, 363 \\
**e)** 5, 925, 202, 910, 245, 363


++++ Řešení (rozbalit)|
**d)** Hodnota 299 nemůže být po 621, protože by byla v levém podstromu uzlu s klíčem 347.
++++

-----

**Řešená úloha 4:**
V jakém pořadí vypíšeme prvky binárního vyhledávácího stromu, pokud ho projdeme inorder?

++++ Řešení (rozbalit)|
Vzestupné uspořádání.
++++

-----

**Řešená úloha 5:**
Mějme binární vyhledávací strom s $n$ uzly. Jaká je asymptotická složitost operace, která spočítá klíče, jejichž hodnota je menší, než $x$? 

++++ Řešení (rozbalit)|
Lze použít procházení inorder pro nalezení prvního prvku, jehož hodnota je větší, než $x$. Jednoduše pak spočítáme počet prohledaných uzlů.

Složitost tohoto přístupu je $\mathrm{O}(n)$.
++++

Co v případě, že si budeme ukládat pomocnou informaci? Jakou?

++++ Řešení (rozbalit)|
Efektivnějším by mohlo být pamatovat si velikost každého podstromu (rozmyslete jak náročné je udržovat tuto informaci při vkládání a mazání klíčů).

Pak by nám stačilo vyhledat prvek s hodnotou $x$ a přičíst velikosti všech
levých podstromů vrcholů cesty, které jsme nenavštívili plus počet
navštívených uzlů, které měly klíče menší. Asymptotická složitost je stále
$O(n)$, ale v případě vyváženého stromu poklesne na $\Theta(\log_2 n)$.
++++

-----
==== Další úlohy ====

<wrap todo>**Úloha 6:**</wrap>
Obdoba úlohy 1, pro jiné posloupnosti. Sestavte operací ''insert'' BVS, poté proveďte ''delete'' na první 3 (nebo i další) prvky posloupnosti.

  * 14, 24, 5, 13, 1, 3, 22, 10, 19, 11
  * 17, 4, 15, 2, 5, 9, 1, 12, 3, 19, 16, 18

----

<wrap todo>**Úloha 7:**</wrap>
Mějme klíče $1, 2, 3, \ldots, n$. Číslo $n$ je liché. Nejprve
vložíme do BVS všechny sudé klíče v rostoucím
pořadí a pak všechny liché klíče, také v rostoucím
pořadí.

Jaká bude hloubka výsledného stromu?

Jak by se změnil tvar stromu, kdybychom liché
klíče vkládali v náhodném pořadí? 
----

**Úloha 8:**
V jakém pořadí máme vkládat $2^n − 1$ prvků do binárního vyhledávacího
stromu tak, aby byl úplný? Formulujte nutnou a postačující
podmínku, aby byl výsledný vyhledávací strom úplný.

/*
Existuje právě jeden úplný strom o daných $2^n − 1$ prvcích. Pokud ho
chceme vybudovat, je nutnou a postačující podmínkou, abychom získali
stejný strom, že vkládáme vždy uzel dříve než jeho potomky. Takto
docílíme toho, že strom budujeme odshora.

Při vkládání je jen jedno možné místo, kam lze nový uzel vložit. Pokud
vkládáme další uzel a jeho rodič a všechny uzly na cestě ke kořeni z
úplného stromu jsou již vloženy do stromu, pak je uzel vložen na
stejné místo jako v úplném stromě. Protože uzel vkládáme vždy před
jeho potomky, platí, že získáme úplný strom.
*/
----

=== Úlohy na složitost ===

**Úloha 9:**
Mějme úplný BVS, který obsahuje $2^n-1$ prvků.
Předpokládejte, že během operace ''find'' stráví
program v každém navštíveném uzlu právě $1\, \mu s$ a že
další případné činnosti jsou v této době zahrnuty.

Předpokládejte, že každý klíč v tomto BVS je
vyhledáván stejně často a že jiné klíče se v něm
nevyhledávají.

Jaká je průměrná doba operace ''find''?

//Bonus:// Co kdybychom v 50% případů hledali klíč, který se ve stromu nevyskytuje?
----

<wrap todo>**Úloha 10:**</wrap>
Je dán BVS s $n$ uzly. Máme za úkol spočítat hodnotu
součtu všech klíčů v tomto stromě.

Jaká bude složitost této operace, když to implementujeme efektivně?
----

**Úloha 11:**
Je dán BVS a dvojice klíčů $x$, $y$ ($x < y$). Máme určit,
kolik je v tomto BVS takových klíčů $z$, pro které platí
$x < z < y$.

Jaká bude asymptotická složitost této operace za
předpokladu, že v uzlech stromu neukládáme žádné
další pomocné informace?
----

**Úloha 12:**
Operace ''R'' z BVS opakovaně
odstraňuje operací ''delete'' vždy ten uzel, který má
alespoň jednoho potomka a přitom klíč v
odstraňovaném uzlu je největší možný. ''R'' končí tesně
předtím, než by odstranila kořen BVS.

Jakou bude mít ''R'' složitost? Co když by byl BVS vyvážený?
----

=== Implementační úlohy ===

[[https://drive.google.com/file/d/1FC-c9nUnRNhSBF_bVsdkMZzKCjsJDRP4/view | Základní implementace BVS v Pythonu]] je k dispozici pro následující implmenentační pokusy. Nejprve doimplementujte operace ''insert'' a ''delete''.

**Úloha 13:**
Napište rekurzivní verze operací: TreeMinimum, která vrátí referenci na uzel s nejmenší hodnotou v BVS.
----

<wrap todo>**Úloha 14:**</wrap>
Napište funkci, jejímž vstupem bude ukazatel (=reference) na uzel $X$ v BVS a výstupem ukazatel
(=reference) na uzel s nejbližší vyšší hodnotou ve stromu.
----

**Úloha 15:**
Přidejte do uzlu pomocnou proměnnou ''count''. Navrhněte nerekurzivní proceduru, která do atributu ''count'' v každém uzlu zapíše počet vnitřních uzlů
v podstromu, jehož kořenem je tento uzel (včetně tohoto uzlu, pokud sám není listem).
----

<wrap todo>**Úloha 16:**</wrap>
Napište (ne)rekurzivní funkci, která přetvoří strom na "zrcadlový obraz" původního. Tedy výpisem klíčů v pořadí inorder získáme opačně uspořádanou
posloupnost.

/* Fce v každém uzlu daného BVS zamění levý a pravý podstrom */
----

**Úloha 17:**
Uzel binárního binárního vyhledávacího stromu obsahuje tři složky: Klíč a ukazatele na pravého a levého
potomka.

Navrhněte rekurzivní funkci (vracející ''bool''), která porovná, zda má dvojice stromů stejnou strukturu. Dva
BVS považujeme za strukturně stejné, pokud se dají nakreslit tak, že po položení na sebe pozorovateli
splývají, bez ohledu na to, jaká obsahují data.

//Bonus:// Upravte předchozí funkci tak, aby zjistila, zda jsou dva BVS shodné, t.j. zda se shodují
strukturou i svými daty.
----

**Úloha 18:**
Navrhněte algoritmus, který spojí dva BVS $A$ a $B$. Spojení proběhne tak, že všechny uzly z $B$ budou
přesunuty do $A$, přičemž se nebudou vytvářet žádné nové uzly ani se nebudou žádné uzly mazat. Přesun
proběhne jen manipulací s ukazateli. Předpokládejte, že v každém uzlu v $A$ i v $B$ je k dispozici ukazatel na
rodičovský uzel.
----

<wrap caution>💻**Úloha 19:**</wrap>
Zkuste naimplementovat úlohu [[https://open.kattis.com/problems/insert | Tree Insert Permutations]]. Cílem je spočítat permutace posloupnosti klíčů, které vedou ke stejnému stromu pokud jsou jeden za druhým přidávány do stromu pomocí operace ''insert''.
----