AVL-stromy     
 
 
 

Zpracováno dle [1], [2] a [3] jako referát na cvičení z předmětu Datové struktury.

 
 
Obsah
 
 
Úvod
 

Používáním operací INSERT a DELETE na binárním vyhledávacím stromě může docházet k jeho postupné degeneraci, což podstatně snižuje efektivitu prováděných operací. Z ideální časové složitosti vyhledávání O( log( n) se tak může deklasovat až ke složitosti lineární O( n).

 

Aby k takovéto degeneraci nedocházelo, definuji se pro binární vyhledávací stromy tzv. podmínky vyváženosti (balance conditions), které by měly zaručit rozumnou logaritmickou výšku stromu a rychlost operací.

 

Ukázalo se, že přímá podmínka vyváženosti (levý a pravý podstrom musí mít stejnou výšku) je příliš omezující pro efektivní implementaci. V roce 1962 zavedli Adelson-Velskij a Landis volnější podmínkou vyváženosti: rozdíl výšek levého a pravého podstromu může být maximálně jedna. Podle jmen autorů se takto vyvážený binární strom nazývá AVL-strom.

 

Definice: ALV-strom je binární vyhledávací strom takový, že pro každý jeho vrchol v platí:

  1. buď v je koncový,
  2. nebo v má jediného následníka, kterým je koncový vrchol,
  3. nebo v má dva následníky s výškami hl a hr, které vyhovují podmínce vyváženosti |hl - hr| < 2.
 

Věta: ALV-strom s n prvky má výšku nejvýše 2.log2 n  

Důkaz: (mírně pozměněná verze z [1])

 

Označme N( h) minimální počet vrcholů AVL-stromu o výšce h, N( 0)=1, N( 1)=2. Pro výšku větší než 1 má kořen stromu dva následníky, z nichž jeden má výšku h-1 a druhý h-1 nebo h-2. Celý strom má tedy alespoň 1 +N( h-1) +N( h-2) >= 2N( h-2) (neboť N( h-2) <= N( h-1)). To tedy znamená, že se zvýšením výšky o 2 se minimální počet vrcholů v AVL-stromě zdvojnásobí, a tedy N( h) >= 2h/2. Z toho plyne h <= 2.log2 N( h). CBD

 

Poznámka (dle [2]): přesnějším výpočtem lze odhad zlepšit na 1,44.log2( n+2) -0,328. Při praktickém použití se výška stromu pohybuje kolem log2( n+1) +0,25.

 
 
Vyvažování po přidání prvku
 

Ještě dříve než popíšeme samotné operace INSERT a DELETE se podíváme podrobněji na problémy vyvážení, které mohou nastat při přidání prvku do stromu použitím klasické operace INSERT.

 

Definice: b( v) označíme rozdíl mezi výškou levého podstromu vrcholu v a výškou pravého podstromu vrcholu v. Ve shodě s definicí AVL-stromu nazveme vrchol v vyvážený, pokud b( v) je -1, 0 nebo 1. Není-li vrchol vyvážený, budeme ho nazývat nevyváženým.

 

Při přidání prvku do binárního stromu se může hodnota b( v) pro každý vrchol změnit o 1 nebo zůstat beze změny. Nás tedy bude především zajímat situace, kdy se hodnota b( v) změní z 1 na 2 nebo z -1 na -2 (tj. vyvážený vrchol se stává nevyváženým).

 

LL a RR rotace

 

Předpokládejme, že stromy T1, T2 a T3 měly před operací INSERT stejnou výšku.

 
Rotace LL
 

Na tomto obrázku se po přidání nového prvku zvětšila výška stromu T1 o 1 a tím se porušila vyváženost vrcholu v1. Jeho vyvážení provedeme změnou tvaru stromu - za pravého následníka vrcholu v2 označíme vrchol v1 a za levého následníka vrcholu v1 označíme kořen stromu T2.

 

Tato úprava se nazývá LL rotací (dle polohy stromu, který nevyváženost způsobil - levý následník svým levým podstromem). Nevyváženost zrcadlově symetrická se opravuje obdobně a nazývá se RR rotací.

 

LR a RL rotace

 

Opět předpokládejme, že stromy T1, T2 a T3 měly před operací INSERT stejnou výšku.

 
Rotace LR
 

Na tomto obrázku se po přidání nového prvku zvětšila výška stromu T2 o 1 a tím se porušila vyváženost vrcholu v1. Jeho vyvážení opět provedeme změnou tvaru stromu - za pravého následníka vrcholu v2 označíme levého následníka vrcholu v3, za levého následníka vrcholu v1 označíme pravého následníka vrcholu v3, pro v3 pak označíme levého následníka jako v2 a pravého následníka jako v1.

 

Tato úprava se nazývá LR rotací (nevyváženost způsobil levý následník svým pravým podstromem). Nevyváženost zrcadlově symetrická se opravuje obdobně a nazývá se RL rotací.

 

Je snadné nahlédnout, že po vyvážení

  1. v1 a všechny jeho následníci jsou vyvážení,
  2. výška stromu určeného vrcholem v1 zůstane stejná jako byla před vložením nového prvku,
  3. všichni předchůdci v1 jsou vyvážení (plyne z předchozího bodu)

Stačí tedy vyvažovat jen ten vrchol v, který je mezi nevyváženými vrcholy nejníže. Takový vrchol určitě leží na cestě mezi kořenem a přidaným vrcholem. Navíc pro každý vrchol w na cestě mezi v a přidaným prvkem platí b( w)=0.

 

Předchozí pozorování odůvodňují korektnost následujícího algoritmu operace INSERT.

 
 
Operace INSERT
 

Vstup tvoří AVL-strom T, pro každý vrchol v máme jeho ohodnocení c( v) a hodnotu b( v). Hodnota přidávaného prvku je C.

  1. Pomocné proměnné:
    v - právě probíraný vrchol,
    x - vrchol, který je kandidátem na vyvažování,
    u resp. z - předchůdci v resp. x
  2. inicializace
    • je-li strom prázdný, vytvoříme strom s jediným vrcholem r, položíme b( r)=0 a c( r)=C a výpočet ukončíme,
    • jinak položíme v a x rovno kořenu stromu, u rovno záhlaví stromu (záhlaví stromu můžeme vytvořit navíc např. jako lokální proměnnou)
  3. procházení stromu; opakujeme operace:
    1. pokud C=c( v), pak strom již vrchol s hodnotou C obsahuje a výpočet ukončíme,
    2. pokud C<c( v) a v nemá levého následníka, pak vrcholu v přidáme levého následníka w, položíme b( v)=b( v)+1, b( w)=0 a c( w)=C a pokračujeme bodem 3,
    3. pokud C<c( v) a v má levého následníka, pak
      • je-li b( v)<>0, pak položíme x=v a z=u,
      • u=v, v=levý následník v,
    4. obdobně jako bod b, opačná podmínka a b( v) snižujeme,
    5. obdobně jako bod c, opačná podmínka,
  4. aktualizace b()
    pro všechny vrcholy y ležící na cestě z x do v (včetně x a v):
    • jestliže se z y postupovalo vlevo, pak b( v)=b( v)+1,
    • jestliže se z y postupovalo vpravo, pak b( v)=b( v)-1,
  5. vyvažování stromu
    pokud je hodnota b( x)=2 nebo -2, provedeme vyvažovací operaci popsané v předchozí části (pro hodnotu -2 jde o zrcadlově symetrické verze). U vrcholů u kterých došlo ke změně následníka je potřeba aktualizovat hodnoty b().

Věta: Operace INSERT pracuje v čase O( log n)

 

Důkaz: Operace INSERT pracuje pouze s vrcholy na cestě od kořene k přidanému prvku nebo v blízkém okolí. Jelikož výška stromu je O( log n), počet zpracovávaných vrcholů je tedy také O( log n) a jelikož u každého vrcholu provádíme pouze konstantní počet operací algoritmus pracuje v čase O( log n).

 
 
Vyvažování po odebrání prvku
 

Vyvažování po operaci DELETE se provádí obdobně jako po operaci INSERT. Pro popis využijeme obrázků a popis rotací z části Vyvažování po přidání prvku a popíšeme pouze rozdílné znaky.

 

První typ nevyváženosti je podobný rotaci LL. Stromy T1 a T3 měly původně stejnou výšku o 1 větší než výška stromu T2. Ubráním vrcholu ze stromu T3 poklesla jeho výška, čímž narušila jeho vyváženost a bude nutné provést popsané vyvážení.

 

Druhý typ nevyváženosti je podobný rotaci LR. Stromy T2 a T3 měly původně stejnou výšku o 1 větší než výška stromu T1. Ubráním vrcholu ze stromu T3 poklesla jeho výška, čímž narušila jeho vyváženost a bude nutné provést popsané vyvážení.

 

Třetí typ nevyváženosti je opět podobný rotaci LL. Všechny tři stromy T1, T2 a T3 měly původně stejnou výšku. Ubráním vrcholu ze stromu T3 jeho výška poklesla, čímž narušila vyváženost vrcholu v1 a bude nutné provést popsané vyvážení.

 

Zatímco se při vyvažování třetího typu nevyváženosti výška stromu nemění, u prvního a druhého typu se výška zmenšuje, čímž může způsobit nevyváženost některých z předchůdců v1. Tedy na rozdíl od operace INSERT se kontrola nevyváženosti musí provádět vícekrát.

 
 
Operace DELETE
 

Vstup tvoří AVL-strom T, pro každý vrchol v máme jeho ohodnocení c( v) a hodnotu b( v). Hodnota odebíraného prvku je C.

  1. úvod
    • tvoří-li strom pouze odebíraný prvek, strom zrušíme,
    • jinak odebíraný prvek nalezneme a odstraníme dle standardní operace DELETE na binárním vyhledávacím stromě, v označíme předchůdce odebíraného prvku nebo předchůdce prvku, za kterého jsme provedli záměnu,
  2. procházení stromu;
    probíráme předchůdce vrcholu v směrem ke kořeni až se dostaneme ke kořeni nebo se ukončí výpočet. Pro každého následníka w provedeme operace:
    1. pokud jsme do w vstoupili z levého následníka a platí b( w)>=0, položíme b( w)=b( w)-1, a bylo-li původně b( w)=0, výpočet ukončíme,
    2. pokud jsme do w vstoupili z pravého následníka a platí b( w)<=0, položíme b( w)=b( w)+1, a bylo-li původně b( w)=0, výpočet ukončíme,
    3. pokud nebyly splněny podmínky z bodu a ani b, pak se jedná o některou ze situací popsaných v předchozí části. Provedeme patřičnou rotaci a pokud jsme provedli rotaci z případu tři, výpočet ukončíme.

    Věta: Operace DELETE pracuje v čase O( log n).

     

    Důkaz: Operace DELETE pracuje pouze s vrcholy na cestě od kořene k odebíranému prvku nebo v blízkém okolí. Jelikož výška stromu je O( log n), počet zpracovávaných vrcholů je tedy také O( log n) a jelikož u každého vrcholu provádíme pouze konstantní počet operací algoritmus pracuje v čase O( log n).

     
     
    Závěr
     

    AVL-strom je datovou strukturou s logaritmickým časem operací MEMBER, INSERT, DELETE, MIN a MAX. Jsou užitečné v případech, kdy nemůžeme zaručit náhodnost přidávaných prvků, nemůžeme si vypomoct randomizací nebo potřebujeme zaručit rychlost přístupu k položkám např. v real-time aplikacích.

     

    Příkladem použití AVL-stromu může být např. implementace správy regionů paměti v OS Linux (viz [6]).

     
     
    Literatura:
     
     
    Viliam Holub
     
    poslední změna 14.5.2001
    případné připomínky posílejte prosím na willis@centrum.cz