Search
Přednáška 3 v oddíle Přednášky.
Stromy jsou hierarchická datová struktura. Mohou být binární, ternární, n-ární…
Obrázek z Geeks for geeks.
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).
Binární strom může být:
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.
Ř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ů?
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ý
Pouze b) je správně. Protipříklady:
Řešená úloha 4: Určete posloupnost zpracovaných uzlů daného stromu (napravo) při průchodu v pořadí
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}$?
$\Theta(N^3)$, protože průchod stromem má lineární složitost vůči počtu uzlů.
Ú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?
Ú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:
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})$.
Ú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$.