BLACK FRIDAY! Slevy až 80 % jsou všude. Tak je nepropásni a přejdi do rostoucího IT oboru!

Lekce 16 - AVL - Benchmark vyváženého stromu v jazyce C

V minulé lekci, AVL - Implementace vyváženého stromu v jazyce C, jsme implementovali vyvažování do našeho binárního vyhledávacího stromu podle algoritmu AVL.

Dnes si vyzkoušíme náš AVL strom v praxi a rychlost vyhledávání v něm porovnáme s programem, ve kterém jsme používali jen nevyvážený BST.

Testování

Na vyzkoušení sepišme program, který vytvoří telefonní seznam se jmény od "a" po "z". Potřebujeme ještě několik pomocných funkcí, zejména pro výpis stromu. Každá z těchto funkcí bude používat rekurzi jako základ zpracování. To je obecně efektivní způsob, jak se ve stromové struktuře pohybovat.

Výpis stromu

Abychom viděli výsledek, tak sepišme ještě funkce, které nám pomohou pochopit strukturu stromu.

inorder()

Projdeme strom rekurzivně tak, že se v každém vrcholu "rozdvojíme" a zavoláme se na oba podstromy a tu aktuální položku vypíšeme:

void inorder(struct NODE* node)
{
    if (node != NULL)
    {
        if (node->left != NULL)
        {
            printf("L ");
            inorder(node->left);
            printf("U ");
        }
        print_node(node);
        if (node->right != NULL)
        {
            printf("R ");
            inorder(node->right);tak
            printf("U ");
        }
    }
}

Funkce prochází celý strom a vypisuje cestu od nejmenší položky po největší (protože jde prvně doleva, kde je menší položka a pak se prvně zavolá znovu zas doleva atd.). Krok označovaný "L" je posun ve stromu vlevo, "R" je posun ve stromu vpravo a "U" je posun ve stromu nahoru.

Podobně přidáme ještě 2 funkce, které fungují úplně stejně, jen vypíší položku v jinou dobu.

preorder()


 

...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 C tutoriálu vytvoříme pomocné funkce pro výpis vyváženého AVL stromu a počtu jeho prvků a pak porovnáme vyhledávání v AVL s nevyváženým BST.

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 120 bodů
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říš 75 Kč. Nabídka je časově omezená a platí pro všechny lekce v kurzu. Nakup teď a získej limitovanou 20% slevu.
120 bodů získáš za přidání svého článku na síť nebo odpovídá 374 Kč 300 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)