# Programování II pro matematiky ## Teoretické cvičení 08 **21 4. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Příklady - Řešení příkladů --- ### Opakování - BST - Binární vyhledávací strom (Binary Search Tree - BST) - Vrchol má maximálně dva následníky (je to binární strom). - V levém podstromu vrcholu jsou pouze vrcholy s menší hodnotou klíče. - V pravém podstromu vrcholu jsou pouze vrcholy s větší hodnotou klíče. ```python class BST: """vrchol binárního stromu""" def __init__(self, x = None): self.info = x # uložená hodnota self.levy: Optional[BST] = None # levý syn self.pravy: Optional[BST] = None # pravý syn ```
--- - Binární vyhledávací strom (nejhorší případ)
-- V nejhorším případě trvá nalezení jednoho prvku $\mathcal{O}(N)$ --- ### Opakování - AVL-tree - AVL strom - Je to Binární vyhledávací strom - Délka nejdelší větve levého a pravého podstromu každého uzlu se liší nejvýše o 1 ```python class AVL(BST): def __init__(self, x = None): super.__init__(x) self.balance = 0 # = výška(p.levy) - výška(p.pravy) ```
--- (pro zajímavost LL vyvažovací rotace)
--- ### Opakování - Rekurzivní generování **Příklad:** Vypsat všechna k-ciferná čísla v poziční soustavě o základu n ```python # k zakódováno v programu for i1 in range(n): for i2 in range(n): for i3 inrange(n): for i4 inrange(n): print(f"{i1} {i2} {i3} {i4}") ``` -- ```python k = 4 # počet cifer n = 3 # číselná soustava def cislo(c: List[int]) -> None: for i in range(n): c.append(i) if len(c) < k: cislo(c) else: print(c) c.pop() cislo([]) ``` --- ### Příklady (1) Najděte algoritmus a určete jeho časovou a prostorovou složitost v nejhorším případě. **Na vstupu máme odkaz na kořen binárního stromu:** 1. Chceme zjistit, zda je zadaný binární strom symetrický podle svislé osy procházející kořenem (jde nám pouze o tvar stromu, nikoliv o hodnoty uložené v jeho uzlech). 2. Na vstupu máme binární vyhledávací strom obsahující čísla. Vypište čísla od nejmenšího po největší. 3. Na vstupu máme binární vyhledávací strom obsahující čísla. Na vstupu dostaneme číslo (číslo nemusí být v BST) a chceme vrátit největší menší prvek v daném BST. *Příklad:* Strom obsahuje `1, 2, 4, 6`, pro vstup `4` vrátíme `2` ; pro vstup `5` vrátíme `4`. 4. Chceme pro každý vrchol binárního (vyhledávacího) stromu určit jeho balance (balance podle definice z AVL stromu). --- ### Příklady (2) **Rekurze:** 1. Chceme vypsat všechny rostoucí posloupnosti vytvořené z množiny čísel $\\{1, 2, \dots, N\\}$ 2. Chceme vypsat všechna korektní uzávorkování pomocí $N$ párů závorek. *Příklad:* Pro $N = 3$ dostaneme: - `()()()` - `(())()` - `()(())` - `(()())` - `((()))` --- ### Řešení (1) Chceme zjistit, zda je zadaný binární strom symetrický podle svislé osy procházející kořenem (jde nám pouze o tvar stromu, nikoliv o hodnoty uložené v jeho uzlech). -- **Algoritmus:** ```python def je_stejny(levy, pravy): if levy is None and pravy is None: return True else: if je_stejny(levy.levy, pravy.pravy) and je_stejny(levy.pravy, pravy.levy): return True else: return False return je_stejny(koren.levy, koren.pravy) ``` -- Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ --- ### Řešení (2) Na vstupu máme binární vyhledávací strom obsahující čísla. Vypište čísla od nejmenšího po největší. -- **Algoritmus:** ```python def vypis(strom: BST): if strom is None: return else: vypis(strom.levy) print(strom.info) vypis(strom.pravy) ``` -- Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ --- ### Řešení (1) Chceme vypsat všechny rostoucí posloupnosti vytvořené z množiny čísel $\\{1, 2, \dots, N\\}$ -- **Algoritmus:** ```python def _vypis(posl: List[int], krok: int) -> None: if krok <= len(posl): posl[krok]=0 _vypis(posl, krok + 1) posl[krok]=krok _vypis(posl, krok + 1) else: for i in posl: if i > 0: print(i, end=" ") print() def vypis(N: int) -> None: seznam = [0] * N _vypis(seznam, 0) ``` --- **Alternativní algoritmus:** ```python def vypis(N: int) -> None: # 000 znamená ""; 100 znamená "1" a 011 znamená "2 3" for binarni_cislo in range(2^N): for i in N: if binarni_cislo & (1 << i) == (1 << i): print(i, end=" ") ``` -- Časová složitost $\mathcal{O}(2^N)$, paměťová složitost $\mathcal{O}(N)$