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:
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 :
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;
Procedure VyberHodnotu (var S : TStrom,var P : TP);
Begin
if S = nil then write(' Vrchol S neexistuje ')
else P := S^.Hodnota
end;
Function VyberLevy (var S : TStrom) : Tstrom;
Begin
if S = nil then write(' Vrchol S neexistuje ')
else VyberLevy := S^.Levy
end;
Function VyberPravy (var S : TStrom) : Tstrom;
Begin
if S = nil then write(' Vrchol S neexistuje ')
else VyberLevy := S^.Pravy
end;
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;
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á.
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;
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.