Strom

 

 

 

 

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).

 

Vyvažování binárního stromu

 
 

[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).

 

Zpět na hlavní stránku


Poslední aktualizace: 28-05-2003.