BPC-ALD - Skripta_rev2019_2

vyhledávání.  

1.  Který z uzlů stromu je kořen a který list? 
2.  Co je vyvážený binární strom? 

Cvičení   

1.  Jakou výšku má vyvážený binární strom se 100 uzly? 
2.  Co kdybychom oslabili požadavek na vyvážený strom tak, že bychom požadovali jen 

minimální výšku. Mohlo by to mít vliv na průměrnou vzdálenost uzlů stromu od 
kořene? Tj. mohl by nastat případ, že bychom mohli mít strom se stejnou minimální 
výškou a přitom s jiným průměrem vzdáleností od kořene, než má vyvážený strom dle 
definice uvedené v této kapitole. (Průměrná vzdálenost od kořene je součet vzdáleností 
všech uzlů od kořene dělený celkovým počtem uzlů ve stromu. Do celkového počtu 
uzlů je zahrnut i kořen. Jeho vzdálenost od kořene je přirozeně nula.) 

Úkoly k textu  

Odvoďte závislost výšky stromu na počtu uzlů pro vyvážený strom, který je r-ární. Kde r 
označuje, kolik následníků může mít každý uzel stromu (r

≥2).  

Řešení  

1.  Výška stromu je 6. 
2.  Následující obrázek ukazuje vlevo vyvážený binární strom se 4 uzly s průměrnou 

vzdáleností uzlů od kořene 1. Vpravo je binární strom se stejným počtem uzlů a se 
stejnou výškou, ale s průměrnou vzdáleností uzlů od kořene 1.25. Z toho lze usoudit, že 
pokud bychom nepožadovali, aby vyvážený strom měl neúplnou jen poslední vrstvu, 
mělo by to nepříznivý vliv na průměrnou vzdálenost uzlů od kořene. 

− 20 − 

Průvodce studiem  

Popis algoritmů začneme tříděním.Pak budou následovat algoritmy vyhledávání. I 

když v běžném životě častěji něco hledáme než třídíme… 

− 21 − 

3  Třídění 

Studijní cíle:  Definovat úlohu třídění a dále zavést pojmy jednak pro popis vlastního třídícího 
problému a dále pro klasifikaci a popisy algoritmů třídících metod. 

Klíčová slova: Uspořádání, klíč, vnitřní třídění, vnější třídění. 

Potřebný čas: 20 minut.