Prednáška 21

Oznamy

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

• Dnes informácia o skúškach, detaily skúšky z programovania, pokračujeme v učive o stromoch
• Tento piatok 10.12. cez cvičenia semestrálny test.
• V pondelok 13.12. bude bežná prednáška, pokračujú stromy.
• V stredu 15.12. dokončíme stromy, potom 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 14.12. v rámci cvičení tréning na skúšku.
  • Už dnes po prednáške sa na testovači objavia tréningové príklady na skúšku. Za niektoré budete môcť získať bonusový bod, ak ich vyriešite do 12.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 piatok 17.12. od 12:00 predtermín skúšky, doplnkové cvičenia nebudú

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 množina (set)

• operácie init, find, insert, remove
• implementácie pomocou
  • neutriedeného poľa
  • utriedeného poľa
  • spájaných zoznamov
  • binárnych vyhľadávacích stromov
  • hešovacej tabuľky
  • lexikografické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;
    item* next;
};
struct linkedList {
    item* first;
};
void insertFirst(linkedList &z, int d){
    /* do zoznamu z vlozi na zaciatok novy prvok s datami d */
    item* p = new item;   // vytvoríme nový prvok
    p->data = d;          // naplníme dáta
    p->next = z.first;    // prvok bude prvým prvkom zoznamu (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;  /* lavy syn */
    node * right; /* pravy syn */
};

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

Lexikografické stromy

• ukladajú množinu reťazcov
• nie sú binárne: vrchol môže mať veľa synov
• 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 {
    /* vrchol lexikografickeho stromu  */
    char data; // pismeno ulozene v tomto vrchole
    bool isWord; // je tento vrchol koncom slova?
    node* next[Abeceda]; // pole smernikov na deti    
};

Hešovanie

• hešovacia tabuľka veľkosti m
• kľúč k premietneme nejakou funkciou na index v poli (0,...,m-1}
• každé políčko hešovacej tabuľky spájaný zoznam prvkov, ktoré sa tam zaheš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á hešovacia funkcia, v praxi väčšinou zložitejšie
    return abs(k) % m;
}
struct node {
    int item;
    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

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 */
    node * left;    /* ľavé dieťa */
    node * right;   /* pravé dieťa */
};

struct binarySearchTree {
    node *root;  /* koreň stromu, NULL pre prázdny strom */
};

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

Definícia štruktúr pre binárny vyhľadávací strom a jeho uzol

Štruktúra node pre uzol binárneho vyhľadávacieho stromu bude veľmi podobná, ako pri všeobecných binárnych stromoch. Spomedzi dát uložených v uzle je najpodstatnejší kľúč key, pričom na tejto prednáške sa obmedzíme na celočíselné kľúče. Okrem kľúča môžu byť v uzle uložené aj ďalšie, tzv. satelitné, dáta – tie však pre jednoduchosť uvažovať nebudeme. Okrem smerníkov na ľavého a pravého syna bude navyše každý uzol obsahovať aj smerník na svojho otca (v prípade koreňa bude mať hodnotu NULL).

Na binárny vyhľadávací strom kladieme globálne podmienky ohľadom kľúčov jeho uzlov. V prípade „ručnej” manipulácie s jeho uzlami by mohlo dôjsť k narušeniu platnosti týchto podmienok (napríklad by sme mohli niektorému ľavému synovi priradiť väčší kľúč, než má jeho otec). Aby sme predišli takýmto problémom, definujeme okrem štruktúry node pre jednotlivé uzly aj štruktúru binarySearchTree realizujúcu „obal” pre celý binárny vyhľadávací strom. Následne definujeme niekoľko funkcií na prácu s binárnymi vyhľadávacími stromami prostredníctvom štruktúry binarySearchTree. Používateľ, ktorý bude na prácu s binárnymi vyhľadávacími stromami používať výhradne tieto funkcie, by nikdy nemal mať možnosť porušiť podmienky platné v binárnych vyhľadávacích stromoch.

/* Uzol binarneho vyhladavacieho stromu. */
struct node {
    int key;       // kluc, podla ktoreho budeme porovnavat prvky (namiesto int aj ina uplne usporiadana mnozina) 
    
    /* Sem mozu prist lubovolne dalsie satelitne data ulozene v danom uzle. */
    
    node *parent;  // smernik na otca (NULL, ak neexistuje)
    node *left;    // smernik na laveho syna (NULL, ak tento syn neexistuje)
    node *right;   // smernik na praveho syna (NULL, ak tento syn neexistuje)
};


// ...


/* Samotna struktura binarneho vyhladavacieho stromu (obal pre pouzivatela). */
struct binarySearchTree {
    node *root;
};

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

Nasledujúca funkcia realizuje inicializáciu binárneho vyhľadávacieho stromu t.

/* Inicializuje prazdny binarny vyhladavaci 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 „baliacu” 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

Nasledujúca funkcia findNode sa pokúsi v podstrome zakorenenom v uzle *root vyhľadať uzol, ktorého kľúč je rovný key. Ak existuje aspoň jeden taký uzol, vráti smerník na niektorý z nich (to je užitočné najmä v prípade, keď sú kľúče po dvoch rôzne). V opačnom prípade vráti NULL.

Pri hľadaní uzla s hodnotou key bude funkcia findNode využívať definujúcu vlastnosť binárnych vyhľadávacích stromov: ak je hľadaná hodnota kľúča key menšia, než kľúč koreňa podstromu *root, pokračuje v hľadaní v jeho ľavom podstrome; ak je naopak väčšia, pokračuje v hľadaní v jeho pravom podstrome. Ak je kľúč koreňa *root rovný key, ide o hľadaný uzol a smerník naň tak možno ihneď vrátiť na výstupe.

Používateľovi pritom opäť poskytneme aj „baliacu” funkciu bstFind, ktorá 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) {
    if (root == NULL || root->key == key) {
        return root;
    } else if (key < root->key) {
        return findNode(root->left, key);
    } else {
        return findNode(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. Poznamenajme ešte, že funkciu findNode je možné realizovať aj nerekurzívne, napríklad takto:

node *findNode(node *root, int key) {
    node *v = root;
    while (v != NULL && v->key != key) {
        if (key < v->key) {
            v = v->left;
        } else {
            v = v->right;
        }
    }
    return v;
}

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. Postupuje pritom rekurzívne: ak zistí, že uzol *v má kľúč menší, než *root, pokúsi sa ho vložiť do ľavého podstromu uzla *root; v opačnom prípade sa ho pokúsi vložiť do pravého podstromu.

Používateľovi následne poskytneme „baliacu” funkciu bstInsert, ktorá vytvorí uzol s daným kľúčom key a pomocou funkcie insertNode ho vloží do binárneho vyhľadávacieho stromu t.

/* Vlozi uzol *v na spravne miesto podstromu zakoreneneho v *root */
void insertNode(node *root, node *v) {
    assert(root != NULL && v != NULL);
    if (v->key < root->key) {
        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);
        }
    }
}


// ...


/* Vlozi do stromu t novy uzol s klucom key. */
void bstInsert(binarySearchTree &t, int key) {
    node *v = new node;
    v->key = key;
    v->left = NULL;
    v->right = NULL;
    v->parent = NULL;
    if (t.root == NULL) {
        t.root = v;
    } else {
        insertNode(t.root, v);
    }
}

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

Cvičenie č. 1: napíšte nerekurzívny variant funkcie insertNode.

Cvičenie č. 2: napíšte funkciu treeSort, ktorá z poľa celých čísel a pomocou volaní funkcie bstInsert vytvorí binárny vyhľadávací strom a následne pomocou prehľadávania tohto stromu v poradí inorder pole a utriedi.

Minimálny uzol

Nasledujúca funkcia minNode nájde v podstrome zakorenenom v *root uzol s minimálnym kľúčom. Je pritom založená na skutočnosti, že všetky uzly tohto podstromu s kľúčom menším ako root->key sa musia nachádzať v ľavom podstrome uzla *root.

„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 (niektory) uzol s minimalnou hodnotou key v podstrome s korenom *root. */
node *minNode(node *root) {
    assert(root != NULL);
    if (root->left != NULL) {
        return minNode(root->left);
    } else {
        return root;
    }
}


// ...


/* Vrati minimalny kluc uzla v strome t. */
int bstMin(binarySearchTree &t) {
    assert(t.root != NULL);
    return minNode(t.root)->key; 
}

Cvičenie: napíšte nerekurzívny variant funkcie minNode.

Následník uzla

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. Je pritom založená na nasledujúcich pozorovaniach:

• Ak má uzol *v pravého syna, následník uzla *v musí byť v jeho pravom podstrome – konkrétne pôjde o minimálny uzol z tohto podstromu.
• V opačnom prípade môže byť následníkom uzla *v jeho otec (ak *v je jeho ľavý syn). Ak je *v pravým synom svojho otca, môže to byť aj jeho starý otec (ak je otec uzla *v ľavým synom tohto starého otca), 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 (jeden spomedzi najväčších prvkov).

/* 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 bstRemove zmaže z binárneho vyhľadávacieho stromu t práve jeden uzol s kľúčom key (ak sa taký uzol v strome vyskytuje). Pracuje tak, že najprv pomocou funkcie findNode nájde uzol *v s kľúčom key. V prípade úspechu zistí počet synov uzla *v. Ak totiž *v nemá žiadneho syna alebo má len jedného syna, možno ho zo stromu t zmazať jednoducho tak, že sa prípadný syn uzla *v stane synom otca uzla *v. V prípade, že má *v dvoch synov je však zrejmé, že jeho následník sa musí nachádzať v jeho neprázdnom pravom podstrome. Tento následník *rm navyše nemôže mať ľavého syna. Odstránenie kľúča key je teda možné realizovať tak, že sa kľúč uzla *rm presunie do uzla *v a následne sa odstráni uzol *rm tak, ako je popísané vyššie.

/* Zmaze zo stromu t prave jeden uzol s klucom key (ak tam taky je). */
void bstRemove(binarySearchTree &t, int key) {
    node *v = findNode(t.root, key);                   // Najde uzol v s hodnotou, ktoru treba vymazat.
    if (v == NULL) {
        return;
    }
    
    node *rm;                                          // Najde uzol *rm stromu t, ktory sa napokon realne zmaze.   
    if (v->left == NULL || v->right == NULL) {         
        rm = v;
    } else  {
        rm = successorNode(v);
    }
   
    if (rm != v) {                                     // Ak rm != v, presunie kluc uzla *rm do uzla *v. 
        v->key = rm->key;
    }
    
    node *child;                                       // Zmaze uzol *rm a uvolni pamat alokovanu pre tento uzol.
    if (rm->left != NULL) {
        child = rm->left;
    } else {
        child = rm->right;
    }                   
    if (child != NULL) {
        child->parent = rm->parent;
    }
    if (rm->parent == NULL) {
        t.root = child;
    } else if (rm == rm->parent->left) {
        rm->parent->left = child;    
    } else if (rm == rm->parent->right) {
        rm->parent->right = child;
    }
    delete rm;
}

Zložitosť jednotlivých operácií

• Časová zložitosť operácií bstFind(t), bstInsert(t) aj bstRemove(t) je úmerná hodnote height(t), čo je výška stromu t.
• Minule 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.

Príklad programu pracujúceho s binárnymi vyhľadávacími stromami

Nasledujúci program realizuje základné operácie s binárnymi vyhľadávacími stromami podľa príkazov zadávaných používateľom na konzolu.

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


// ...


int main(void) {
    binarySearchTree t;
    bstInit(t);
    char command[20];
    int key;
    while (true) {
        scanf("%19s", command);
        if (strcmp(command, "insert") == 0) {
            scanf("%d", &key);
            bstInsert(t, key);
        }
        if (strcmp(command, "remove") == 0) {
            scanf("%d", &key);
            bstRemove(t, key);
        }
        if (strcmp(command, "find") == 0) {
            scanf("%d", &key);
            bool b = bstFind(t, key);
            if (b) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
        if (strcmp(command, "min") == 0) {
            printf("%d\n", bstMin(t));
        }
        if (strcmp(command, "exit") == 0) {
            break;
        }
    }
    bstDestroy(t);                     
    return 0;
}