Vyvážený binární strom

 

 

 

 

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, kte­rou 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 pra­vé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ásle­dují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; {LR}

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

Zpět

 


Poslední aktualizace: 29-05-2003.