{{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.
{{Stub}}
