TIN066 AVL stromy

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Tato část je neúplná a potřebuje rozšířit. 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ý) - \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).