Tento týden až 80% sleva na e-learning týkající se jazyka C
50 % bodů zdarma na online výuku díky naší Slevové akci!

Lekce 14 - 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...

Prémiový článek

Prémiový článek

Na itnetwork.cz se nachází největší a nejucelenější česká databáze s výukovými články, jejímž cílem je umožnit kvalitní vzdělání v oblasti IT úplně každému. Měsíčně zobrazíme k milionu článků a sklidíme desítky děkovných emailů, kde nám sdělujete, že jsme vám pomohli k lepšímu zaměstnání nebo vzdělání.

Ačkoli se snažíme držet většinu obsahu úplně zadarmo, udržovat síť v provozu a aktuální stojí obrovské úsilí. Proto je nějaký obsah, jako cvičení nebo odbornější články, přístupný pouze za body. Nebojte, nestojí to skoro nic :)

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.

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

Koupit články a funkce postupně a po jednom 130 bodů
Koupit všechny aktuálně dostupné články v sekci se všemi funkcemi za exkluzivní cenu 104 bodů
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 15 článkům s kontrolou a certifikací a ještě navíc ušetříš 65 Kč. Nabídka je časově omezená a platí pro všechny články v kurzu. Nakup teď a získej limitovanou 20% slevu.
104 bodů získáš za přidání svého článku na síť nebo odpovídá 325 Kč 260 Kč
Pro přístup k článku potřebuješ 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

Koupí článku k němu získáš neomezený přístup a to napořád. Posuneš své znalosti zas kousek dopředu a zároveň nám pomůžeš udržovat celý projekt při životě a pomáhat vám tak k lepší budoucnosti.

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

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

Dobít body můžeš okamžitě např.:

Kartou SMS Převodem
Kartou SMS Převodem
Článek pro vás napsal Daniel Martinko
Avatar
Aktivity (2)