====== 3 - Binární stromy ====== /* Toto cvičení prochází úpravou, zatím využijte následující zdroje. {{:courses:a4b33alg:cviceni04upd.pdf| pdf}}, {{:courses:a4b33alg:cviceni3resene.pdf| pdf}} {{:courses:a4b33alg:cviceni3code.zip| zip}}, {{:courses:b4b33alg:tree.java |řešení}} */ ==== Připomenutí teorie ==== Přednáška 3 v oddíle [[courses:b4b33alg:prednasky|Přednášky]]. Stromy jsou hierarchická datová struktura. Mohou být binární, ternární, n-ární... {{:courses:b4b33alg:cviceni:tree-data-structure.png}} Obrázek z [[https://www.geeksforgeeks.org/tree-data-structure/|Geeks for geeks]]. * Hloubka je počet hran na cestě z kořene. * Výška je počet hran na cestě 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 (stromu) | | 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): Strom má všechny listy v nejhlubší úrovni (Pokud není vhodný počet uzlů, poslední úroveň má přebytek listů zleva) * **Vyvážený** (Balanced): Rozdíl hloubek podstromů pro každé sourozence musí být maximálně roven jedné. /*Na obrázku jsou příklady zleva {{ :courses:b4b33alg:cviceni:03_tree_types.png?400 |}}*/ {{ :courses:b4b33alg:cviceni:03_tree_types_text.png?600 |}} == 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 [[https://www.geeksforgeeks.org/preorder-vs-inorder-vs-postorder/|Geeks for geeks]]. {{ :courses:b4b33alg:cviceni:03_pruchody_stromem.jpg?400|}} ==== Ř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í (rozbalit)| 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í (rozbalit)| 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í (rozbalit)| Pouze **b)** je správně. Protipříklady: {{ :courses:b4b33alg:cviceni:03_3_couterexamples.png?400 |}} ++++ ----- **Řešená úloha 4:** {{ :courses:b4b33alg:cviceni:03_4_tree.png?400|}} Určete posloupnost zpracovaných uzlů daného stromu (napravo) při průchodu v pořadí * Pre-order * In-order * Post-order ++++ Pre-order (rozbalit)| B, O, H, M, R, L, K, J, A, E, D, V ++++ ++++ In-order (rozbalit)| M, H, R, O, K, L, B, A, E, J, V, D ++++ ++++ Post-order (rozbalit)| 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í (rozbalit)| $\Theta(N^3)$, protože průchod stromem má lineární složitost vůči počtu uzlů. ++++ ----- ==== Další úlohy ==== **Úloha 6:** Jaká je **maximální** možná hloubka $h$ binárního stromu s 300 listy? ---- **Úloha 7:** 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 8:** 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? ---- === Konstrukční úlohy === **Úloha 9:** Popište tvar binárního stromu, pro nějž platí: a) Průchod v pořadí Inorder a Preorder vytvoří stejnou posloupnost uzlů. \\ b) Průchod v pořadí Inorder a Postorder vytvoří stejnou posloupnost uzlů. \\ c) Průchod v pořadí Preorder a Postorder vytvoří stejnou posloupnost uzlů. \\ d) Průchod v pořadí Inorder a Preorder a Postorder vytvoří stejnou posloupnost uzlů. ---- **Úloha 10:** 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 11:** 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})$. ---- === Implementační úlohy === **Úloha 12:** Napište pseudokód funkce, která z binárního stromu odstraní všechny listy. ---- **Úloha 13:** Napište pseudokód funkce, která každému uzlu v binárním stromu přiřadí hodnotu jeho výšky. (Neboli výšky stromu který obsahuje všechny potomky daného uzlu) ---- **Úloha 14:** Napište pseudokód funkce, která vytvoří přesnou kopii binárního stromu. ---- **Úloha 15:** Napište pseudokód funkce, která daný binární strom modifikuje tak, že výsledný strom bude zrcadlovým obrazem původního. Musí platit, že výpis uzlů původního stromu v pořadí Inorder vytvoří opačně uspořádanou posloupnost než výpis uzlů modifikovaného stromu taktéž v pořadí Inorder. ---- **Úloha 16:** Aritmetický výraz obsahující celá čísla, závorky a operace $+,-,*,/$ (celočíselné dělení) může být reprezentován jako pravidelný binární strom. Popište, jak takový strom obecně vypadá, navrhněte implementaci uzlu a napište funkci, jejímž vstupem bude ukazatel na kořen stromu a výstupem hodnota odpovídajícího aritmetického výrazu. Příklad na obrázku reprezentuje $(2*(3+6/2))/4$. {{ :courses:b4b33alg:cviceni:03_13_expression_tree.png?200 |}} ----