Programovanie (1) v C/C++
1-INF-127, ZS 2024/25

Úvod · Pravidlá · Prednášky · Softvér · Testovač
· Kontaktujte nás pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Prosíme študentov, aby si pravidelne čítali e-maily na @uniba.sk adrese alebo aby si tieto emaily preposielali na adresu, ktorú pravidelne čítajú.
· Test pre pokročilých bude v piatok 27.9. o 13:10 v posluchárni A (pracovať budete na papieri, bez počítača). Ako prípravu si môžete pozrieť ukážky príkladov z archívu predmetu a ukážkový test. Na test si môžete priniesť ťahák v rozsahu jedného listu (dvoch strán) A4. V prípade záujmu o test sa prihláste do stredy 25.9. obeda na testovači (heslo na testovač dostanete v pondelok poobede). Ak chcete na test prísť a máte s týmto časom konflikt, dajte nám vedieť čím skôr.
· Tento piatok o 13:10 budú doplnkové cvičenia nepovinné. Príďte ak máte otázky ohľadom softvéru na notebookoch alebo ohľadom úloh z cvičení 1.


Prednáška 21: Rozdiel medzi revíziami

Z Programovanie
Skočit na navigaci Skočit na vyhledávání
Riadok 1: Riadok 1:
 
== Oznamy ==
 
== Oznamy ==
  
 +
<!--
 
Plán prednášok a cvičení na zvyšok semestra:
 
Plán prednášok a cvičení na zvyšok semestra:
 
* Dnes informácia o skúškach, [[Zimný semester, skúška|detaily skúšky z programovania]], pokračujeme v učive o stromoch
 
* Dnes informácia o skúškach, [[Zimný semester, skúška|detaily skúšky z programovania]], pokračujeme v učive o stromoch
Riadok 9: Riadok 10:
 
** 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ť.
 
** 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ú
 
* V piatok 17.12. od 12:00 predtermín skúšky, doplnkové cvičenia nebudú
 +
-->
  
 
== Binárne vyhľadávacie stromy ==
 
== Binárne vyhľadávacie stromy ==

Verzia zo dňa a času 16:05, 1. december 2022

Oznamy

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.