Zpracováno dle [1], [2] a [3] jako referát na cvičení z předmětu Datové struktury.
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í:
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.
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.
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.
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í
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.
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.
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 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.
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.
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).
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]).