Lekce 7 - AVL strom

V minulé lekci, Binární vyhledávací strom (BST), jsme si popsali algoritmus vyhledávací struktury binárního vyhledávacího stromu (BST) s obrázky a teorií.

AVL strom je binární vyhledávací strom s jednou podmínkou navíc: V každém vrcholu stromu se hloubka jeho levého a pravého podstromu liší nejvýše o jedna. Tato podmínka zajistí, že strom nemůže příliš zdegenerovat, na rozdíl od běžného binárního stromu, který může skončit jako lineární spojový seznam. Jeho implementace je jednodušší, než u dokonale vyváženého stromu. Strom má i v nejhorším případě zajištěnu logaritmickou hloubku vůči počtu uložených vrcholů.

Vyhledání

Vyhledání probíhá stejně jako u binárního stromu. Pokud je hledaná hodnota rovna klíči ve vrcholu, nalezli jsme správný vrchol. Pokud je hodnota vetší než klíč, hledáme dál v pravém podstromu, respektive pokud je hodnota menší, hledáme dál v levém podstromu. Jestliže porovnáváme vrchol, který neexistuje (jeho ukazatel je null místo adresy), pak hledaná hodnota ve stromu není.

Vkládání

Nejprve nalezneme místo pro vložení nového vrcholu. Podobně jako při vyhledání porovnáme hodnotu klíče aktuálního vrcholu s vkládanou hodnotou. Jestliže nyní dojde ke shodě, snažíme se uložit prvek, který již uložen je a můžeme skončit. Pokud dojdeme k neexistujícímu vrcholu (ukazatel je null) přidáme na jeho místo nový list do něhož vkládáme.

Tím jsme mohli zvýšit hloubku všech vrcholů ležících na cestě ke kořenu. Musíme tedy ověřit, zda strom stále splňuje podmínku AVL a případnou chybu opravit pomoci rotací. Bez újmy na obecnosti předpokládejme, že nový vrchol je levý syn(vnuk...) vrcholu X. Pokud hloubka levého podstromu ve vrcholu X byla menší než pravého podstromu, jsou nyní stejné a celková hloubka podstromu ve vrcholu X se nezměnila. Pokud byly hloubky stejné, je nyní levá delší, což není nijak na škodu, ale musíme tuto informaci předat dále otci vrcholu X. Pokud byla hloubka levého podstromu větší než pravého, je nyní větší o dva a musíme použít rotaci. Nejprve zjistíme vyváženost našeho levého syna X, vrchol Y. Pokud je převážen doleva použijeme pravou rotaci. Vrchol X i Y jsou nyní vyvážené a hloubka celého podstromu se nezměnila – končíme. Druhá možnost, kdy Y bude vyvážen, nastat nemůže. Takže třetí možnost Y je převážena doprava, použijeme pravou dvojitou rotaci přes pravého syna Y jehož hloubka se zvýší o jedna a je nyní vyvážen. Hloubka podstromu se nezměnila a končíme.

Vymazání

Opět nejprve nalezneme správný vrchol průchodem od kořene jako při vyhledávání. Pokud dojdeme k neexistujícímu vrcholu, snažíme se smazat vrchol, který neexistuje a máme hotovo. Jinak dorazíme k hledanému vrcholu a budeme se dál rozhodovat dle počtu jeho synů. Pokud náš vrchol X nemá žádného syna, tak ho smažeme (do ukazatele na něj vložíme null). Pokud má jednoho syna, můžeme opět ihned smazat. Tentokrát místo null vložíme do ukazatele na vrchol X ukazatel na jeho syna(čímž X „přeskočíme“). Pokud má vrchol X dva syny, najdeme vrchol Y, jakožto maximum z levého podstromu (mohli bychom i minimum z pravého). Hodnotou Y nahradíme hodnotou ve vrcholu X a následně ze stromu odstraníme vrchol Y. Vlastnost binárního vyhledávacího stromu neporušíme, protože Y bylo maximum z levého podstromu, tudíž vše vlevo je stále menší než hodnota nového Y a vše vpravo zas větší. Odstraněním jsme ale mohli porušit vlastnost AVL stromu. Každý vrchol na cestě od smazaného vrcholu ke kořeni může být nyní špatně vyvážen, to budeme opět opravovat rotací. V každém vrcholu, který obdrží informaci o zkrácení hloubky v jednom z jeho podstromů, se budeme rozhodovat. Opět předpokládejme, že informace přijde od levého syna. Pokud byl vrchol převážen doleva, je nyní vyvážen, ale snížila se celková hloubka podstromu s kořenem v X a tuto informaci předáme výše. Pokud byl vrchol vyvážen, tak nyní přepadává doprava, ale celková hloubka se nezměnila a můžeme skončit. Třetí možnost je, že byl vrchol převážen doprava a nyní je tedy převážen o dva, a to vyřešíme rotací podle pravého syna. Pokud je pravý syn převážen doleva, použijeme dvojitou rotaci vlevo. Hloubka podstromu se snížila, o čemž informujeme výše. Pokud je pravý syn vyvážen, rotujeme vlevo přes pravého syna. Vrchol X je nyní vyvážen a celková hloubka se nezměnila. Pokud je pravý syn vrcholu X převážen doprava, použijeme opět levou rotaci. Levý syn a vrchol X jsou nyní vyváženi, ale celková hloubka se snížila, to oznámíme o úroveň výš.

Složitost

V nejhorším případě (nejvzdálenější list od vrcholu) se nám podaří nalézt správný vrchol za log(N) porovnání, které jsou v konstantním čase. Samotná operace vložení či mazání děláme v konstantním čase, stejně tak jako rotace (přepojení ukazatelů). Pokud bude nutné strom vyvažovat pokaždé při zpětném průchodu po operacích vložení a smazání prvku, které změnily strukturu. Rotace budeme v nejhorším případě muset použit log(N) krát. Což se ale schová do multiplikativní konstanty. Všechny operace provádíme v log(N).

V další lekci, B-stromy, si popíšeme b-strom včetně algoritmů pro hledání, vkládání a odebírání prvků.