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
Minul si až sem a to je super! Veríme, že ti prvé lekcie ukázali niečo nového a užitočného.
Chceš v kurze pokračovať? Prejdi do prémiové sekcie.
Kúpiť tento kurz
Pred kúpou tohto článku je potrebné kúpiť predchádzajúci diel
Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.
- Neobmedzený a trvalý prístup k jednotlivým lekciím.
- Kvalitné znalosti v oblasti IT.
- Zručnosti, ktoré ti pomôžu získať vysnívanú a dobre platenú prácu.
Popis článku
Požadovaný článok má nasledujúci obsah:
V tutoriálu implementujeme funkciu na zistenie vyváženosti vrchole vyhľadávacieho AVL stromu, rotácie a konečne automatické vyvažovanie pri vložení prvku.
Kredity získaš, keď podporíš našu sieť. To môžeš urobiť buď zaslaním symbolickej sumy na podporu prevádzky alebo pridaním obsahu na sieť.
