15. diel - AVL - Implementácia vyváženého stromu v jazyku C

V minulej lekcii, Binárne vyhľadávacie stromy (BST) v jazyku C , sme si predstavili a implementovali binárny strom.

V dnešnej lekcii vylepšíme náš binárny vyhľadávací strom (BST) a pridáme k nemu funkciu automatického vyvažovanie. Tým pádom nám nikde nezdegeneruje na štruktúru podobnú skôr zoznamu, než stromu. To by sa nám teraz mohlo stať, keď by sa do stromu vkladali len také prvky, že by preťažil len jednu z jeho konárov.

Strom, ktorý sa automaticky vyvažuje a ktorý tu budeme implementovať, sa nazýva AVL strom podľa dvoch autorov, ktorí ho vynašli a publikovali v roku 1962 - GM Adelson-Velskii a EM Landis.

Definícia vyváženého stromu

Pripomeňme si, že sme definovali vyvážený strom tak, že výška ľavej vetvy stromu položky sa od výšky pravej vetvy stromu líšia maximálne o jedna.

Preto pri vložení novej položky musíme skontrolovať, či sme neporušili pravidlo vyváženie stromu a ak sme ho porušili, tak musíme strom vyvážiť. Samozrejme, ak je rozdiel medzi výškou stromu vľavo a vpravo väčšia ako 1, tak vyvažujeme doprava a opačne, ak je rozdiel medzi výškou stromu vpravo a vľavo väčšie ako 1, tak vyvažujeme doľava. Vyvažovanie stromov vykonávame pomocou tzv. Rotáciou, ktoré si hneď vysvetlíme. Pokračujeme s projektom nášho BST stromu.

Funkcie k vyváženie stromu

Urobme si prvýkrát pomocné funkcie, ktoré budeme k vyvažovanie nášho stromu potrebovať.

get_height_tree()

...koniec náhľadu článku...
Pokračuj ďalej