BPC-ALD_Zpracované_otazky_ke_zkousce

oblasti B (8, 15, 28, 31, 39) -> s = (5+9)/2 = 7 (

as = 28) -> 38>28 takže dále budeme hledat v oblasti B’ (31, 39) (což 

je pravá podoblast oblasti B) -> s = (8+9)/2 = 8 (

as = 31) -> 38>31 takže dále budeme hledat v oblasti B’  (39) (což je 

pravá podoblast podoblasti B’) -> s = (9+9)/2 = 9 (as = 39) -> 38<39 -> při pokusu o vytvoření další podoblasti dojde k 
index_min > index_max, což znamená, že daná podoblast neobsahuje žádný prvek -> hledaný prvek jsme nenašli, 
tudíž vyhledávání končí. 

(Stejsky) 

Video: https://www.youtube.com/watch?v=i2oBKUScQb0 

3. Je dáno pole obsahující např. vzestupně setříděné prvky: 1, 2, 4, 5, 7, 8, 15, 28, 31, 39. Nakreslete konkrétní 

binární vyhledávací strom a popište jednotlivé kroky vyhledávání pomocí binárního vyhledávacího stromu, pokud 
hledáme např. prvky: 15 a 9. (+++) 

Tvorbu vyváženého binárního vyhledávacího stromu jsme neimplementovali, ale na to přijdete, není to tak težké. 

Základem je, že všechny vrstvy musí být plně obsazeny krom poslední vrstvy. Dále pokud má uzel následníky, nalevo 
je vždy menší prvek a napravo větší prvek (v obrázku je naznačeno, že jednička nemůže být napravo od dvojky, 
sedmička nalevo od pětky atd...). Respektive celý levý podstrom daného prvku musí obsahovat prvky menší, než 
tento prvek 

– to samé platí kdekoli i pro pravé podstromy. Předpokládejme, že se ve stromu nemůže vyskytovat více 

prvků se stejnou hodnotu. 

Používáme především v případech, kdy se prvky množiny v čase mění - pro pole je toto velký problém, nevkládáme-li 

na konec pole. 

Časová složitost této metody je O(log2(n)). 

(Stejsky) 

Text z přednášky č. 13: 
Počáteční krok: 
•Uzel, který je v daném okamžiku vyhledávání aktuální budeme označovat 𝑢. 

•Na začátku jim bude kořen stromu. 

•Hledaná hodnota je 𝑥.