BPC-ALD - Skripta_rev2019_2
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Nejběžnější
jsou binární
stromy.
− 18 −
Levý strom je nejméně výhodný. V podstatě je to seznam a o seznamu víme, že časová složitost
přístupu k jeho uzlům je lineární. Naproti tomu strom zcela vpravo má tu vlastnost, že má při
daném počtu uzlů nejmenší možnou výšku. Je to vyvážený binární strom.
Vyvážený binární strom je takový binární strom, který 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. Vrstvou přitom tady
rozumíme všechny uzly, které mají stejnou vzdálenost od kořene, tedy mají stejnou
vodorovnou úroveň při běžném nakreslení stromu shora-dolů. Tuto vzdálenost nazveme číslem
vrstvy. Podíváme-li se na následující příklad vyváženého binárního stromu
můžeme z něho odvodit, jaké počty uzlů budou obecně v jednotlivých vrstvách vyváženého
binárního stromu výšky h.
Číslo vrstvy
Počet uzlů v ní
0
1
1
2
2
22
…
…
h-1
2h-1
h
1 .. 2h
Odtud pro počet uzlů n v celém stromu dostáváme vztah
Výška stromu je
důležitá pro
efektivnost
algoritmů.
− 19 −
h
h
h
n
2
2
...
2
2
1
1
2
...
2
2
1
1
2
1
2
+
+
+
+
+
≤
≤
+
+
+
+
+
−
−
Jeho postupnými úpravami (použitím součtu geometrické řady)
1
2
2
1
−
≤
≤
+
h
h
n
n
n
h
≤
≤
+
2
2
1
)
(
log
2
1
log
2
2
n
h
n
≤
≤
⎟
⎠
⎞
⎜
⎝
⎛ +
)
(
log
1
)
1
(
log
2
2
n
h
n
≤
≤
−
+
Z tohoto plyne důležitý závěr, že ve vyváženém binárním stromu výška stromu logaritmicky
závisí na počtu uzlů v něm, což můžeme vyjádřit jako složitost
Θ(log(n)).
Průvodce studiem
Jak uvidíme dále, stromy jsou základem velmi efektivních algoritmů zejména pro