Vianoce v ITnetwork sú tu! Dobí si teraz kredity a získaj až 80 % extra kreditov na e-learningové kurzy ZADARMO. Zisti viac.
Hľadáme nové posily do ITnetwork tímu. Pozri sa na voľné pozície a pridaj sa k najagilnejšej firme na trhu - Viac informácií.

16. diel - AVL - Benchmark vyváženého stromu v jazyku C

V minulej lekcii, AVL - Implementácia vyváženého stromu v jazyku C , sme implementovali vyvažovanie do nášho binárneho vyhľadávacieho stromu podľa algoritmu AVL.

Dnes si vyskúšame náš AVL strom v praxi a rýchlosť vyhľadávania v ňom porovnáme s programom, v ktorom sme používali len nevyvážený BST.

Testovanie

Na vyskúšanie napíšme program, ktorý vytvorí telefónny zoznam s menami od "a" po "z". Potrebujeme ešte niekoľko pomocných funkcií, najmä pre výpis stromu. Každá z týchto funkcií bude používať rekurziu ako základ spracovania. To je všeobecne efektívny spôsob, ako sa v stromovej štruktúre pohybovať.

Výpis stromu

Aby sme videli výsledok, tak napíšme ešte funkcie, ktoré nám pomôžu pochopiť štruktúru stromu.

inorder()

Prejdeme strom rekurzívne tak, že sa v každom vrchole "rozdvojíme" a zavoláme sa na oba podstromy a tú aktuálnu 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 ");
        }
    }
}

Funkcia prechádza celý strom a vypisuje cestu od najmenšej položky po najväčšie (pretože ide prvýkrát doľava, kde je menšia položka a potom sa prvýkrát zavolá znovu zas doľava atď.). Krok označovaný "L" je posun v strome vľavo, "R" je posun v strome vpravo a "U" je posun vo stromu nahor.

Podobne pridáme ešte 2 funkcie, ktoré fungujú úplne rovnako, len vypíšu položku v inú dobu.

preorder()


 

...koniec náhľadu článku...
Pokračuj ďalej

Vedomosti v hodnote stoviek tisíc získaš za pár korún

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.

Obmedzená ponuka: Nauč sa všetko a ušetri

Kúpiť všetky aktuálne dostupné lekcie s funkciou odovzdávanie úloh za exkluzívnu cenu 300 kreditov
Aktuálny stav konta 0 kreditov
Kúpou tohoto výhodného balíčku získaš prístup ku všetkým 17 článkom (17 lekcií) s kontrolou a certifikáciou a ešte naviac ušetríš 76 Kč. Ponuka je časovo obmedzená a platí pro všetky lekcie v kurze. Nakúp teraz a získaj limitovanou 20% zľavu.

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.

Čo od nás v ďalších lekciách dostaneš?
  • 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 C tutoriálu vytvoríme pomocné funkcie pre výpis vyváženého AVL stromu a počtu jeho prvkov a potom porovnáme vyhľadávanie v AVL s nevyváženým BST.

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

Článok pre vás napísal Daniel Martinko
Avatar
Aktivity