Prednáška 21

Binárne vyhľadávacie stromy

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

Stromy sa v informatike používajú na veľa účelov. Ďalším príkladom sú binárne vyhľadávacie stromy, ktoré môžu slúžiť na implementovanie abstraktného dátového typu dynamická množina, ktorý sme videli na prednáške 14. Prvky množiny nebudeme ukladať do poľa, ani v spájaného zoznamu, ale do 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 uložená vo vrchole */
    node * parent;  /* rodič vrchola, NULL v koreni */
    node * left;    /* ľavé dieťa, NULL ak neexistuje */
    node * right;   /* pravé dieťa, NULL ak neexistuje */
};

/* Samotná dynamická množina (obal pre používateľa). */
struct set {
    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 init(set &s) {
    s.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 destroy, ktorá dostane množinu implementovanú ako strom a tento strom zlikviduje.

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

/* Zlikviduje množinu s (uvoľní pamäť). */
void destroy(set &s) {
    destroy(s.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 contains 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 reprezentujuci mnozinu s 
 * obsahuje uzol s klucom key. */
bool contains(set &s, int key) {
    return findNode(s.root, key) != NULL;
}

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

Binárne vyhľadávacie stromy

Opakovanie

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

Binárny vyhľadávací strom (binary search tree) je dátová štruktúra určená na ukladanie dynamickej množiny prvkov.

• 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

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 */
};

Videli sme vyhľadávanie prvku v binárnom vyhľadávacom strome. Čas výpočtu je v najhoršom prípade úmerný výške stromu.

Vkladanie do binárneho vyhľadávacieho stromu

Nasledujúca funkcia insertNode vloží uzol *v na správne miesto podstromu zakoreneného v *root ako jeho list.

• Predpokladáme, že prvok v strome nie je.
• Putujeme po strome podobne ako pri vyhľadávaní prvku, až kým nenarazíme na nulový smerník.
  • Na tomto mieste by mal byť nový prvok, takže ho tam pridáme ako nový list
  • Uvádzame rekurzívnu verziu, ale dá sa aj cyklom, podobne ako pri hľadaní
• Funkcia add vytvorí uzol s daným kľúčom key a pomocou funkcie insertNode ho vloží do binárneho vyhľadávacieho stromu.

/* Vloží uzol v na správne miesto podstromu zakoreneného v root */
void insertNode(node *root, node *v) {
    assert(root != NULL && v != NULL);
    if (v->data < root->data) {
        if (root->left == NULL) {
            root->left = v;
            v->parent = root;
        } else {
            insertNode(root->left, v);
        }
    } else {
        if (root->right == NULL) {
            root->right = v;
            v->parent = root;
        } else {
            insertNode(root->right, v);
        }
    }
}

/* Vloží do stromu pre mnozinu s nový uzol s kľúčom key. */
void add(set &s, int key) {
    node *v = new node;
    v->data = key;
    v->left = NULL;
    v->right = NULL;
    v->parent = NULL;
    if (s.root == NULL) {
        // specialny pripad, ked vkladame prvy uzol
        s.root = v;
    } else {
        insertNode(s.root, v);
    }
}

Čas vkladania je tiež v najhoršom prípade úmerný hĺbke stromu.

Cvičenia

• Napíšte nerekurzívny variant funkcie insertNode.
• Napíšte funkciu treeSort, ktorá z poľa celých čísel a pomocou volaní funkcie add vytvorí binárny vyhľadávací strom a následne pomocou prehľadávania tohto stromu v poradí inorder pole a utriedi.
• Ako bude vyzerať strom po nasledujúcej postupnosti operácií?

    set s;
    init(s);
    add(s, 2);
    add(s, 5);
    add(s, 3);
    add(s, 10);
    add(s, 7);  

Minimum a následník

Uvedieme teraz dve funkcie, ktoré sa zídu pri mazaní prvku zo stromu, ale môžu sa zísť aj inokedy.

Prvá funkcia minNode nájde vo vyhľadávacom strome uzol, v ktorom je uložená najmenšia hodnota.

• Všetky prvky menšie ako koreň sú v ľavom podstrome, bude tam zrejme aj minimum.
• Tá istá úvaha platí pre koreň ľavého podstromu.
• Ideme teda doľava kým sa dá, posledný vrchol vrátime (list alebo vrchol, ktorý má iba pravé dieťa).
• Nie je treba teda prechádzať celý strom a nemusíme sa ani pozerať na položku data v uzloch.
• Dá sa napísať cyklom aj rekurzívne.
• Obalom pre používateľa bude funkcia bstMin, ktorá pomocou funkcie minNode nájde minimálny kľúč v danom binárnom vyhľadávacom strome t.

/* Vrati uzol s minimalnou hodnotou data v podstrome s korenom v. */
node *minNode(node *v) {
    assert(v != NULL);
    while (v->left != NULL) {
        v = v->left;
    }
    return v;
}

/* Vrati minimalnu hodnotu v mnozine s. */
int min(set &s) {
    assert(s.root != NULL);
    return minNode(s.root)->data; 
}

Cvičenia:

• Napíšte rekurzívny variant funkcie minNode.
• Ako by bolo treba funkciu zmeniť, aby hľadala maximum?

Funkcia successorNode nájde pre daný uzol v jeho následníka (angl. successor) v binárnom vyhľadávacom strome, čiže uzol, ktorý vo vzostupnom poradí podľa kľúčov nasleduje bezprostredne za uzlom v.

• Ak má uzol v pravé dieťa, následník uzla v bude vrchol s minimálnou hodnotou data v pravom podstrome
• V opačnom prípade môže byť následníkom uzla v jeho rodič, ak v je jeho ľavé dieťa.
• Ak je v pravým dieťaťom svojho rodiča, môže to byť jeho prarodič (ak je rodič uzla v ľavým dieťaťom tohto prarodiča), atď.
• Vo všeobecnosti teda ide o najbližšieho predka uzla v takého, že v patrí do jeho ľavého podstromu.
• V strome existuje práve jeden uzol bez následníka (najväčší prvok).
  • Ako presne sa bude funkcia nižšie pre tento prvok správať?

/* Vrati uzol, ktory vo vzostupnom poradi uzlov podla 
 * klucov nasleduje za v. 
 * Ak taky uzol neexistuje, vrati NULL. */
node *successorNode(node *v) {
    assert(v != NULL);
    if (v->right != NULL) {
        return minNode(v->right);
    }
    while (v->parent != NULL && v == v->parent->right) {
        v = v->parent;
    }
    return v->parent;
}

Mazanie z binárneho vyhľadávacieho stromu

Nasledujúca funkcia remove zmaže z binárneho vyhľadávacieho stromu uzol s kľúčom key (ak sa taký uzol v strome vyskytuje).

• Najprv pomocou funkcie findNode nájde uzol v s kľúčom key.
• Ak je v list, jednoducho ho zmažeme.
• Ak má v jedno dieťa, toto dieťa prevesíme priamo pod rodiča v a v zmažeme.
• Ak má v dve deti, nájdeme nasledovníka v, t.j. minimum v pravom podstrome v.
• Tento nasledovník nemá ľavé dieťa, vieme ho teda zmazať.
• Jeho údaje presunieme do vrcholu v.
• Tiež treba dať pozor na mazanie koreňa.

/* Zmaze zo stromu pre mnozinu s uzol s klucom key, ak tam taky je. */
void remove(set &s, int key) {
    // Najde uzol s hodnotou, ktoru treba vymazat.
    node *v = findNode(s.root, key);                   
    if (v == NULL) {
        // pozadovany uzol neexistuje
        return;
    }
    
    // Najde uzol *rm, ktory sa napokon realne zmaze.   
    node *rm;                                          
    if (v->left == NULL || v->right == NULL) {         
        rm = v;
    } else  {
        rm = successorNode(v);
    }
   
    // Ak rm != v, presunie kluc uzla *rm do uzla *v. 
    if (rm != v) {                                     
        v->data = rm->data;
    }
    
    // ak ma uzol rm dieta, jeho rodicom bude rodic rm
    node *child;                                      
    if (rm->left != NULL) {
        child = rm->left;
    } else {
        child = rm->right;
    }
    if (child != NULL) {
        child->parent = rm->parent;
    }
    if (rm->parent == NULL) {
        s.root = child;
    } else if (rm == rm->parent->left) {
        rm->parent->left = child;    
    } else if (rm == rm->parent->right) {
        rm->parent->right = child;
    }
    // rm uz nie je v strome, uvolnime jeho pamat
    delete rm;
}

Zložitosť jednotlivých operácií

• Časová zložitosť operácií contains, add aj remove je úmerná výške stromu, ktorú označíme h.
• Minule sme ukázali, že pre strom s n uzlami máme log₂(n+1)-1 ≤ h ≤ n-1.
• Zložitosť uvedených operácií je teda v najhoršom prípade lineárna od počtu uzlov stromu (tento prípad nastane, ak prvky vkladáme od najmenšieho po najväčší alebo naopak).
• Dá sa však ukázať, že ak sa prvky vkladajú v náhodnom poradí, výška stromu bude v priemere logaritmická od počtu uzlov.
• Na predmete Algoritmy a dátové štruktúry (druhý ročník) sa tieto tvrdenia dokazujú poriadne a preberajú sa tam aj varianty vyhľadávacích stromov, pre ktoré je zložitosť uvedených operácií logaritmická aj v najhoršom prípade.