{{TIN066 Skripta}}
{{TODO|rozepsat}}

**Definice**: Binární vyhledávací strom nazveme AVL, pokud pro každý uzel platí: Výška levého a pravého podstromu se liší nejvýše o 1.  

Pro vrchol *v* si definujme $\eta(v)$ - výška stromu s kořenem *v* (= nejdelší cesta z *v* do listu). Dále definujme $\omega(v) = \eta(v.pravý) - \eta(v.levý)$. Omega tedy bude -1, 0 nebo 1. U vrcholů evidujeme pouze Omegu, Etu lze z ní dopočítat.

Definujme si mn(i) - minimální počet uzlů AVL stromu výšky i, mx(i) - maximální počet uzlů AVL stromu výšky i. Maximální bude nejspíše "úplný zarovnaný" strom - po přidání dalšího vrcholu se už zvýší výška, tedy $mx(i) = 2^i-1$. Hodnota $mn(i) = mn(i-1) + mn(i-2) + 1 = F_{i+2}-1$, kde $F_i$ je i-té fibonacciho číslo (dokážeme indukcí dle vztahu mezi rovnítky). Z toho všeho odvodíme, že výška je vždy O(log n) vzhledem k počtu uzlů.

## Algoritmy ##

Vyhledání a Member je stejné, jako u BVS. Při vkládání a mazání už bude třeba vyvažovat pomocí Rotace a Dvojita-rotace, při tom upravovat hodnotu Omega.

Tvrzení: Když se $\eta(v)$ po INSERTu zvětší, pak nové $\omega(v)$ není 0. Důkaz: kdyby se změnilo na 0, pak předtím muselo být -1 nebo 1 a přidávalo se do kratšího podstromu, což je ve sporu s tím, že se zvětší Eta.

**Kontrola-INSERT t** : předpokládáme, že podstrom *t* je již vyvážený, vyváží zbytek směrem ke kořenu.

* pokud (t levý syn)
    * pokud (omage otce 1) omega otce 0;  konec;
    * pokud (omega otce 0) omega otce -1; Kontrola-INSERT(otec);  konec;
    * pokud (omega t -1) Rotace(otec, t); omega otce = omega t = 0;  konec;
    * t2 pravý syn t; Dvojita-rotace(otec, t, t2);
    * pokud (omega t2  0) omega otce 0;  omega t  0;
    * pokud (omega t2  1) omega otce 0;  omega t -1;
    * pokud (omega t2 -1) omega otce 1;  omega t  0;
    * omega t2 0;
* to samé symetricky pokud (t pravý syn)

Všimněte si, že procedura po provedení rotace končí, provede nejvýše jednu rotaci.

**INSERT x** - stačí vložit jako do BVS. List *t* změníme na vnitnří vrchol, připojíme dva listy a zavoláme Kontrola-INSERT(t).

**Kontrola-DELETE t**: předpokládáme, že podstrom *t* je již vyvážený, vyváží zbytek směrem ke kořenu.

* pokud (t levý syn)
    * pokud (omega otce  0) omega otce 1;  konec;
    * pokud (omega otce -1) omega otce 0;  Kontrola-DELETE(otec); konec;
    * pokud (omega bratra >= 0) 
        * Rotace(otec, bratr)
        * pokud (omega otce 0)  omega otce 1, omega bratra -1;
        * jinak omega otce 0, omega bratra 0, Kontrola-DELETE(otec);
    * jinak
        * u1 levý syn bratra, Dvojita-rotace(otec, bratr, u1);
        * pokud (omega u1  1) omega bratra 0, omega otce 1;
        * pokud (omega u1  0) omega bratra 0, omega otce 0;
        * pokud (omega u1 -1) omega bratra 1, omega otce 0;
        * omega u1 0;  Kontrola-delete(u1);
* to samé symetricky pokud (t pravý syn)

Může se provést až O(log n) rotací.

**DELETE x** : mažu vrchol jako z BVS. Buď *t* vrchol, jehož otec se odstranil (jeho otec buď přímo měl hodnotu x, nebo byl maximem z levého podstromu, proto se odstranil). Bratr *t* je list. Pak zavoláme Kontrola-DELETE(t). 

{{Stub}}