Uzly jsou navzájem spojeny „hranami“. Neexistuje osamocený uzel, ke kterému by nevedla žádná hrana (s výjimkou stromu s pouze jedním uzlem). Pokud jsou hrany orientované, nazývají se uzly připojené k jednomu uzlu jako „potomci uzlu“, nadřazený uzel je potom „rodičovský uzel“. Uzel může mít pouze jednoho rodiče, ale více potomků. Počet všech potomků nějakého uzlu se nazývá „stupeň uzlu“.
Základní prvky stromu
Strom v informatice
Kořen stromu
Nejvyšší uzel ve stromu se nazývá „kořen stromu“ (anglicky „root“)
Kořen stromu je jediným uzlem ve stromu bez rodiče
V každém stromu se nachází maximálně jeden kořen, takový strom nazýváme „zakořeněný strom“
Vnitřní uzly
Uzel, který není koncovým uzlem se nazývá „vnitřní uzel“ (anglicky „internal node“ nebo „inner node“). Někteří autoři z množiny vnitřních uzlů explicitně vypouští kořen.
Koncové uzly
„Koncový uzel“, někdy také „list“ (anglicky „leaf“ nebo „leaf node“), je takový prvek, který nemá žádného potomka. Má-li strom jen jeden uzel, je tento uzel kořenem i listem zároveň.
Podstrom S
Maximální počet potomků
Konkrétní typy stromů většinou mají definován maximální počet potomků ve svých vnitřních uzlech. Například:
pro případ extrémně nevyrovnaného stromu (který se blíží lineárnímu seznamu) je to 1
Do uzlu s již maximálním počtem poduzlů nelze další uzel přidat a místo toho je potřeba jej nějakým způsobem přeuspořádat.
Podstrom
„Podstrom“ (anglicky „subtree“) je část stromové datové struktury tvořené jedním uzlem („kořenem podstromu“) a všemi jeho potomky. Může být chápán jako kompletní strom sám o sobě. Každý uzel ve stromu může tvořit kořen podstromu.
Hloubka, výška, šířka, úroveň a cesta
Strom má výšku 4. Uzel X leží na 3. úrovni a má hloubku 2.
„Cesta“ k nějakému uzlu je definována jako posloupnost všech uzlů od kořene k uzlu.
„Délka cesty“ je rovna počtu hran, které cesta obsahuje, tedy počtu uzlů posloupnosti – 1.
„Hloubka uzlu“ je definována jako délka cesty od kořene k uzlu.
Prvky se stejnou hloubkou jsou na „téže úrovni“.
„Výška stromu“ je rovna hodnotě maximální hloubky uzlu, se označuje též za „hloubku stromu“.
„Šířkou stromu“ je počet uzlů na stejné úrovni.
Strom má „nejmenší výšku“ právě tehdy, když na všech úrovních (s možnou výjimkou té poslední) má tato struktura plný počet uzlů. Úroveň všech listů je stejná nebo se liší maximálně o 1.
Při sestavování stromové struktury je důležité sestavovat stromy s nejmenší možnou výškou, protože tím se zajistí optimální rychlost práce se strukturou.
„Vyvážený strom“ je takový strom, který má uzly rovnoměrně rozložené, tedy má nejmenší výšku. Ideální situace je taková, kdy má strom v každé hladině, kromě poslední, maximální počet uzlů, a v poslední hladině má uzly co nejvíce vlevo.
Stromové uspořádání
Uspořádaný binární strom
Stromy se dělí na dva základní typy:
Uspořádaný (anglicky „ordered tree“)
Neuspořádaný (anglicky „unordered tree“)
„Uspořádaný“ nebo také „seřazený strom“ je takový strom, ve kterém jsou všichni přímí potomci každého uzlu seřazeni. Tudíž, pokud uzel má n dětí, lze určit prvního přímého potomka, druhého přímého potomka, až n-tého přímého potomka.
U „neuspořádaného stromu“ se jedná o strom v čistě strukturálním smyslu. To znamená, že pro daný uzel nejsou uspořádáni potomci.
Metody procházení stromu
Procházení stromem do šířky
Procházením „stromu do šířky“ (anglicky „level-order“) se rozumí procházení stromem po vrstvách úrovní (tzn. po hladinách). Viz prohledávání do šířky.
Procházení stromem do hloubky
Procházení začíná v kořeni stromu a postupuje se vždy na potomky daného vrcholu. Procházení končí, když v žádné větvi (tj. v žádném podstromu) již není následník. Viz prohledávání do hloubky.
Podle pořadí, ve kterém se prochází uzly uspořádaného stromu, se rozlišují tři základní metody:
PREORDER
proveď akci
projdi levý podstrom
projdi pravý podstrom
INORDER
projdi levý podstrom
proveď akci
projdi pravý podstrom
POSTORDER
projdi levý podstrom
projdi pravý podstrom
proveď akci
Při použití metody INORDER se prochází uzly v uspořádaném stromě podle jejich přirozeného pořadí.
Procházení do šířky (po vrstvách) Level-order: F, B, G, A, D, I, C, E, H
Reprezentace stromu
Binární strom jako pole – vztahy uzlu na potomky jsou určeny funkcemi 2i+1 a 2i+2
Je mnoho způsobů jak reprezentovat stromy. Běžné reprezentace reprezentují uzly jako záznamy na haldě s ukazatelem na dítě nebo na rodiče nebo na oba. Případně se reprezentují jako pole prvků se vztahy mezi sebou (pomocí algoritmů), které určují jejich pozici v poli.
Nahlížet na hierarchii můžeme mnoha způsoby. Jedním z nich je „hnízděná množina“, kterou si lze představit jako vnořené množiny. Další velmi podobný způsob je „hraniční“ reprezentace.
Reprezentace stromu jako hnízděné množiny
Reprezentace stromu hraničním zobrazením
Strom jako graf
V teorii grafů odpovídá hierarchická struktura stromu acyklickému grafu s jedním kořenem, jež bývá často nazýván jako „orientovaný acyklický graf“ a ve kterém každý vrchol má „vstupní hranu“. Acyklický graf, který není propojen, se někdy nazývá les, protože se skládá z více stromů.
Reprezentace stromu v relační databázi
Pro reprezentaci struktury v relační databázi se používá zpravidla jedna tabulka, ve které si ukládáme identifikaci rodičovského uzlu a identifikátor uzlu. Je-li potřeba vytvořit strom s více rodiči pro jeden uzel, tabulka se rozdělí na dvě. Jedna tabulka bude obsahovat seznam uzlů a ve druhé budou zaznamenány vazeb mezi uzly (tzv. vztah uzlů M:N). V případě binárního stromu se používá tabulka se třemi sloupci kde je zaznamenána hodnota, levý a pravý ukazatel na dítě.
Id_uzlu
Id_rodiče
A
B
B
F
C
D
D
B
E
D
F
–
G
F
H
I
I
G
Operace na stromech
Počet všech prvků
Hledání prvků
Přidání nového prvku na určitou pozici ve stromu
Smazání prvku
Vyjmutí celé části stromu – prořezávání (anglicky „pruning“)
Přidání celé části do stromu – roubování (anglicky „grafting“)
Hledání kořene pro každý uzel
Výška (hloubka) stromu
Využití
Stromy, a zejména jejich některé konkrétní vyhledávací varianty, nacházejí široké uplatnění v oblastech, kde je třeba řešit ukládání a vyhledávání dat, zejména tam, kde je kritickou omezující podmínkou vyhledání dat s co nejmenší úrovní složitostí a při co nejméně přístupy čtení.
.jpg)
