13-Vyhledavani

1. 

𝑛 

2. 

𝑛

2

3. 

𝑛

22

4. 

𝑛

23

… 

… 

𝑘 − 𝑡ý 

𝑛

2𝑘−1

Složitost metody binárního vyhledávání  

• Vyhledávání končí nejpozději, když délka prohledávané části je už 

pouze jeden prvek. Pak platí: 

1 =

𝑛

2𝑘−1

• Úpravami dostaneme:  

2𝑘−1 = 𝑛 

𝑘 = 𝑙𝑜𝑔2 𝑛 + 1 

• Míra složitosti je: 𝑙𝑜𝑔2 𝑛  
• Binární vyhledávání je mnohem rychlejší, než vyhledávání, kdy prvky 

nejsou uspořádány.  

Binární vyhledávací stromy 

Použití stromů pro vyhledávání 

• Binární vyhledávání má velmi příznivou časovou složitost. 
• Problém nastane, když se množina prvků v čase mění. 

• Při použití pole, je problém vložit nebo odebrat prvek, pokud se nenachází na 

konci pole. 

• V případech, kdy se prvky množiny mění v čase, je výhodné prvky 

ukládat do uzlů stromů. 

• Nejjednodušším případem jsou binární vyhledávací stromy. 

Binární vyhledávací strom 

• Má v každém uzlu uložen právě jeden prvek. 
• Uvažujme uzel s prvkem 𝑐. 
• Pak musí platit: 

• Prvek v levém následníku uzlu s prvkem 𝑐 a rovněž všechny prvky v celém 

levém podstromu jsou menší než je hodnota prvku 𝑐.  

• Prvek v pravém následníku uzlu s prvkem 𝑐 a rovněž všechny prvky v celém 

pravém podstromu jsou větší než je hodnota prvku 𝑐. 

• Předpokládejme, že se ve stromu nemůže vyskytovat více prvků se stejnou 

hodnotu. 

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

• 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 𝑥. 

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

• Průběžný krok 

• Vezmeme prvek uložený v aktuálním uzlu 𝑢, označme ho 𝑐, a provedeme jeho 

srovnání s hledanou hodnotou 𝑥.