{{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 <math>\eta(v)</math> - výška stromu s kořenem ''v'' (= nejdelší cesta z ''v'' do listu). Dále definujme <math>\omega(v) = \eta(v.pravý) - \eta(v.levý)</math>. 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 <math>mx(i) = 2^i-1</math>. Hodnota <math>mn(i) = mn(i-1) + mn(i-2) + 1 = F_{i+2}-1</math>, kde <math>F_i</math> 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 <math>\eta(v)</math> po INSERTu zvětší, pak nové <math>\omega(v)</math> 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'''
* 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 a na nově vzniklý vrchol ''v'' zavolat Kontrola-INSERT(v).
Mazání je složité, může se provést až O(log n) rotací.
{{Stub}}
