{{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''' : 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}}
