Aktuálně: Postihly zákazy tvou profesi? Poptávka po ajťácích prudce roste, využij slevové akce 50% výuky zdarma!
Pouze tento týden sleva až 80 % na e-learning týkající se Javy

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

Znalosti v hodnotě stovek tisíc získáš za pár korun

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.

Omezená nabídka: Nauč se vše a ušetři

Koupit lekce a funkce postupně a po jednom 150 bodů
Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za exkluzivní cenu 128 bodů (320 Kč)
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 17 lekcím s kontrolou a certifikací a ještě navíc ušetříš 55 Kč. Nabídka je omezená pouze pro první lekce z kurzu a obsahuje exkluzivní slevu 15%.
128 bodů získáš za přidání svého článku na síť nebo odpovídá 374 Kč 320 Kč

Pozor, pokud si koupíš pouze tuto lekci, ztratíš nárok na speciální slevu 15% na balíček všech lekcí.

Koupit jen lekci 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

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.

Co od nás v dalších lekcích dostaneš?
  • 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.

Body 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íť.

Článek pro vás napsal Daniel Martinko
Avatar
Aktivity (3)