Lekce 15 - AVL - Implementace vyváženého stromu v jazyce C
V minulé lekci, Binární vyhledávací stromy (BST) v jazyce C, jsme si představili a implementovali binární strom.
V dnešní lekci vylepšíme náš binární vyhledávací strom (BST) a přidáme k němu funkci automatického vyvažování. Tím pádem nám nikde nezdegeneruje na strukturu podobnou spíše seznamu, než stromu. To by se nám teď mohlo stát, když by se do stromu vkládaly jen takové prvky, že by přetížily jen jednu z jeho větví.
Strom, který se automaticky vyvažuje a který zde budeme implementovat, se nazývá AVL strom podle dvou autorů, kteří ho vynalezli a publikovali v roce 1962 - GM Adelson-Velskii a EM Landis.
Definice vyváženého stromu
Připomeňme si, že jsme definovali vyvážený strom tak, že výška levé větve stromu položky se od výšky pravé větve stromu liší maximálně o jedna.
Proto při vložení nové položky musíme zkontrolovat, zda jsme
neporušili pravidlo vyvážení stromu a pokud jsme ho porušili, tak musíme
strom vyvážit. Samozřejmě, pokud je rozdíl mezi výškou stromu vlevo a
vpravo větší než 1, tak vyvažujeme doprava a opačně, pokud
je rozdíl mezi výškou stromu vpravo a vlevo větší než 1, tak
vyvažujeme doleva. Vyvažování stromů provádíme pomocí tzv.
rotací, které si hned vysvětlíme. Pokračujeme s projektem
našeho BST stromu.
Funkce k vyvážení stromu
Udělejme si prvně pomocné funkce, které budeme k vyvažování našeho stromu potřebovat.
get_height_tree()
...konec náhledu článku...
Pokračuj dál
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
Koupit tento kurz
Před koupí tohoto článku je třeba koupit předchozí díl
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
Popis článku
Požadovaný článek má následující obsah:
V tutoriálu implementujeme funkci ke zjištění vyváženosti vrcholu vyhledávacího AVL stromu, rotace a konečně automatické vyvažování při vložení prvku.
Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.
