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