|
Strom je další z běžně používaných rekurzivních datových struktur. Abstraktní definice stromu se základním typem T je rekurzivní a vypadá takto: Strom
se základním typem T je buď prázdná struktura nebo prvek typu T, na který je připojen konečný počet disjunktních stromových
struktur se základním typem T (označujeme
je jako podstromy). Prvky stromu se obvykle
označují jako vrcholy
nebo uzly
. Vrchol, ke kterému není připojen žádný
podstrom, označujeme jako koncový vrchol
nebo list
. Vrchol, který sám není připojen k žádnému
jinému vrcholu, označujeme jako kořen
. To znamená, že kořen spolu se všemi
podstromy, které jsou k němu připojeny, tvoří celý strom. Prvky, které
nejsou listy, označujeme jako vnitřní
vrcholy
stromu. Je-li G
kořen podstromu, připojeného k uzlu C (viz
obr. 1.1),
říkáme také, že G je (přímým)
následovníkem
C
a C je (přímým) předchůdcem
G.
Kořen je vrchol, který nemá předchůdce; list je vrchol, který nemá žádného
následovníka. Přidáme k definici
stromu požadavek, aby počet podstromů, připojený k libovolnému z vrcholů
daného stromu, nepřesáhl n. Takový
strom
označujeme jako n-ární. Nejčastěji se setkáme s binárními stromy (n = 2) nebo
ternárními stromy (n = 3). Číslo n
("-aritu") budeme označovat jako typ
stromu
. Příklad 1.1
Na obrázku 1.1
vidíte příklad ternárního stromu s vrcholy označenými A, ... , O.[1] Vrchol A je
kořen tohoto stromu, vrcholy J, K, L, F,
M, N, O, H a I
jsou listy. Strom jsme znázornili
jako graf, jehož uzly odpovídají vrcholům stromu a hrany odpovídají odkazům
na připojené podstromy. Jeden takový podstrom, připojený k uzlu C,
se skládá z uzlů G, M, N, O. Všimněte si, že v tomto
grafu jsme znázornili i odkaz na kořen stromu (jako hranu vedoucí do A).
Obr.
1.1 Příklad ternárního
stromu Následující pojmy využijeme
při úvahách o složitosti algoritmů, které využívají stromů: O kořeni stromu říkáme,
že je na první úrovni
. Uzly, které jsou následovníky kořene,
jsou na druhé úrovni. Obecně je-li uzel S
na úrovni i a uzel Š je následovníkem S,
je Š
na úrovni i+1. Je-li x
úroveň vrcholu X, znamená to, že chceme-li projít stromem od kořene k X,
musíme projít x hran (včetně hrany, která vstupuje do kořene). Proto se místo
o úrovni vrcholu často hovoří o délce
vnitřní cesty
daného
vrcholu. Součet délek cest všech
uzlů v daném stromě se nazývá délka
vnitřní cesty stromu. Průměrná délka vnitřní cesty stromu je pak
definována vztahem
, kde ni je počet uzlů na i-té úrovni stromu. Kromě délky vnitřní
cesty zavádíme také délku vnější
cesty stromu.
Než ji ale definujeme, musíme zavést zvláštní
vrcholy
stromu
(na obr. 1.2
jsou znázorněny pomocí čtverečků). V n-árním
stromu doplníme počet následovníků každého "obyčejného"
vrcholu zvláštními vrcholy na hodnotu n.
Zvláštní vrcholy nebudou mít žádné následovníky. Délku vnější cesty
stromu definujeme jako součet délek cest všech
zvláštních vrcholů. Průměrná délka vnější cesty stromu je
kde mi je počet zvláštních vrcholů na i-té úrovni stromu a m je celkový počet zvláštních vrcholů.
Obr.
1.2
Strom z obr.
1.
1 s přidanými zvláštními vrcholy Počet m zvláštních vrcholů, které musíme do stromu přidat, závisí
na typu stromu, vyjádřeném číslem d,
a na počtu "původních" vrcholů n.
Protože do každého vrcholu rozšířeného stromu vstupuje právě jedna
hrana, je v něm celkem m + n hran.
Protože z každého původního vrcholu vystupuje vždy d
hran, zatímco ze speciálních vrcholů žádné hrany nevystupují, obsahuje
strom celkem dn hran, vystupujících
z vrcholů, a navíc jednu hranu, která vstupuje do kořene (ta nevychází ze
žádného z vrcholů). Z těchto úvah dostaneme pro číslo m rovnici
, tj.
Maximální počet vrcholů ve stromu typu d s k úrovněmi je roven součtu
neboť na první úrovni je nejvýše jeden vrchol, který má nejvýše d následovníků na 2. úrovni, z nichž každý má opět nejvýše d následovníků na 3. úrovni atd. Speciálně
binární strom s k úrovněmi má nejvýše
uzlů. Stromy nejčastěji
reprezentujeme jako dynamické datové struktury. Vrcholy stromu typu d
mohou být záznamy, které obsahují ukazatele na kořeny připojených
podstromů (nebo nil, není-li podstrom připojen ): type
uVrchol = ^vrchol; vrchol
= record Dt:
data; Další:
array [1..d] of uVrchol; end; Užitečné informace jsou uloženy ve složce Dt, která je typu data (podobně jako v případě seznamů). Poznamenejme, že na jednosměrný seznam se můžeme dívat jako na unární strom (strom typu 1).
[1]Stromy se zpravidla zobrazují s kořenem jako nejvyšším vrcholem a s
listy dole. Pokud vám to připadá nelogické, máte jistì pravdu -
stromy obvykle rostou obrácenì. Můžete s tím nesouhlasit, ale to
je asi tak vše, co s tím můžete dělat (J. Cimrman).
|
|