BPC-ALD - Skripta_rev2019_2

Závěr:  Složitost  binárního  vyhledávání  je 

Θ(log(n)).  Z ní  plyne,  že  binární  vyhledávání  je 

mnohem rychlejší než vyhledávání, kdy prvky nejsou uspořádány. 

Průvodce studiem  

Možná jste si nyní vzpomněli na třídění přímým vkládáním. Zde se místo pro vložení 

hledalo v setříděné části posloupnosti. Dalo by se tedy použít mnohem rychlejší binární 
vyhledávání. Na časovou složitost metody by to ale nemělo vliv, neboť tu zůstává ještě 
operace posunutí a ta má kvadratickou složitost. 

Binární 
vyhledávání má 
vynikající 
složitost. 

− 62 − 

Kontrolní otázky  

1.  Proč a jakým způsobem používáme zarážku při vyhledávání v nesetříděném poli? 
2.  Co je principem binárního vyhledávání? 
3.  Jaký je rozdíl časové složitosti při vyhledávání v nesetříděném a setříděném poli? 

Cvičení  

1.  Ukažte po jednotlivých krocích, jak proběhne binární vyhledání písmena K 

následujícím poli písmen. 

Úkoly k textu  

Třídění je časově náročnější než vyhledávání. Proto v případě pole nesetříděných údajů se 
nevyplatí ho napřed setřídit kvůli tomu, abychom pak mohli použít efektivnější binární 
vyhledávání. Nicméně v případě, že bychom v něm hledali velmi často, mohlo by to už být 
účelné ho napřed setřídit. Máme-li n prvků, kolikrát v nich musíme hledat, aby bylo rozumné je 
napřed setřídit? 

Řešení  

1.  Postup vyhledání ukazuje následující obrázek: 

4.3  Binární vyhledávací stromy 

Studijní cíle:  Tato část vysvětluje princip binárních vyhledávacích stromů, popisuje konstrukci 
AVL  stromů,  ukazuje,  jak  do  takového  stromu  přidat  prvek  nebo  z  něho  prvek  odebrat  a 
zejména, jak pak provést transformace, jimiž se zajistí zachování vyváženosti stromu. 

Klíčová slova: Vložení, odebrání, AVL strom.