{{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\acute{y})-\eta (v.lev\acute{y})$. 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}}