13-Vyhledavani

• Je-li 𝑥 < 𝑐, hledání musí pokračovat v levém podstromu. 

• Jako nový aktuální uzel 𝑢 použijeme levého následníka současného aktuálního uzlu a znovu 

provedeme průběžný krok. 

• Pokud současný uzel levého následníka nemá, vyhledávání končí, hledaný prvek není ve 

stromu obsažen. 

• Pokud není 𝑥 < 𝑐, srovnáme zda 𝑥 > 𝑐. Pokud ano, je nutno v hledání pokračovat v 

pravém podstromu. 

• Jako nový aktuální uzel 𝑢 použijeme pravého následníka současného aktuálního uzlu a znovu 

provedeme průběžný krok. 

• Pokud současný uzel pravého následníka nemá, vyhledávání končí, hledaný prvek není ve 

stromu obsažen. 

Postup vyhledávání v binárním stromu 

• Průběžný krok - pokračování 

• Pokud není 𝑥 < 𝑐 a zároveň ani 𝑥 > 𝑐, musí být 𝑥 = 𝑐. Hledání končí, neboť prvek 

obsažený v aktuálním uzlu 𝑢 je hledaným prvkem. 

Ukázka vyhledávání pomocí binárního stromu 

Máme najít prvek 
s hodnotou 𝑥 = 5. 

6 

7 

8 

9 

1 

4 

5 

5 < 6 

4 < 5  

5 = 5 

Příklad vyhledávání pomocí binárního 
vyhledávacího stromu 
• Je dáno pole obsahující vzestupně setříděné prvky:  

1 2 4 5 7 8 15 28 31 39 . 

• Popište konkrétně jednotlivé kroky vyhledávání pomocí binárního 

vyhledávacího stromu, pokud hledáme: 

a) Prvek s hodnotou 15 
b) Prvek s hodnotou 3  

Složitost metody vyhledávání pomocí 
binárního vyhledávacího stromu 
• Míra složitosti je: 𝑙𝑜𝑔2 𝑛  

Vyhledávání pomocí indexace 

• Nejrychlejší způsob vyhledávání. 
• Klíč, podle kterého vyhledáváme, je přímo index prvku v poli nebo v 

souboru. 

• Složitost má konstantní hodnotu (tj. nezávislá na počtu prvků). 

Hašování 

Hašování 

• Chceme využít výhody indexování – konstantní složitosti. 
• Uvažujme hašovací tabulku realizovanou jako pole. 
• Někdy označováno jako: tabulka s rozptýlenými hesly, hashtable. 
• V hašovací tabulce máme např. řetězce, datum, …, podle kterých