⭐ Úloha 7: Obdoba úlohy 1, pro jiné posloupnosti. Sestavte operací insert BVS, poté proveďte delete na první 3 (nebo i další) prvky posloupnosti.

⭐ Úloha 8: 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 9: 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ý.

Úloha 10: Které z následující posloupností představují (min-)haldu o čtyřech prvcích uloženou v poli?

a) 1 3 4 2
b) 1 4 2 3
c) 1 2 4 3
d) 2 3 4 1
e) 1 3 2 4

Úloha 11: Pole $n$ prvků uspořádané v rostoucím pořadí lze považovat za haldu. Z této operace odstraníme standardní operací deleteTop() její vrchol. Určete za jakých okolností je možné, aby výsledné pole bylo po uvedené operaci opět celé uspořádané.

Úloha 12: V haldě, jejíž vrchol obsahuje minimální prvek haldy, máme najít prvek s maximálním klíčem. Jaká je asymptotická složitost této akce? Umíte vyřešit problém lépe (ne nutně asymptoticky) než v $n$ operacích.

Úloha 13: 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?

⭐ Úloha 14: 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 15: 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 16: 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ý?

Úloha 17: Je dáno $n$ ($n \in \mathbb{N}, n \ge 2$) navzájem různých celočíselných klíčů a prázdná halda. Všechny klíče vložíme jeden po druhém v náhodném pořadí do dané haldy.

⭐ Úloha 18: Z binární haldy obsahující $n^3$ prvků, jejíž kořen obsahuje nejmenší hodnotu z celé haldy, odstraníme $n$ nejmenších prvků. Jaká je asymptotická složitost této akce?

Úloha 19: Do binární haldy obsahující $n^{1.5}$ prvků, jejíž kořen obsahuje nejmenší hodnotu z celé haldy, přidáme $n$ prvků. Jaká je asymptotická složitost této akce?

⚡ Úloha 20: Danou haldu s $n$ prvky máme rozdělit na dvě haldy, tak že každá bude mít $n/2$ prvků. Předpokládejme, že původní halda je uložena v poli délky $n$ a nové haldy budou uloženy ve dvou připravených polích délky $n/2$. Navrhněte, jak rozdělit haldu v čase $\Theta(n)$.

Základní implementace BVS v Pythonu je k dispozici pro následující implmenentační pokusy. Nejprve doimplementujte operace insert a delete.

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

⭐ Úloha 22: 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 23: 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).

⭐ Úloha 24: 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.

Úloha 25: 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 26: 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.

💻 Úloha 27: Zkuste naimplementovat úlohu 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.