TIN066 AVL stromy
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).
