Prednáška 21

Binárne vyhľadávacie stromy

Príklad binárneho vyhľadávacieho stromu.

Stromy sa v informatike často používajú. Ďalším príkladom sú binárne vyhľadávacie stromy, ktoré slúžia na ukladanie množiny prvkov. Prvky množiny teda nemáme v poli, ani v spájanom zozname, ale vo vrcholoch binárneho stromu.

• V binárnom vyhľadávacom strome má každý vrchol 0,1 alebo 2 deti
• V každom vrchole máme položku s dátami (pre jednoduchosť typu int)
• Pre každý vrchol v stromu platí:
  • Každý vrchol v ľavom podstrome v má hodnotu data menšiu ako vrchol v
  • Každý vrchol v pravom podstrome v má hodnotu data väčšiu ako vrchol v
• Z toho vyplýva, že ak vypíšeme strom v inorder poradí, dostaneme prvky usporiadané
• Pre danú množinu kľúčov existuje veľa vyhľadávacích stromov

Cvičenie: nájdite všetky binárne vyhľadávacie stromy pozostávajúce z troch uzlov s kľúčmi 1, 2, 3.

Definícia dátových štruktúr

Vrchol typu node

• Položka data typu int
• Smerník na ľavé a pravé dieťa
• Na niektoré úlohy (napr. mazanie vrcholu) sa hodí aj smerník na rodiča (ten má hodnotu NULL v koreni)

Celý strom je štruktúra obsahujúca iba smerník na koreň

• Pre prázdny strom je to NULL.

struct node {
    /* vrchol binárneho vyhľadávacieho stromu  */
    int data;       /* hodnota */
    node * parent;  /* rodič vrchola, NULL v koreni */
    node * left;    /* ľavé dieťa, NULL ak neexistuje */
    node * right;   /* pravé dieťa, NULL ak neexistuje */
};

/* Samotná štruktúra binárneho vyhľadávacieho stromu (obal pre používateľa). */
struct binarySearchTree {
    node *root;  /* koreň stromu, NULL pre prázdny strom */
};

Inicializácia prázdneho binárneho vyhľadávacieho stromu

/** Funkcia inicializuje prázdny binárny vyhľadávací strom */
void bstInit(binarySearchTree &t) {    
    t.root = NULL;
}

Likvidácia binárneho vyhľadávacieho stromu

Likvidáciu podstromu zakoreneného v danom uzle root realizujeme funkciou destroy, obdobne ako pri všeobecných binárnych stromoch. Používateľovi navyše dáme k dispozícii aj funkciu bstDestroy, ktorá zlikviduje binárny vyhľadávací strom t tak, že zavolá funkciu destroy na jeho koreň.

/* Uvolni pamat pre podstrom s korenom *root. */
void destroy(node *root) {
    if (root != NULL) {
        destroy(root->left);
        destroy(root->right);
        delete root;
    }
}

/* Zlikviduje strom t (uvolni pamat). */
void bstDestroy(binarySearchTree &t) {
    destroy(t.root);
}

Hľadanie v binárnom vyhľadávacom strome

Funkcia findNode v podstrome s koreňom root hľadá uzol, ktorého položka dáta obsahuje hľadaný kľúč key. Vráti takýto uzol alebo NULL ak neexistuje

• Najskôr porovná hľadaný kľúč s dátami v koreni
  • Ak sa rovnajú, končíme (našli sme, čo hľadáme)
  • Ak je hľadaná hodnota menšia ako dáta v koreni, musí byť v ľavom podstrome, ak je väčšia v pravom
• V príslušnom podstrome sa rozhodujeme podľa tých istých pravidiel
• Keď narazíme na prázdny podstrom, dáta sa v strome nenachádzajú
• Dá sa zapísať rekurzívne alebo cyklom, lebo vždy ideme iba do jedného podstromu

Funkcia bstFind zavolá funkciu findNode pre koreň daného binárneho vyhľadávacieho stromu t a pomocou nej zistí, či tento strom obsahuje uzol s kľúčom key.

/* Ak v strome s korenom root existuje uzol s klucom key, 
 * vrati ho na vystupe. Inak vrati NULL. */
node * findNode(node *root, int key) {
    node * v = root;
    while (v != NULL && v->data != key) {
        if (key < v->data) {
            v = v->left;
        } else {
            v = v->right;
        }
    }
    return v;
}

/** Rekurzívna verzia */
node *findNodeR(node *root, int key) {
    if (root == NULL || key == root->data) {
        return root;
    } else if (key < root->data) {
        return findNodeR(root->left, key);
    } else {  // key > root->data
        return findNodeR(root->right, key);
    }
}

/* Zisti, ci strom t obsahuje uzol s klucom key. */
bool bstFind(binarySearchTree &t, int key) {
    return findNode(t.root, key) != NULL;
}

Čas výpočtu je v najhoršom prípade úmerný výške stromu.