NOVINKA! E-learningové kurzy umělé inteligence. Nyní AI za nejlepší ceny. Zjisti více:
NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!

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

Koupit tento kurz

Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za pouhých 375 Kč
Aktuální stav konta 0 Kč
Koupí tohoto balíčku získáš přístup ke všem 17 článkům (17 lekcí) tohoto kurzu.

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

Kredity 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