Prednáška 22

Zložitosť operácií na prácu s binárnymi vyhľadávacími stromami

• Časová zložitosť operácií bstFind(t), bstInsert(t) aj bstRemove(t) je úmerná hodnote height(t), čo je výška stromu t.
• Predminule sme ukázali, že pre výšku h stromu s n vrcholmi je 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 v priemernom prípade je ich zložitosť rádovo 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.

Lexikografické stromy

Lexikografický strom reprezentujúci množinu reťazcov a, aj, ale, aleba, alebo, cez, na, nad.

Lexikografické stromy (niekde tiež prefixové stromy; angl. trie zo slova retrieval) sú dátová štruktúra na uchovávanie množiny reťazcov. Ide o stromy, ktoré nemusia byť binárne:

• Každý uzol lexikografického stromu má najviac toľko synov, koľko je písmen v uvažovanej abecede. Každý zo synov zodpovedá práve jednému písmenu abecedy a každému písmenu abecedy zodpovedá najviac jeden syn daného uzla. Graficky možno písmená zodpovedajúce jednotlivým synom znázorniť ohodnotením hrán spájajúcich dané uzly.
• Koreň lexikografického stromu zodpovedá prázdnemu reťazcu.
• Uzol v hĺbke k zodpovedá reťazcu dĺžky k, ktorý dostaneme prečítaním písmen na ceste z koreňa do daného uzla.
• Každý uzol lexikografického stromu obsahuje informáciu (true alebo false) o tom, či k nemu prislúchajúci reťazec patrí do množiny reprezentovanej týmto lexikografickým stromom alebo nie.
• V korektnom lexikografickom strome všetky listy zodpovedajú reťazcom z reprezentovanej množiny; niektoré reťazce reprezentovanej množiny však môžu zodpovedať aj vnútorným vrcholom stromu. Každý uzol lexikografického stromu tak zodpovedá nejakému prefixu slova z ním reprezentovanej množiny – odtiaľ alternatívne pomenovanie prefixový strom.

Štruktúra node pre uzol lexikografického stromu tak obsahuje booleovskú premennú isWord, v ktorej je uložená informácia o tom, či reťazec prislúchajúci k danému uzlu patrí alebo nepatrí do reprezentovanej množiny a pole children smerníkov na jednotlivých synov daného uzla. Veľkosť alphSize tohto poľa je rovná veľkosti uvažovanej abecedy – pre písmená malej anglickej abecedy je táto hodnota rovná 'z' - 'a' + 1.

Pri rôznych praktických aplikáciách môže štruktúra node obsahovať aj rozličné ďalšie informácie – pre každé slovo z reprezentovanej množiny si napríklad môžeme pamätať jeho frekvenciu výskytu, preklad do nejakého iného jazyka a podobne.

const int alphSize = 'z' - 'a' + 1;

struct node {
    node *children[alphSize]; // pole smernikov na deti
    bool isWord;              // udava, ci uzol prislucha k slovu z reprezentovanej mnoziny
    // dalsie data (napriklad preklad slova, pocet vyskytov slova v texte, ...)
};

Samotný lexikografický strom je potom daný iba smerníkom na svoj koreň:

struct trie {
    node *root;      
};

Inicializácia lexikografického stromu

Nasledujúca funkcia inicializuje prázdny lexikografický strom t:

void trieInit(trie &t) {
    t.root = NULL; 
}

Likvidácia lexikografického stromu

Uvoľnenie pamäte alokovanej pre podstrom zakorenený v uzle root realizujeme obdobne ako pri binárnych vyhľadávacích stromoch. Jediný rozdiel spočíva v potenciálne väčšom počte synov uzla root.

void destroySubtree(node *root) {
    if (root != NULL) {
        for (int i = 0; i <= alphSize - 1; i++) {
            destroySubtree(root->children[i]);
        }
        delete root;
    }
}

Nasledujúca funkcia potom zlikviduje celý lexikografický strom t:

void trieDestroy(trie &t) {
    destroySubtree(t.root);
}

Vkladanie do lexikografického stromu

Pri vkladaní reťazca do množiny realizovanej lexikografickým stromom často vznikne potreba vytvárať nové uzly tohto stromu. Túto podúlohu realizuje funkcia createNode, ktorá vytvorí nový uzol s hodnotou isWord danou jej argumentom a so všetkými smerníkmi na synov rovnými NULL.

node *createNode(bool isWord) {
    node *v = new node;
    for (int i = 0; i <= alphSize - 1; i++) {
        v->children[i] = NULL;
    }
    v->isWord = isWord;
    return v;
}

Vloženie reťazca word do lexikografického stromu t potom realizuje funkcia trieInsert, ktorá pracuje nasledovne:

• Začne v koreni stromu, odkiaľ postupuje nižšie smerom k listom.
• V každom uzle sa pozrie na ďalšie písmeno slova word. Ak danému uzlu chýba syn pre toto písmeno, vytvorí ho pomocou funkcie createNode. Následne sa presunie do tohto syna.
• Ak v nejakom uzle v príde na koniec slova word, nastaví hodnotu v->isWord na true.

void trieInsert(trie &t, const char *word) {
    if (t.root == NULL) {
        t.root = createNode(false);
    }
    node *v = t.root;
    for (int i = 0; word[i] != 0; i++) {
        int c = word[i] - 'a';
        if (v->children[c] == NULL) {
            v->children[c] = createNode(false);
        }
        v = v->children[c];
    }
    v->isWord = true;
}

Hľadanie v lexikografickom strome

Funkcia treeFind pre daný lexikografický strom t a reťazec word zistí, či slovo word patrí do množiny reprezentovanej stromom t. Opäť pritom postupuje po písmenách reťazca word. Kým nedôjde na koniec slova, snaží sa ísť po hranách, ktoré zodpovedajú jednotlivým písmenám. V prípade, že v niektorom bode narazí na NULL, slovo word sa v strome nenachádza. V opačnom prípade toto slovo dočíta v nejakom uzle v. V takom prípade slovo word patrí do reprezentovanej množiny práve vtedy, keď v->isWord má hodnotu true.

bool trieFind(trie &t, const char *word) {
    node *v = t.root;
    if (v == NULL) {
        return false;
    }
    for (int i = 0; word[i] != 0; i++) {
        v = v->children[word[i] - 'a'];
        if (v == NULL) {
            return false;
        }
    }
    return v->isWord;
}

Vymazávanie z lexikografického stromu

Vymazávanie slov z množiny reprezentovanej lexikografickým stromom budeme realizovať prostredníctvom pomocnej rekurzívnej funkcie removeFromSubtree, ktorá z podstromu zakorenenom v uzle *root vymaže sufix reťazca word začínajúci na pozícii index. Táto funkcia vráti na výstupe booleovskú hodnotu podľa toho, či sa pri tomto vymazaní sufixu z daného podstromu vymazal jeho koreň *root (táto situácia nenastane vždy: napríklad pri mazaní slova a z podstromu reprezentujúceho množinu slov {a,ab} uzol prislúchajúci k reťazcu a v strome ostáva; zmení sa len jeho hodnota isWord).

Ak sa slovo word v reprezentovanej množine nenachádza, funkcia removeFromSubtree vyhlási chybu pomocou funkcie assert.

Funkcia removeFromSubtree pracuje nasledovne:

• Ak je sufix reťazca word začínajúci na indexe index prázdny, nastaví hodnotu root->isWord na false.
• V opačnom prípade funkcia removeFromSubtree zavolá rekurzívne samú seba pre syna zodpovedajúceho písmenu na pozícii index reťazca word. Ak toto volanie daného syna zmaže, prestaví smerník na tohto syna na NULL.
• V prípade, že po vykonaní jednej z predchádzajúcich dvoch operácií nemá uzol root žiadneho syna a súčasne má root->isWord hodnotu false, uvoľní pamäť alokovanú pre uzol root a informáciu o jeho zmazaní vráti na výstupe.

bool removeFromSubtree(node *root, const char *word, int index) {
    assert(root != NULL);
    if (word[index] == 0) {
        assert(root->isWord);
        root->isWord = false;
    } else {
        int c = word[index] - 'a';
        bool deleted = removeFromSubtree(root->children[c], word, index + 1);
        if (deleted) {          
            root->children[c] = NULL;
        }
    }
    int numChildren = 0;                        
    for (int i = 0; i <= alphSize - 1; i++) {
        if (root->children[i] != NULL) {
            numChildren++;
        }
    }
    if (numChildren == 0 && !root->isWord) {
        delete root;
        return true;
    }
    return false;
}

Samotné odstránenie reťazca word z množiny reprezentovanej stromom t potom realizuje nasledujúca funkcia trieRemove. Tá len zavolá funkciu removeFromSubtree pre koreň stromu t a v prípade, že volanie tejto funkcie koreň zo stromu odstráni, nastaví t.root na NULL.

void trieRemove(trie &t, const char *word) {
    bool rootRemoved = removeFromSubtree(t.root, word, 0);
    if (rootRemoved) {
        t.root = NULL;
    }
}

Výška lexikografického stromu

Nasledujúca funkcia vypočíta výšku podstromu zakoreneného v uzle *root (definovaná je rovnako ako pre binárne stromy):

int subtreeHeight(node *root) {
    if (root == NULL) {
        return -1;
    }
    int maxHeight = -1;
    for (int i = 0; i <= alphSize - 1; i++) {
        int height = subtreeHeight(root->children[i]);
        if (height > maxHeight) {
            maxHeight = height;
        }
    }
    return maxHeight + 1;
}

Výšku samotného lexikografického stromu t potom spočíta nasledujúca funkcia:

int trieHeight(trie &t) {
    return subtreeHeight(t.root);
}

Vypisovanie slov reprezentovaných lexikografickým stromom

Nasledujúca funkcia printSubtree prehľadáva podstrom zakorenený v uzle *root a v reťazci s postupne generuje všetky slová z reprezentovanej množiny, ktoré zároveň vypisuje na konzolu.

void printSubtree(node *root, char *s, int index) {
    if (root == NULL) {
        return;
    }
    if (root->isWord) {
        s[index] = 0;
        printf("%s\n", s);
    }
    for (int i = 0; i <= alphSize - 1; i++) {
        s[index] = 'a' + i;
        printSubtree(root->children[i], s, index + 1);
    }
}

Funkcia triePrint vypisujúca všetky slová v množine reprezentovanej lexikografickým stromom t najprv spočíta výšku stromu t, ktorá je rovná dĺžke najdlšieho reťazca tejto množiny. Následne dynamicky alokuje reťazec dostatočnej dĺžky na uchovanie každého slova množiny a zavolá funkciu printSubtree pre koreň stromu t.

void triePrint(trie &t) {
    int height = trieHeight(t);
    if (height >= 0) { 
        char *s = new char[height + 1];
        printSubtree(t.root, s, 0);
        delete[] s;
    }
}

Program pracujúci s lexikografickými stromami

Nasledujúci program načítava z konzoly príkazy zodpovedajúce operáciám na lexikografickom strome a za každým načítaným príkazom túto operáciu vykonáva.

#include <cstdio>
#include <cassert>
#include <cstring>
using namespace std;


// ...


int main(void) {
    trie t;
    trieInit(t);
    char command[20];
    char arg[20];
    while (true) {
        scanf("%19s", command);
        if (strcmp(command, "insert") == 0) {
            scanf("%19s", arg);
            trieInsert(t, arg);
        }
        if (strcmp(command, "find") == 0) {
            scanf("%19s", arg);
            bool b = trieFind(t, arg);
            if (b) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
        if (strcmp(command, "remove") == 0) {
            scanf("%19s", arg);
            trieRemove(t, arg);
        }
        if (strcmp(command, "height") == 0) {
            printf("%d\n", trieHeight(t));
        }
        if (strcmp(command, "print") == 0) {
            triePrint(t);
        }
        if (strcmp(command, "exit") == 0) {
            break;
        }
    }
    trieDestroy(t);
    return 0;
}