Nelineární datové struktury
Binární strom
 Tisk

Binární strom


Má-li každý vrchol nejvýše dva potomky, nazývá se takový strom Binární. Každý vrchol binárního stromu má tedy levého, případně pravého následníka (potomka).


Uspořádaný binární strom je takový, jehož leví následníci každého vrcholu mají ohodnocení nižší než sám vrchol, praví následníci mají ohodnocení vyšší.


Takové stromy jsou velice důležitým pojmem a často se využívají pro implementaci nejrůznějších rozhodovacích procesů.


Každý vrchol stromu je reprezentován trojicí:



Poznámky:


  1. Hodnotou může být i složitě strukturovaný objekt, např. záznam.
  2. Celý strom je reprezentován ukazatelem na kořen.
  3. Nejvýhodnější implementace binárního uspořádaného stromu je pomocí dynamického spojového seznamu.


Type

    TP     = ...;     { Typ hodnot, jimiž jsou ohodnoceny vrcholy }

    TStrom = ^Vrchol; { Strom je reprezentován odkazem na vrchol }

    Vrchol = record { Každý vrchol je kořenem z něj vzcházející části stromu }

                 Hodnota : TP;     { Ohodnocení vrcholu }

                 Levy    : TStrom; { Ukazatel na levého potomka }

                 Pravy   : TStrom; { Ukazatel na pravého potomka }

                 Rodic   : TStrom; { Ukazatel na rodiče }

             end;

{ Vytvoření nového vrcholu s ohodnocením P }

Function NovyVrchol (P : TP) : TStrom;

{ Funkce vrací ukazatel na nově vytvořený vrchol }

Var

    Pom : TStrom;

Begin

    New(Pom);     { Dynamické přidělení paměti pro nový vrchol }

    With Pom^ do begin

        Hodnota := P;   { Ohodnocení vrcholu }

        Levy    := nil; { Vrchol zatím nemá potomky; chová se jako list }

        Pravy   := nil;

    end;

    NovyVrchol := Pom

end;


Pro práci se stromem definujeme množinu dalších procedur :


Nastavení ukazatele Levy vrcholu S na vrchol SL.


Procedure SpojLevy (var S,SL : TStrom);

Begin

    if S = nil then write(' Vrchol S neexistuje ')

    else S^.Levy := SL

end;


Nastaveni ukazatele Pravy vrcholu S na vrchol SP.


Procedure SpojPravy (var S,SP : TStrom);

Begin

    if S = nil then write(' Vrchol S neexistuje ')

    else S^.Pravy := SL

end;


Zpřístupnění hodnoty vrcholu.


Procedure VyberHodnotu (var S : TStrom,var P : TP);

Begin

    if S = nil then write(' Vrchol S neexistuje ')

    else P := S^.Hodnota

end;


Vybrání ukazatele na levého potomka.


Function VyberLevy (var S : TStrom) : Tstrom;

Begin

    if S = nil then write(' Vrchol S neexistuje ')

    else VyberLevy := S^.Levy

end;


Vybrání ukazatele na pravého potomka.


Function VyberPravy (var S : TStrom) : Tstrom;

Begin

    if S = nil then write(' Vrchol S neexistuje ')

    else VyberLevy := S^.Pravy

end;


Vytvoření uspořádaného binárního stromu.


Procedure Vytvorstrom (var S : TStrom);

{ Vstupní posloupnost ohodnocení vrcholů je 6,12,4,9,2 }

Var

    X,Y     : TP;

    Rodic,Act,Pom : TStrom;

Begin

    Read(X);     { Přečte ohodnocení vrcholu }

    S := NovyVrchol; {Vytvoření vrcholu (X,nil,nil)}

    While not Eof do begin

        Read(X);     { Přečte ohodnocení dalšího vrcholu }

        Act := S; { Hledání vhodného místa v aktuálním stromu S}

        While not (Act = nil) do begin

            Rodic := Act;

            VyberHodnotu(Act,Y); { Hodnotu uzlu uloží do Y }

            If (X < Y)     { Rozhodnutí, má-li se pokračovat }

            then     { v prohledávání levým nebo pravým }

                Act := VyberLevy(Act)     { podstromem }

            else

                Act := VyberPravy(Act)

        end;

        VyberHodnotu (Rodic,Y); { Po nalezení uzlu bez následníků }

        If (X < Y)     { (listu) se rozhodne zapojí-li se}

        then     { nový uzel jako levý nebo pravý }

            SpojLevy(Rodic,Pom) { následník     }

        else

            SpojPravy(Rodic,Pom)

    end

end;


Vznikne následující strom .

Každým stromem se dá procházet při jeho prohledávání řadou způsobů. Bude-li se postupovat u zkoumaného binárního uspořádaného stromu tak, že nejprve projdeme levou část stromu, pak vypíšeme ohodnocení vrcholu a pak projdeme pravou část stromu, dostaneme seřazenou (setříděnou) posloupnost hodnot uzlů stromu. Při procházení stromu se s výhodou používá rekurzivní volání procedury, ale buďme opatrní, při rozsáhlé struktuře stromu bychom se mohli dostat do potíží s operační pamětí nebo s velikostí zásobníkové paměti, kterou náš výpočetní systém používá.


Procedura procházení:


Procedure Prochazej(var S : TStrom);

Var

    P : TP;

    Pom : TStrom;

Begin

    If not ( S = nil ) then begin

        Pom := VyberLevy(S); { Nejdříve se prochází levá větev }

        Prochazej(Pom)       { Každý uzel je nový strom, proto rekurse }

        VyberHodnotu(S,P);   { Po projití větve až na konec (nil)}

        Writeln(P);          { se vybere hodnota uzlu a vypíše se}

        Pom := VyberPravy(S);{ Potom se pokračuje pravou větví}

        Prochazej(Pom)

    end

end;


Pro seřazení ukázané posloupnosti čísel :


Procedure Serad;

Var

    S : TStrom;

Begin

    VytvorStrom(S);

    Prochazej(S)

end;


Binárních stromů se často používá pro ukládání, vyhledávání a třídění informací. Aby byl proces efektivní, nestačí, aby binární strom byl uspořádaný, ale aby byl tzv. vyvážený, tj. aby počet úrovní jeho uzlů byl minimální. Náš strom je vyvážený, ale kdybychom jinak uspořádali vstupní hodnoty, mohla by vzniknout v krajním případě situace, kdy prohledávání takového stromu je vlastně sekvenční. Jde o degenerovaný binární strom .


Výška ideálně vyváženého stromu je menší než log2 n. V nejhorším případě může být výška degenerovaného stromu až n, kde n je počet vrcholů.


Doba vyhledání informace ve vyváženém stromu je


     T ≈ log2 n


Vyvažování binárních (i jiných) stromů tvoří samostatnou problematiku a o této algoritmizaci je možno se dočíst v literatuře.