Algoritmizace B4B33ALG
Algoritmizace

4 - Binární stromy a binární vyhledávací strom

Připomenutí teorie

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

Stromy jsou hierarchická datová struktura. Mohou být binární, ternární, n-ární…

tree-data-structure.png

Obrázek z Geeks for geeks.

  • Hloubka uzlu je počet hran na cestě do něj z kořene.

  • Výška uzlu je počet hran na cestě z něj do nejvzdálenějšího listu.

  • Výška stromu je počet hran na cestě z kořene do nejvzdálenějšího listu.

Dále existuje Předek (Ancestor), což je uzel, který je od rodiče dál směrem ke kořeni.

Uzel, který není list, se nazývá vnitřní (inner), a říká se, že se “větví” na potomky. Podstrom každého potomku je pak větev (branch).

English Česky

Node (Vertex)

Uzel

Key

Klíč (Hodnota v uzlu)

Edge

Hrana

Root

Kořen

Leaf

List

Height

Výška (uzlu/podstromu)

Depth

Hloubka (uzlu)

Level

Úroveň (Patro)

Parent

Rodič

Child

Potomek

Siblings

Sourozenci

Subtree

Podstrom

Typy

Binární strom může být:

  • Pravidelný (Regular): Každý uzel má buď nula, nebo dva potomky.

  • Úplný (Complete): Všechny úrovně stromu jsou zcela zaplněné, kromě případně poslední úrovně, jejíž uzly jsou zarovnané zleva.

  • Vyvážený (Balanced): Pro každý uzel musí být rozdíl výšek jeho levého a pravého podstromu maximálně roven jedné (neexistující podstrom má výšku -1).

tree types

Průchody

struct TreeNode{
    int val;
    TreeNode* left, right;
};

void traversal(TreeNode* node) {
    if (node){
        cout << node->val << " "; // pre-order
        traversal(node->left);      // levý podstrom
        cout << node->val << " "; // in-order
        traversal(node->right);     // pravý podstrom
        cout << node->val << " "; // post-order
    }
}

Vizualizace průchodů na Geeks for geeks.

tree traversal

Binární vyhledávací strom

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

bst

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.


(Min) Halda

Halda (Heap) je binární strom, kde platí pravidlo, že klíče v obou potomcích jsou vyšší (nebo rovni) než v jejich rodiči. Haldu lze zapsat do pole, které reprezentuje úplný strom. Někdy se specifikuje jako min-heap, protože v kořeni je minimum. Alternativně můžeme sestrojit max-heap, kde je v kořeni maximum a potomci jsou vždy menší (nebo rovni).

Vkládání (insert): Pokud přidáváme prvek, vložíme ho na konec pole a “probubláváme” ho nahoru skrze strom, dokud má klíč v rodiči větší hodnotu.

Odstraňování (deleteTop): Pokud odebíráme kořen (jiné prvky neodebíráme), nahradíme ho posledním prvkem z haldy a opravujeme haldu směrem dolů, záměnou za menšího (pro min-heap) z jeho potomků (pokud je menší než klíč v rodiči.

Haldu lze využít například na prioritní frontu (znáte z PRP) a heap sort.

08_heap.svg

Řešené úlohy

Řešená úloha 1: Jaká je minimální možná hloubka \(h\) binárního stromu s 300 listy? Jak bude takový strom vypadat?

Řešení

Půjde o úplný binární strom. V poslední úrovni bude \(2^h\) listů. Takže

\[h = \left\lceil\log_2(300)\right\rceil = 9.\]

Co když bude strom ternární?

Řešená úloha 2: Pravidelný binární strom má \(N\) uzlů. Kolik má listů?

Řešení

Listů má \(\frac{N+1}{2}\) což lze dokázat pomocí indukce.

Intuitivně, pravidelný strom má lichý počet uzlů, přidání uzlů je možné jen po dvou, což změní celkový počet listů o jeden.

Řešená úloha 3: Daný binární strom má tři listy. Tudíž:

a) má nejvýše dva vnitřní uzly
b) počet vnitřních uzlů není omezen
c) všechny listy mají stejnou hloubku
d) všechny listy nemohou mít stejnou hloubku
e) strom je pravidelný

Řešení

Pouze b) je správně. Protipříklady:

counterexamples

Řešená úloha 4: Určete posloupnost zpracovaných uzlů daného stromu při průchodu v pořadí:

  • Pre-order

  • In-order

  • Post-order

tree
Pre-order

B, O, H, M, R, L, K, J, A, E, D, V

In-order

M, H, R, O, K, L, B, A, E, J, V, D

Post-order

M, R, H, K, L, O, E, A, V, D, J, B

Řešená úloha 5: Algoritmus \(\mathcal{A}\) provádí průchod v pořadí in-order binárním vyváženým stromem s \(N\) uzly a v každém uzlu provádí navíc další (nám neznámou) akci, jejíž složitost je \(\Theta(N^2)\). Jaká je asymptotická složitost \(\mathcal{A}\)?

Řešení

\(\Theta(N^3)\), protože průchod stromem má lineární složitost vůči počtu uzlů.

Řešená úloha 6:

Čí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

sol

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í

sol

sol

sol

Řešená úloha 7: 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ěď

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ěď

Je stejná.

A co pro vyvážený BVS?

Odpověď

Pro vyvážený BVS je složitost těchto operací \(\mathrm{O}\left( \log(n) \right)\).

Řešená úloha 8: 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í

d) Hodnota 299 nemůže být po 621, protože by byla v pravém podstromu uzlu s klíčem 347. Z uzlu s klíčem 347 totiž jdeme do pravého podstromu, protože 621 je větší než 347. 299 naopak musí být nalevo od 347.

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

Řešení

Vzestupné uspořádání.

Řešená úloha 10: 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í

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í

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)\).

Řešená úloha 11: Která z následujících posloupností představuje (min-)haldu uloženou v poli?

a) 9 5 4 6 3
b) 5 4 2 3 9
c) 3 8 9 5 6
d) 5 1 8 9 1
e) 1 3 6 5 4

Řešení

e)

Další úlohy

Binární strom

Úloha 12: Jaká je maximální možná hloubka \(h\) binárního stromu s 300 listy?

Úloha 13: Algoritmus \(\mathcal{A}\) provede jeden průchod binárním stromem s hloubkou \(H\). Při zpracování celé \(k\)-té úrovně (= všech uzlů s hloubkou \(k\)) provede \(k+H\) operací. Jaká je asymptotická složitost \(\mathcal{A}\)? Vyjádřete ji jako funkci proměnné \(H\).

⭐ Úloha 14: Máme projít pravidelným binárním stromem a navštívit všech jeho \(N\) uzlů. Jediné dvě možnosti pohybu v každém uzlu jsou buď posun do některého bezprostředního potomka nebo skok zpět do kořene stromu. Každý posun nebo skok trvá jednu mikrosekundu.

Za jak dlouho lze úkol splnit, pokud
a) strom má minimální možnou hloubku,
b) strom má maximální možnou hloubku?

Bonus: Strom s kolika uzly zvládne algoritmus zpracovat za jednu sekundu?

Úloha 15: Popište tvar binárního stromu, pro nějž platí:

  1. Průchod v pořadí Inorder a Preorder vytvoří stejnou posloupnost uzlů.

  2. Průchod v pořadí Inorder a Postorder vytvoří stejnou posloupnost uzlů.

  3. Průchod v pořadí Preorder a Postorder vytvoří stejnou posloupnost uzlů.

  4. Průchod v pořadí Inorder a Preorder a Postorder vytvoří stejnou posloupnost uzlů.

⭐ Úloha 16: Při průchodu stromem v pořadí Inorder a Preorder získáme následující posloupnosti klíčů uložených v jeho jednotlivých (celkem devíti) uzlech:

Inorder

45

71

98

47

50

62

87

3

79

Preorder

50

47

71

45

98

62

3

87

79

Rekonstruujte tvar stromu.

Bonus: Navrhněte a formulujte algoritmus, který zkonstruuje libovolný strom z jeho Inorder a Preorder posloupností.

⭐ Úloha 17: Navrhněte algoritmus, který pro danou vstupní hodnotu \(N\) vytvoří binární strom s \(N\) uzly jehož hloubka nebude vyjádřena výrazem ani \(\Theta(\log(N))\) ani \(\Theta(N)\), ale výrazem \(\Theta(\sqrt{N})\).

Binární vyhledávací strom

⭐ Úloha 18: Obdoba úlohy 6, 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 19: 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 20: 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ý.

Odpověď

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.

Halda

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

Úlohy na složitost

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

  1. Jaká je asymptotická složitost tohoto procesu?

  2. Je možné, že pro některé speciální pořadí klíčů bude asymptotická složitost menší nebo větší než v náhodném případě?

⭐ Úloha 29: 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 30: 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 31: 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)\).

Implementační úlohy

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

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

⭐ Úloha 33: 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 34: 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 35: 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.

Odpověď

Funkce v každém uzlu daného BVS zamění levý a pravý podstrom

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