BPC-ALD - Skripta_rev2019_2

Strom je 
acyklický graf. 

− 17 − 

s ním spojeny hranami. Tyto uzly mohou mít rovněž následníky, které jsou opět pod nimi a jsou 
s nimi opět spojeny hranami. Uzly, které nemají žádné následníky, nazýváme listy. Každý uzel 
vyjma  kořene  je  hranou  spojen  s  právě  jedním  uzlem,  který  je  nad  ním.  Tento  uzel  je  jeho 
předchůdce. 

Na kreslení uzlů a hran nejsou žádná zvláštní omezení. Uzly většinou kreslíme jako kružnice, 
hrany jako rovné čáry. 

Běžně  používané  stromy  mají  zpravidla  omezeno,  kolik  může  mít  uzel  následníků.  V tomto 
ohledu nejjednodušší stromy jsou stromy, v nichž každý uzel může mít nejvýše dva následníky. 
Používají se poměrně často a říkáme jim binární stromy. 

Při použití stromů v algoritmech si uchováváme ukazatel na kořenový uzel. K libovolnému uzlu 
se pak dostaneme tak, že začneme od kořene a postupně po hranách přecházíme k nižším uzlů, 
až  dojdeme  k žádanému  uzlu.  Přechod  od  nějakého  uzlu  po  hraně  k jeho  následníkovi 
považujeme za jednu základní operaci. Počet operací potřebný k tomu, abychom se od kořene 
dostali k danému uzlu, je roven počtu hran, které jsou na cestě od kořene k tomuto uzlu. Tento 
počet  nazýváme  vzdáleností  uzlu  od kořene.  Maximum  ze  vzdáleností  uzlů  od  kořene  stromu 
nazveme výškou stromu. Výška stromu je tedy vzdálenost kořene od listů, které jsou ve stromu 
nejníže. Zřejmě čím má strom při daném počtu uzlů menší výšku, tím je to výhodnější, neboť 
tím nižší je maximální délka cesty od kořene k uzlům stromu. Na následujícím obrázku jsou tři 
binární stromy. Všechny mají stejný počet uzlů – šest.