AVL strom
AVL strom je binárny vyhľadávací strom s jednou podmienkou navyše: V každom vrchole stromu sa hĺbka jeho ľavého a pravého podstromu líšia najviac o jedna. Táto podmienka zabezpečí, že strom nemôže príliš zdegenerovať, na rozdiel od bežného binárneho stromu, ktorý môže skončiť ako lineárne spájať zoznam. Jeho implementácia je jednoduchšie, než u dokonale vyváženého stromu. Strom má aj v najhoršom prípade zaistenú logaritmickou hĺbku voči počtu uložených vrcholov.
Vyhľadanie
Vyhľadanie prebieha rovnako ako u binárneho stromu. Ak je hľadaná hodnota rovná kľúčmi vo vrchole, našli sme správny vrchol. Ak je hodnota väčšia ako kľúč, hľadáme ďalej v pravom podstrome, respektíve ak je hodnota menšia, hľadáme ďalej v ľavom podstrome. Ak porovnávame vrchol, ktorý neexistuje (jeho ukazovateľ je null miesto adresy), potom hľadaná hodnota v strome nie je.
Vkladanie
Najprv nájdeme miesto pre vloženie nového vrchole. Podobne ako pri vyhľadanie porovnáme hodnotu kľúča aktuálneho vrchole s vkladanú hodnotou. Ak teraz dôjde k zhode, snažíme sa uložiť prvok, ktorý už uložený je a môžeme skončiť. Ak dôjdeme k neexistujúcemu vrcholu (ukazovateľ je null) pridáme na jeho miesto nový hárok do ktorého vkladáme.
Tým sme mohli zvýšiť hĺbku všetkých vrcholov ležiacich na ceste ku koreňu. Musíme teda overiť, či strom stále spĺňa podmienku AVL a prípadnú chybu opraviť pomôcť rotáciou. Bez ujmy na všeobecnosti predpokladajme, že nový vrchol je ľavý syn (vnuk ...) vrchole X. Ak hĺbka ľavého podstromu vo vrchole X bola menšia ako pravého podstromu, sú teraz rovnaké a celková hĺbka podstrome vo vrchole X sa nezmenila. Ak boli hĺbky rovnaké, je teraz ľavá dlhšia, čo nie je nijako na škodu, ale musíme túto informáciu odovzdať ďalej otcovi vrchole X. Ak bola hĺbka ľavého podstromu väčšia ako pravého, je teraz väčšia o dva a musíme použiť rotáciu. Najprv zistíme vyváženosť nášho ľavého syna X, vrchol Y. Ak je prevážaný doľava použijeme pravú rotáciu. Vrchol X aj Y sú teraz vyvážené a hĺbka celého podstrome sa nezmenila - končíme. Druhá možnosť, kedy Y bude vyvážaný, nastať nemôže. Takže tretia možnosť Y je prevážaná doprava, použijeme pravú dvojitou rotáciu cez pravého syna Y ktorého hĺbka sa zvýši o jedna a je teraz vyvážený. Hĺbka podstromu sa nezmenila a končíme.
Vymazanie
Opäť najprv nájdeme správny vrchol priechodom od koreňa ako pri vyhľadávaní. Ak dôjdeme k neexistujúcemu vrcholu, snažíme sa zmazať vrchol, ktorý neexistuje a máme hotovo. Inak dorazíme k hľadanému vrcholu a budeme sa ďalej rozhodovať podľa počtu jeho synov. Ak náš vrchol X nemá žiadneho syna, tak ho zmažeme (do ukazovateľa na neho vložíme null). Pokiaľ má jedného syna, môžeme opäť ihneď zmazať. Tentokrát miesto null vložíme do ukazovateľa na vrchol X ukazovateľ na jeho syna (čím X "preskočíme"). Pokiaľ má vrchol X dvoch synov, nájdeme vrchol Y, ako maximum z ľavého podstromu (mohli by sme aj minimum z pravého). Hodnotou Y nahradíme hodnotou vo vrchole X a následne zo stromu odstránime vrchol Y. Vlastnosť binárneho vyhľadávacieho stromu neporušíme, pretože Y bolo maximum z ľavého podstromu, teda všetko vľavo je stále menší ako hodnota nového Y a všetko vpravo zas väčšie. Odstránením sme ale mohli porušiť vlastnosť AVL stromu. Každý vrchol na ceste od zmazaného vrcholu ku koreňu môže byť teraz zle vyvážený, to budeme opäť opravovať rotáciou. V každom vrchole, ktorý dostane informáciu o skrátenie hĺbky v jednom z jeho podstromov, sa budeme rozhodovať. Opäť predpokladajme, že informácie príde od ľavého syna. Ak bol vrchol prevážaný doľava, je teraz vyvážený, ale znížila sa celková hĺbka podstrome s koreňom v X a túto informáciu odovzdáme vyššie. Ak bol vrchol vyvážený, tak teraz prepadáva doprava, ale celková hĺbka sa nezmenila a môžeme skončiť. Tretia možnosť je, že bol vrchol prevážaný doprava a teraz je teda prevážaný o dva, a to vyriešime rotáciou podľa pravého syna. Pokiaľ je pravý syn prevážaný doľava, použijeme dvojitou rotáciu vľavo. Hĺbka podstromu sa znížila, o čom informujeme vyššie. Pokiaľ je pravý syn vyvážený, rotujeme vľavo cez pravého syna. Vrchol X je teraz vyvážený a celková hĺbka sa nezmenila. Pokiaľ je pravý syn vrchole X prevážaný doprava, použijeme opäť ľavú rotáciu. Ľavý syn a vrchol X sú teraz vyvážať, ale celková hĺbka sa znížila, to oznámime o úroveň vyššie.
Zložitosť
V najhoršom prípade (najvzdialenejšie list od vrcholu) sa nám podarí nájsť správny vrchol za log (N) porovnanie, ktoré sú v konštantnom čase. Samotná operácia vloženie či mazanie robíme v konštantnom čase, rovnako tak ako rotácie (prepojenie ukazovateľov). Ak bude potrebné strom vyvažovať zakaždým pri spätnom prechode po operáciách vložení a zmazanie prvku, ktoré zmenili štruktúru. Rotácia budeme v najhoršom prípade musieť použitý log (N) krát. Čo sa ale schová do multiplikatívnej konštanty. Všetky operácie vykonávame v log (N).
