11-Trideni_halda_stromy

BPC-ALD

11. přednáška

Stromy - základní informace, třídění s využitím haldy

rev. 2019.3

Ing. T. Macho, Ph.D. (macho@feec.vutbr.cz)

Stromy

Datová struktura strom

• Nelineární datová struktura.
• Specifický případ matematických grafů (tzv. acyklický graf).
• Stromy jsou tvořeny uzly a hranami.

• V uzlech jsou uloženy datové prvky nad kterými algoritmus probíhá.
• Hrany reprezentují vztahy mezi prvky uloženými v uzlech.

Uzel

Hrana

Datová struktura strom

u

Kořen

Uzel u

Listy

Následníci uzlu u

Předchůdce uzlu u

Datová struktura strom

• Kořen

• Uzel na vrcholu stromu.
• Jediný uzel, který nemá žádného předchůdce.

• Listy

• Uzly, které nemají žádného následníka

• Každý uzel, kromě kořenového, má právě jednoho předchůdce.
• Uzel může mít následníky

• Počet následníků je obvykle omezen.

Výška stromu

• Přechod po hraně od předchůdce k následovníkovi považujeme za 

jednu operaci.

• Počet operací, které musíme provést, abychom se dostali od kořene k 

danému uzlu je roven počtu hran, které jsou na cestě od kořene k 
danému uzlu a nazývá se vzdálenost uzlu od kořene.

• Výška stromu je maximum ze vzdáleností všech uzlů od kořene 

stromu.

• Vzdálenost kořene od listů, které jsou ve stromu nejníže.

Binární strom
• Každý uzel může mít maximálně dva následníky.
• Nejjednodušší, ale nejčastěji používaný typ stromu.

u

Kořen

Uzel u

Listy

Levý a pravý 
následník uzlu u

Předchůdce uzlu u

Vrstva 0

Vrstva 1

Vrstva 2

Vrstva 3

Vyvážený binární strom

• Má ve všech vrstvách maximální možný počet uzlů vyjma poslední 

vrstvy, která může být zaplněna jen zčásti.

• Má nejmenší výšku při daném počtu uzlů.
• Má nejmenší průměrnou vzdálenost uzlů od kořene.

Počty uzlů v jednotlivých vrstvách binárního 
vyváženého stromu

Číslo 

vrstvy

Počet uzlů ve vrstvě

0

1

1

21

2

22

3

23

…

ℎ − 1

2ℎ−1

ℎ

1 … 2ℎ

Vztah mezi počtem uzlů a výškou binárního 
vyváženého stromu
• Je-li poslední vrstva plně zaplněna uzly, je celkový počet uzlů stromu: