|
V binárním stromu < jsou ke každému vrcholu připojeny dva podstromy (jeden nebo oba mohou být prázdné). Jeden z nich označíme jako levý a druhý jako pravý podstrom. Nejčastěji se setkáme
s binárními stromy, ve kterých jsou data uspořádána podle následujícího
pravidla: Pro každý vrchol U platí, že všechny údaje, uložené v levém podstromu, připojeném
k U, jsou menší, než je údaj uložený
v U, a všechny údaje, uložené v
pravém podstromu, připojeném k U,
jsou větší, než je údaj uložený v U.
Binární strom označíme za dokonale vyvážený, jestliže pro jeho libovolný vrchol v platí , že počet vrcholů v levém a pravém podstromu vrcholu v se liší nejvýše o 1. Není obtížné
sestrojit statický dokonale vyvážený strom, tedy strom, u něhož předem známe
počet vrcholů a ten se nebude měnit. Jde o úlohu podobnou konstrukci optimálního
vyhledávacího stromu. Značné problémy ovšem
nastanou, jestliže se bude strom v průběhu své existence měnit, tj. jestliže
do něj budeme chtít přidávat vrcholy nebo je rušit. Proto se obvykle používají
slabší definice vyváženosti. Jednu z nich navrhli Adelson-Velskij a Landis a
stromy, vyvážené podle jejich definice, se (podle nich) označují jako AVL-stromy
nebo jako AVL-vyvážené
stromy
. Protože
žádnou jinou definici vyváženosti nebudeme používat, budeme o nich hovořit
prostě jako o vyvážených stromech
. Tedy: Strom
je vyvážený, právě když se výšky obou podstromů, připojených k jeho
libovolnému vrcholu, liší nejvýše o 1. Autoři AVL-stromů dokázali,
že výška AVL-stromu nikdy nepřesáhne 1,45-násobek výšky dokonale vyváženého
stromu, složeného ze stejných vrcholů. To znamená, že obvyklé operace,
jako je přidání vrcholu do stromu, vyhledání nebo zrušení vrcholu lze
provést v čase O(log2n),
kde n je počet vrcholů. Vyhledávání ve vyváženém
stromu se neliší od vyhledávání v "obyčejném" binárním
stromu. Při přidávání nebo rušení vrcholů se ovšem z vyváženého
stromu může stát strom nevyvážený. Podíváme se, jak se napravuje rovnováha,
porušená při přidávání vrcholů; postup při obnovení rovnováhy po zrušení
vrcholu bude podobný.
Přidávání vrcholů do vyváženého
stromu
Máme tedy strom, který byl vyvážený, a do kterého jsme přidali jeden vrchol. Pro určitost předpokládejme, že jsme jej přidali levého podstromu. Jestliže si označíme K kořen, L resp. P levý resp. pravý podstrom a vL resp. vP jejich výšky, bude před přidáním vrcholu platit jedna z následujících tří možností: 1. vL = vP. Po přidání bude vL o jedničku větší než vP, nicméně strom zůstane
vyvážený. 2. vL
< vP. Po přidání bude vL = vP,
strom zůstal vyvážený. 3. vL
> vP. Po přidání bude vL = vP
+ 2, takže strom již není vyvářený
- je třeba zjednat nápravu. Při vyvažování musíme zachovat relativní pořadí vrcholů ve stromu, neboť to odpovídá pořadí klíčů. To znamená, že jediné přípustné zásahy budou rotace vrcholů, při kterých např. vrchol L nahradí K, kořen K přejde do pravého podstromu apod. Příklad 2.1
V tomto příkladu si ukážeme
všechny situace, které mohou nastat. Uvažujme prázdný AVL-strom, do kterého
budeme postupně přidávat vrcholy s hodnotami 4, 5, 7, 2, 1, 3, 6. Po přidání vrcholu 7
vznikne poprvé nevyvážený strom, který vidíte na obr. 6.4
vlevo. Nápravy dosáhneme jednoduchou rotací vpravo, kterou označíme PP
(prodloužil se pravý podstrom pravého podstromu).
Obr.
1.
1
Jednoduchá rotace PP Po přidání vrcholu 2 zůstane
strom vyvážený.
Po přidání vrcholu 1 se rovnováha opět poruší (obr.
1.4),
takže musíme použít jednoduchou rotaci doleva (LL, neboť se prodloužil se levý podstrom levého podstromu).
Obr.
1.
2
Jednoduchá rotace LL Po přidání vrcholu 3
poruší vyváženost kořene, tj. vrcholu 5. K nápravě nyní použijeme
dvojitou rotaci, kterou označíme LP (vyrostl levý podstrom pravého podstromu, obr. 1.4). Nejprve upravíme levý podstrom
s kořenem 2 tak, aby se jeho kořenem stal vrchol 4. Pak posuneme kořen
celého stromu - tím se stane 4.
Obr.
1.
3
Dvojitá rotace LP Poslední přidaná hodnota je 6. Tentokrát se objeví nerovnováha v levém
podstromu pravého podstromu, takže použijeme rotaci PL. Postup je zrcadlovým obrazem rotace LP (obr. 1.4).
Obr.
1.4
Dvojitá
rotace PL Při práci s vyváženým stromem budeme potřebovat údaje o tom, o kolik se liší výška levého a pravého podstromu. Proto přidáme do každého záznamu položku vyváženost, která bude obsahovat rozdíl výšky pravého a levého podstromu (v tomto pořadí). Ve složce počet budeme ukládat počet výskytů prvku s daným klíčem. type
uVrchol = ^vrchol; vrchol
= record klíč:
integer; počet:integer; levý,
pravý: uVrchol; vyváženost:
-1..1; end; Při vkládání budeme potřebovat informaci o tom, zda se výška podstromu změnila. K tomu použijeme pomocný parametr h typu boolean, který budeme předávat hodnotou. Jestliže přidáme prvek do levého podstromu kořene K a výška tohoto podstromu se zvětší, bude potřebné strom znovu vyvážit, jestliže bude vyváženost = -1. Jestliže jsme přidávali do pravého podstromu a jeho výška se zvětšila, bude potřebné strom znovu vyvážit, bude-li vyváženost = 1. Podle hodnoty vyváženost
v kořeni podstromu pak určíme, kterou z rotací použijeme. V následující
proceduře vlož jsou rotace vyjádřeny
jako vnořené procedury LL, LR atd. procedure
vlož(x: integer; var p: uVrchol; var v: boolean); var p1, p2: uVrchol; {na počátku musí být v = false} procedure
LL; {levý podstrom levého podstromu} begin p^.levý
:= p1^.pravý; p1^.pravý
:= p; p^.vyváženost
:= 0; p := p1; end; {LL} procedure
RR; {pravý podstrom pravého podstromu} begin
p^.pravý
:= p1^.levý; p1^.levý
:= p; p^.vyváženost
:= 0; p := p1; end; {RR} procedure
LR; {levý podstrom pravého podstromu} begin
p2 :=
p1^.pravý; p1^.pravý
:= p2^.levý; p2^.levý
:= p1; p^.levý
:= p2^.pravý; p2^.pravý
:= p; if p2^.vyváženost
= -1 then p^.vyváženost := 1
else p^.vyváženost := 0; if p2^.vyváženost
= +1 then p1^.vyváženost := -1
else p1^.vyváženost := 0; p := p2; end; { } procedure
RL; {pravý podstrom levého podstromu} begin
p2 :=
p1^.levý; p1^.levý
:= p2^.pravý; p2^.pravý
:= p1; p^.pravý
:= p2^.levý; p2^.levý
:= p; if p2^.vyváženost
= +1 then p^.vyváženost := -1
else p^.vyváženost := 0; if p2^.vyváženost
= -1 then p1^.vyváženost := +1
else p1^.vyváženost := 0; p := p2; end; {RL} begin
{vlož} if p=nil
then begin
{klíč není ve stromu, přidá se} new(p); v
:= true; with
p^ do begin klíč
:= x; počet
:= 1; levý
:= nil; pravý
:= nil; vyváženost
:= 0; end end else if x
< p^.klíč then begin vlož(x,
p^.levý,v); if
v then {zvětšil se levý podstrom} case
p^.vyváženost of 1:
begin
dec(p^.vyváženost);
v := false;
end; 0:
dec(p^.vyváženost); -1:
begin {vyvažování}
p1 := p^.levý;
if p1^.vyváženost = -1 then LL else LR;
p^.vyváženost := 0;
v := false;
end; end
{case} end
else if
x > p^.klíč then begin vlož(x,
p^.pravý,v); if
v then
{zvětšil se pravý podstrom} case
p^.vyváženost of -1:
begin
inc(p^.vyváženost);
v := false;
end; 0:
inc(p^.vyváženost); 1:
begin
{vyvažování}
p1 := p^.pravý;
if p1^.vyváženost = +1 then RR else RL;
p^.vyváženost := 0;
v := false;
end; end
{case} end
else begin inc(p^.počet); v
:= false; end end;{vlož} Je zřejmé, že operace s vyváženým stromem jsou podstatně složitější než operace s "obyčejným" stromem. Proto se tyto stromy vyplatí budovat zejména tehdy, když vyhledávání převažuje nad přidáváním nebo rušením vrcholů. Také v případě, že se používá zhuštěného ukládání záznamů, přestávají být vyvážené stromy výhodné - operace přístupu ke zhuštěným záznamům mohou být velmi neefektivní. |
|