5 - Binární vyhledávací strom (BVS)

Přednáška 5 v oddíle Přednášky.

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šší.

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á ú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)

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)

Ř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)

Jaká je složitost operace find a delete?

Odpověď (rozbalit)

A co pro vyvážený BVS?

Odpověď (rozbalit)

Ř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)

Ř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)

Ř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)

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

Řešení (rozbalit)

Úloha 6: 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

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

Ú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?

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

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.

Úloha 14: 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).

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

💻Úloha 19: 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.