3.6 AVL

Z předchozího výkladu tedy plyne, že žádné kritérium vyváženosti stejně jako příliš přísné kritérium vyváženosti vedou v nejhorším případě na lineární složitost alespoň jedné z operací BVS.

Kritérium vyváženosti BVS je tedy třeba definovat méně restriktivně, stačí udržovat hloubku $O(\log n)$.

Definice 3.17 (AVL)

BVS je hloubkově vyvážený, pokud pro každý jeho vrchol v platí

\begin{equation*} |h(L(v)) − h(R(v))∣ \lt 1 \end{equation*}

Věta 3.5 (O hloubce hloubkově vyvážených stromů)

Hloubkově vyvážený strom s $n$ vrcholy má hloubku $\Theta(\log n)$.

Zobrazit důkaz

Definujme $A_h$ = min. počet vrcholů HV stromu hloubky $h$.
Ukážeme, že $A_h$ roste exponenciálně s $h$.
Nejmenší takové stromy dané hloubky jsou maximálně „hloubkově vyvážené“ v mezích definice, čili v každém vnitřním vrcholu v platí $|h(L(v)) − h(R(v))| = 1$.
Pro $h ≤ 4$ lze nejmenší HV stromy hloubky $h$ nalézt přímo:TODO obrázek Přednáška 6 slajd 23
Obecně pak minimální HV strom hloubky $h$ musí mít jako podstromy minimální HV stromy hloubky $h − 1$ a $h − 2$.
Musí tedy platit $A_h = A_{h−1} + A_{h−2} + 1$.
Dokážeme indukcí, že $A_{h+1} ≥ 2^{\frac{h}{2}} = 1.41^h$
ZK:
\begin{align*} A_1 = 1 &\geq 2^{\frac{0}{2}} = 1 \\ A_2 = 2 &\geq 2^{\frac{1}{2}} = 1.414\end{align*}
IK:
\begin{align*} A_{h+1} &= 1 + A_h + A_{h-1} \\ &> 2^{\frac{h-1}{2}} + 2^{\frac{h-2}{2}} \\ &= 2^{\frac{h}{2}} \cdot (2^{\frac{-1}{2}} + 2^{-1}) \\ &> 2^{\frac{h}{2}} \cdot (\frac{1}{2} + \frac{1}{2}) \\ &= 2^{\frac{h}{2}}\end{align*}
HV strom hloubky $h + 1$ má tedy nejméně $√2^{h}$ vrcholů.
Proto HV strom o $n$ vrcholech má hloubku nejvýše $\log_{√2}{n} + 1$.
A protože je binární, nemůže mít hloubku menší než $⌊\log_{2}{n}⌋$. viz Přednáška 4.
Tedy hloubka HV stromu o $n$ vrcholech je $\Theta(\log n)$.

$\square$

Pozorování 3.9

Operace BVSShow, BVSMin, BVSPred a BVSFind nemění ani tvar ani obsah BVS, fungují tedy beze změny i pro AVL stromy.

Definice 3.18 (AVL rotace doprava)

Jednoduchá rotace doprava opraví hloubkovou nevyváženost v modelové situaci dle obrázku dole, kdy:
- $y = l(x)$ a $h = h(B) = h(C) = h(A) − 1$ a tudíž
- $δ(y) = -1$ a $δ(x) = -2$.
Po provedení rotace doprava je $δ(x) = δ(y) = 0$.
Z definice BVS plyne, že přepojení B od $y$ k $x$ zachovává BVS.

Rotace doleva je zrcadlově symetrická modelová situace

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {rotateLeft}{Vrchol $x$ v BVS}
    \STATE $y$ := $r(x)$
    \STATE $r(x)$ := $l(y)$
    \STATE $l(y)$ := $x$
    \STATE $p(r(x))$ := $x$; $p(y)$ := $p(x)$; $p(x)$ := $y$
    \STATE $h(T(x))$ := max($h(L(x))$, $h(R(x))$) + 1
    \STATE $h(T(y))$ := max($h(R(y))$, $h(T (x))$) + 1
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Algoritmus 3.7: rotateLeft ($x$)

Vše symetricky pro rotateRight($x$).

Pozorování 3.10

Pokud je $x$ vrcholem v binárním vyhledávacím stromě, potom po volání rotateLeft($x$) máme opět binární vyhledávací strom.

Příklad 3.2

Existuje případ, kdy nám jen jednoduchá L nebo R rotace nestačí na vyvážení stromu?

Zobrazit řešení

Ano, ale i tyto příklady lze vyřešit jen za využití L a R rotací s menšími úpravami.

Pak opraci nazýváme dvojitou LR/RL rotaci podle pořadí jednoduchých rotací.

Definice 3.19 (AVLInsert)

Nový vrchol vložíme standardně jako list se znaménkem $0$.
Z prázdného podstromu hloubky 0 se tak stal jednovrcholový podstrom hloubky 1.
Potom je třeba přepočítat hloubky stromů na cestě z jeho rodiče do kořene.
Proto budeme propagovat nahoru informaci o tom, že se zvětšila hloubka podstromu.
V jednotlivých úrovních se tato informace zpracuje v závislosti na hloubkách příslušných sourozenců.
Tuto kontrolu a případné napravení nevyvážeností můžeme elegantně provést během návratu z rekurze v proceduře AVLInsert.

Definice 3.20 (AVLDelete)

Obdobně jako AVLInsert.
Vrchol smažeme podle BVSDelete a po cestě zpět do kořene propagujeme informaci o snížení hloubky podstromu.
Pokaždé mažeme list nebo vrchol s jediným synem, takže stačí propagovat od místa smazaného vrcholu nahoru.
Popíšeme propagaci pro jeden vrchol.
Nechť do vrcholu x přišla ze syna informace o snížení hloubky podstromu.
Ukážeme opět pro případ, kdy přišla z levého syna.
Případ, kdy přišla z pravého syna se řeší obdobně, jen se vymění význam +1 a -1, levého a pravého podstromu a směr rotací.
Rozlišíme opět tři případy podle znaménka vrcholu x.

Tvrzení 3.1 (Složitost operací)

AVLInsert a AVLDelete trvají $O(\log n)$.

Zobrazit důkaz

Hloubka AVL stromu je vždy $\Theta(\log n)$.
Původní implementace operací BVSFind, BVSInsert a BVSDelete tedy pracují v logaritmickém čase.
Při vyvažování se operace vždy vrací po cestě do kořene a v každém vrcholu provede $\Theta(1)$ operací, takže celkově také trvá $\Theta(\log n)$.

$\square$