Prednáška 22

Oznamy

Plán prednášok a cvičení na zvyšok semestra:

• Dnes informácie k skúške a posledná ukážka stromov
• Zahraniční študenti: ak máte záujem o preklad zadaní skúšky a testu na tomto predmete, nezabudnite to do piatka 9.12. nahlásiť pomocou formulára
• V piatok posledné doplnkové cvičenia
• V pondelok 12.12. nepovinná prednáška o nepreberaných črtách jazykov C a C++ (táto nepovinná časť učiva nebude vyžadovaná na skúške, ale môžete ju použiť).
• V utorok 13.12. v rámci cvičení tréning na skúšku.
  • Na testovači už sú tréningové príklady na skúšku, jeden pribudne dnes týkajúci sa dnešného učiva. Za niektoré budete môcť získať bonusový bod, ak ich vyriešite do 8.1. (ako tréning sa dajú riešiť aj neskôr). V utorok na cvičeniach pribudne ešte jeden tréningový príklad za 4 body. Ak prídete na cvičenia a odovzdáte na konci aspoň rozumne rozrobenú verziu programu, získate jeden bonusový bod, aj keď ho nestihnete dokončiť.
• V stredu 14.12. cez prednášku semestrálny test
• V piatok 16.12. od 13:10 predtermín skúšky, doplnkové cvičenia nebudú

Prefixové stromy

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

Prefixové stromy (niekde tiež lexikografické 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:

• Uzol prefixového stromu má najviac toľko detí, koľko je znakov v uvažovanej abecede. Každé dieťa je označené iným znakom abecedy. Graficky si môžeme predstaviť tento znak prislúchajúci k hrane spájajúcej rodiča a dieťa.
• Koreň prefixové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 prefixového stromu obsahuje logickú hodnotu vyjadrujúcu, či k nemu prislúchajúci reťazec patrí do množiny reprezentovanej týmto prefixovým stromom.
• V korektnom prefixovom strome všetky listy zodpovedajú reťazcom z reprezentovanej množiny.
• Vnútorné vrcholy môžu zodpovedať reťazcu z množiny alebo iba prefixu jedného alebo viacerých takých reťazcov.

Uzly prefixového stromu budeme reprezentovať štruktúrou node

• Uzol obsahuje 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é deti daného uzla.
• Veľkosť alphSize tohto poľa je rovná veľkosti uvažovanej abecedy.
• V ukážkovom programe uvažujeme abecedu 'a'..'z'.

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

struct node {
    // pole smernikov na deti
    node *children[alphSize]; 
    // udava, ci uzol prislucha k slovu z reprezentovanej mnoziny 
    bool isWord;              
};

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

struct trie {
    node *root;      
};

Inicializácia a likvidácia prefixového stromu

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

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

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 detí uzla root.

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

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

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

Hľadanie v prefixovom strome

Funkcia contains pre daný prefixový strom t a reťazec word zistí, či slovo word patrí do množiny reprezentovanej stromom t.

• 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 contains(trie &t, const char *word) {
    node *v = t.root;
    if (v == NULL) {
        return false;
    }
    for (int i = 0; word[i] != 0; i++) {
        int c = word[i] - 'a';
        assert(c >= 0 && c < alphSize);
        v = v->children[c];
        if (v == NULL) {
            return false;
        }
    }
    return v->isWord;
}

Vkladanie do prefixového stromu

Pri vkladaní reťazca do množiny reprezentovanej prefixovým stromom potrebujeme vytvárať nové uzly. 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 deti nastavenými na NULL.

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

Vloženie reťazca word do prefixového stromu t vykoná funkcia add, 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 dieťa pre toto písmeno, vytvorí ho pomocou funkcie createNode. Následne sa presunie do tohto dieťaťa.
• Keď v nejakom uzle v príde na koniec slova word, nastaví hodnotu v->isWord na true.

void add(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';
        assert(c >= 0 && c < alphSize);
        if (v->children[c] == NULL) {
            v->children[c] = createNode(false);
        }
        v = v->children[c];
    }
    v->isWord = true;
}

Vymazanie slova z prefixového stromu

Vymazávanie slov z množiny reprezentovanej prefixovým stromom budeme realizovať prostredníctvom pomocnej rekurzívnej funkcie removeFromSubtree.

• Funkcia z podstromu zakorenenom v uzle root vymaže sufix reťazca word začínajúci na pozícii index.
• Funkcia vráti booleovskú hodnotu podľa toho, či sa pri tomto vymazaní sufixu z daného podstromu vymazal jeho koreň root.
• 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 dieťa zodpovedajúce písmenu na pozícii index reťazca word. Ak toto volanie dané dieťa zmaže, prestaví smerník na toto dieťa na NULL.
• V prípade, že po vykonaní jednej z predchádzajúcich dvoch operácií nemá uzol root žiadne dieťa 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.

Cvičenie: hoci mazanie neprehľadáva celý strom, iba jednu cestu z koreňa smerom dolu, naprogramovali sme ju rekurzívne. Na aký problén by sme narazili, ak by sme ju chceli naprogramovať cyklom? Pomohli by nám smerníky na rodiča v uzloch stromu?

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; i++) {
        if (root->children[i] != NULL) {
            numChildren++;
        }
    }
    if (numChildren == 0 && !root->isWord) {
        delete root;
        return true;
    } else {
        return false;
    }
}

Samotné odstránenie reťazca word z množiny reprezentovanej stromom t potom realizuje funkcia remove.

void remove(trie &t, const char *word) {
    // zavolame rekurziu pre koren stromu
    bool rootRemoved = removeFromSubtree(t.root, word, 0);
    // ak bol koren odstraneny, nastavime t.root na NULL
    if (rootRemoved) {
        t.root = NULL;
    }
}

Výška prefixového stromu

Nasledujúca funkcia vypočíta výšku podstromu zakoreneného v uzle root:

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

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

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

Vypisovanie slov reprezentovaných prefixový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. V parametri index dostane hĺbku aktuálneho vrcholu, t.j. pozíciu v reťazci, na ktorú pridáme ďalší znak.

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

Funkcia printAll vypisujúca všetky slová v množine reprezentovanej prefixový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 printAll(trie &t) {
    int height = height(t);
    if (height >= 0) { 
        char *s = new char[height + 1];
        printSubtree(t.root, s, 0);
        delete[] s;
    }
}

V akom poradí budú slová vypísané?

Ukážka programu s prefixovým stromom, ADT slovník

Na vstupe máme text pozostávajúci zo slov s malými písmenami a pre každé slovo v texte chceme spočítať, koľkokrát sa tam nachádza.

• Jednotlivé slová uložíme pomocou prefixového stromu a v každom uzle si pamätáme namiesto hodnoty isWord počítadlo count, ktoré udáva, koľkokrát sme príslušné slovo videli na vstupe.
• Počítadlo má hodnotu nula pre prefixy vstupných slov, ktoré samé zatiaľ ako slovo na vstupe neboli.
• Namiesto funkcie treeInsert máme funkciu treeIncrement, ktorá dostane slovo a zvýši jeho počítadlo, pričom ak slovo zatiaľ v strome nebolo, tak ho pridá.
• Podobne by sme na tento účel vedeli upraviť aj implementáciu množiny pomocou binárneho vyhľadávacieho stromu, hašovacej tabuľky, poľa alebo zoznamu.
  • Pozor, ak sú kľúče reťazce, na ich porovnanie musíme v týchto implementáciách použiť strcmp, nie ==, < a pod.

Abstraktný dátový typ, ktorý si okrem množiny kľúčov ku každému kľúču pamätá aj ďalšie dáta, sa zvykne nazývať slovník (angl. dictionary, map).

• Tu boli kľúče slová a ďalšie dáta počet výskytov.
• Iný príklad je zoznam kontaktov, kde kľúčom je meno osoby a pre dané meno chceme vrátiť kontaktné údaje danej osoby (emailová adresa, telefón a pod.)

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

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

// uzol prefixoveho stromu
struct node {
    // pole smernikov na deti
    node *children[alphSize];
    // pocet vyskytov slova prisluchajuceho uzlu
    int count;
};

// cely prefixovy strom 
struct trie {
    node *root;
};


// inicializacia prazdneho stormu
void init(trie &t) {
    t.root = NULL;
}

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

// uvolnenie pamate celeho stromu
void destroy(trie &t) {
    destroySubtree(t.root);
}

// vytvorenie noveo uzlu bez deti a s nula vyskytmi
node *createNode() {
    node *v = new node;
    for (int i = 0; i < alphSize; i++) {
        v->children[i] = NULL;
    }
    v->count = 0;
    return v;
}

// zvysenie pocitadla pre slovo word
// ak slovo este nie je v strome, je pridane
void increment(trie &t, const char *word) {
    if (t.root == NULL) {
        t.root = createNode();
    }
    node *v = t.root;
    for (int i = 0; word[i] != 0; i++) {
        int c = word[i] - 'a';
        assert(c >= 0 && c < alphSize);
        if (v->children[c] == NULL) {
            v->children[c] = createNode();
        }
        v = v->children[c];
    }
    v->count++;
}

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

// vyska stromu. t.j. dlzka najdlsieho slova
int height(trie &t) {
    return subtreeHeight(t.root);
}

// vypisanie slov v podstrome prefixoveho stromu
void printSubtree(node *root, char *s, int index) {
    if (root == NULL) {
        return;
    }
    if (root->count > 0) {
        s[index] = 0; // ukoncenie retazca pred vypisom
        printf("%s %d\n", s, root->count);
    }
    for (int i = 0; i < alphSize; i++) {
        s[index] = 'a' + i;
        printSubtree(root->children[i], s, index + 1);
    }
}

// vypisanie slov prefixoveho stromu
void printAll(trie &t) {
    int height = height(t);
    if (height >= 0) {
        char *s = new char[height + 1];
        printSubtree(t.root, s, 0);
        delete[] s;
    }
}

int main() {
    // inicializacia stromu
    trie t;
    init(t);
    // postupne nacitavanie slov
    char word[100];
    while (true) {
        int count = scanf("%99s", word);
        if (count < 1) { // koniec vstupu
            break;
        }
	// pridanie slova resp. zvysenie pocitadla
        increment(t, word);
    }
    // vypis a uvolnenie pamate
    printAll(t);
    destroy(t);
}

Sylaby predmetu

Základy

Konštrukcie jazyka C

• premenné typov int, double, char, bool, konverzie medzi nimi
• podmienky (if, else, switch), cykly (for, while)
• funkcie (a parametre funkcií - odovzdávanie hodnotou, referenciou, smerníkom)

void f1(int x){}            //hodnotou
void f2(int &x){}           //referenciou
void f3(int* x){}           //smerníkom
void f(int a[], int n){}    //polia bez & (ostanú zmeny)
void kresli(Turtle &t){}    //korytnačky, SVGdraw a pod. s &

Polia, reťazce (char[])

int A[4]={3, 6, 8, 10}; 
int B[4];               
B[0]=3; B[1]=6; B[2]=8; B[3]=10;

char C[100] = "pes";
char D[100] = {'p', 'e', 's', 0};

• funkcie strlen, strcpy, strcmp, strcat

Súbory, spracovanie vstupu

• cin, cout alebo printf, scanf
• fopen, fclose, feof
• fprintf, fscanf
• getc, putc, ungetc, fgets, fputs
• spracovanie súboru po znakoch, po riadkoch, po číslach alebo slovách

Smerníky, dynamicky alokovaná pamäť, dvojrozmerné polia

int i;    // „klasická“ celočíselná premenná
int *p;   // ukazovateľ na celočíselnú premennú

p = &i;         // spravne
p = &(i + 3);   // zle i+3 nie je premenna
p = &15;        // zle konstanta nema adresu
i = *p;         // spravne ak p bol inicializovany

int * cislo = new int;  // alokovanie jednej premennej
*cislo = 50;
..
delete cislo;

int a[4];
int *b = a;  // a,b su teraz takmer rovnocenne premenne 

int *a = new int[n]; // alokovanie 1D pola danej dlzky
..
delete[] a;

int **a;       // alokovanie 2D matice
a = new int *[n];
for (int i = 0; i < n; i++) a[i] = new int[m];
..
for (int i = 0; i < n; i++) delete[] a[i];
delete[] a;

Abstraktné dátové typy

Abstraktný dátový typ dynamické pole (rastúce pole)

• operácie init, add, get, set, length

Abstraktný dátový typ dynamická množina (set)

• operácie init, contains, add, remove
• implementácie pomocou
  • neutriedeného poľa
  • utriedeného poľa
  • spájaných zoznamov
  • hašovacej tabuľky
  • binárnych vyhľadávacích stromov
  • prefixového stromu (ak kľúč je reťazec)

Abstraktné dátové typy rad a zásobník

• operácie pre rad (frontu, queue): init, isEmpty, enqueue, dequeue, peek
• operácie pre zásobník (stack): init, isEmpty, push, pop
• implementácie: v poli alebo v spájanom zozname
• využitie: ukladanie dát na spracovanie, odstránenie rekurzie
• kontrola zátvoriek a vyhodnocovanie výrazov pomocou zásobníka

Dátové štruktúry

Spájané zoznamy

struct node {
    int data;
    node* next;
};
struct linkedList {
    node* first;
};
void insertFirst(linkedList &z, int d){
    /* do zoznamu z vlozi na zaciatok novy prvok s datami d */
    node* p = new node;   // vytvoríme nový prvok
    p->data = d;          // naplníme dáta
    p->next = z.first;    // uzol ukazuje na doterajší začiatok
    z.first = p;          // tento prvok je novým začiatkom
}

Strom pre výraz (65 – 3*5)/(2 + 3)

Binárne stromy

struct node {
    /* vrchol stromu  */
    dataType data;
    node * left;  /* lave dieta */
    node * right; /* prave dieta */
};

node * createNode(dataType data, node *left, node *right) {
    node *v = new node;
    v->data = data;
    v->left = left;
    v->right = right;
    return v;
}

• prehľadávanie inorder, preorder, postorder
• použitie na uloženie aritmetických výrazov

Binárne vyhľadávacie stromy

• vrcholy vľavo od koreňa menší kľúč, vpravo od koreňa väčší
• insert, find, remove v čase závisiacom od hĺbky stromu

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

Prefixové stromy

• ukladajú množinu reťazcov
• nie sú binárne: vrchol môže mať veľa detí
• insert, find, remove v čase závisiacom od dĺžky kľúča, ale nie od počtu kľúčov, ktoré už sú v strome

struct node { // uzol prefixoveho stromu 
    bool isWord; // je tento uzol koncom slova?
    node* next[Abeceda]; // pole smernikov na deti    
};

Hašovanie

• hašovacia tabuľka veľkosti m
• kľúč k premietneme nejakou funkciou na index v poli (0,...,m-1}
• každé políčko hašovacej tabuľky spájaný zoznam prvkov, ktoré sa tam zahašovali
• v ideálnom prípade sa prvky rozhodia pomerne rovnomerne, zoznamy krátke, rýchle hľadanie, vkladenie, mazanie
• v najhoršom prípade všetky prvky v jednom zozname, pomalé hľadanie a mazanie

int hash(int k, int m){ // veľmi jednoduchá hašovacia funkcia, v praxi väčšinou zložitejšie
    return abs(k) % m;
}
struct node {
    int data;
    node* next;
};

struct set {
    node** data;
    int m;
};

Algoritmy

Rekurzia

• Rekurzívne funkcie
• Vykresľovanie fraktálov
• Prehľadávanie s návratom (backtracking)
• Vyfarbovanie
• Prehľadávanie stromov

Triedenia

• nerekurzívne: Bubblesort, Selectionsort, Insertsort
• rekurzívne: Mergesort, Quicksort
• súvisiace algoritmy: binárne vyhľadávanie

Matematické úlohy

• Euklidov algoritmus, Eratostenovo sito
• Práca s aritmetickými výrazmi: vyhodnocovanie postfixovej formy, prevod z infixovej do postfixovej, reprezentácia vo forme stromu