Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 21: Rozdiel medzi revíziami
(58 medziľahlých úprav od 3 ďalších používateľov nie je zobrazených) | |||
Riadok 1: | Riadok 1: | ||
== Oznamy == | == Oznamy == | ||
− | == | + | * Tretiu domácu úlohu odovzdávajte do zajtra 22:00. |
+ | |||
+ | Prednášky | ||
+ | * V stredu v prvej polovici prednášky informácie k skúške a rady k skúškovému všeobecne, potom doberieme posledné učivo | ||
+ | * Budúci pondelok nepovinná prednáška o nepreberaných črtách jazykov C a C++ | ||
+ | * Budúcu stredu 13.12. o 18:10 [[Zimný semester, semestrálny test|semestrálny test]] | ||
+ | |||
+ | Cvičenia | ||
+ | * Zajtra bude rozcvička na papieri, potom pokračujte riešením úloh na testovači | ||
+ | * Piatkové cvičenia nepovinné, avšak odporúčame účasť, ak chcete pomôcť s príkladmi alebo máte otázky | ||
+ | * Budúci utorok v rámci cvičení tréning na skúšku | ||
+ | * Na testovači už je niekoľko tréningových príkladov, za niektoré môžete dostať aj bonusový bod do cvičení, ešte dva príklady pribudnú neskôr | ||
+ | * V piatok 15.12. od 13:10 predtermín skúšky, cvičenia nebudú | ||
+ | |||
+ | <!-- | ||
+ | Začneme dokončením učiva z [[Prednáška 20#Ak.C3.A1_m.C3.B4.C5.BEe_by.C5.A5_v.C3.BD.C5.A1ka_bin.C3.A1rneho_stromu.3F |predchádzajúcej prednášky]] | ||
+ | --> | ||
+ | |||
+ | == Opakovanie: aritmetický výraz ako strom == | ||
+ | |||
+ | [[Image:PROG-P21-aritm.png|thumb|right|Strom pre výraz <tt>(65 – 3 * 5)/(2 + 3)</tt>]] | ||
+ | |||
+ | Uzol takéhoto stromu môžeme reprezentovať nasledujúcou štruktúrou: | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | struct treeNode { | ||
+ | // číselná hodnota (len v listoch) | ||
+ | double val; | ||
+ | |||
+ | // operátor vo vnútorných uzloch, pre listy medzera | ||
+ | char op; | ||
− | + | // smerníky na podstromy | |
+ | treeNode * left, * right; | ||
+ | }; | ||
+ | </syntaxhighlight> | ||
− | + | * Vnútorné uzly stromu zodpovedajú operátorom | |
+ | * Listy zodpovedajú číselným hodnotám | ||
− | + | Videli sme | |
− | * | + | * Štruktúru <tt>treeNode</tt> |
− | + | * Vytvorenie stromu z postfixového výrazu (podobné na vyhodnocovanie, využíva sa zásobník hotových podstromov) | |
+ | * Vyhodnotenie výrazu, výpis v postfixovej, prefixovej a infixovej forme, uvoľnenie pamäte stromu (jednoduché rekurzívne funkcie) | ||
− | |||
− | + | Zaoberali sme sa aj všeobecnými binárnymi stromami, videli sme | |
+ | * Terminológiu | ||
+ | * Štruktúru <tt>node</tt> | ||
+ | * Výpis v poradí preorder, inorder, postorder, uvoľnenie pamäte stromu (jednoduchá rekurzia, podobne ako pre výrazy) | ||
+ | * Hĺbka vrchola a výška stromu | ||
− | + | Dokončime teraz [[Prednáška_20#Pr.C3.ADklad:_pln.C3.A9_bin.C3.A1rne_stromy|cvičenie z minulej prednášky]]. | |
− | == | + | == Binárne vyhľadávacie stromy == |
− | + | [[Image:P22-BST.png|200px|right|thumb|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áška 14#Dynamick.C3.A1_mno.C5.BEina_2|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 <tt>int</tt>), tieto dáta niekedy voláme aj kľúč | ||
+ | * Pre každý vrchol ''v'' stromu platí: | ||
+ | ** Každý vrchol v ľavom podstrome ''v'' má hodnotu <tt>data</tt> menšiu ako vrchol ''v'' | ||
+ | ** Každý vrchol v pravom podstrome ''v'' má hodnotu <tt>data</tt> 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 <tt>node</tt> | ||
+ | * Položka <tt>data</tt> typu <tt>int</tt> | ||
+ | * 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 <tt>NULL</tt> v koreni) | ||
+ | Celý strom je štruktúra obsahujúca iba smerník na koreň | ||
+ | * Pre prázdny strom je to <tt>NULL</tt>. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | |||
struct node { | 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 *parent; // | + | node * right; /* pravé dieťa, NULL ak neexistuje */ |
− | node *left; / | ||
− | node *right; / | ||
}; | }; | ||
− | + | /* Samotná dynamická množina (obal pre používateľa). */ | |
− | + | struct set { | |
− | + | node *root; /* koreň stromu, NULL pre prázdny strom */ | |
− | |||
− | /* | ||
− | struct | ||
− | node *root; | ||
}; | }; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Inicializácia prázdneho binárneho vyhľadávacieho stromu | |
− | |||
− | |||
− | |||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | /* | + | /* Funkcia inicializuje prázdny binárny vyhľadávací strom */ |
− | void | + | void init(set &s) { |
− | + | s.root = NULL; | |
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Riadok 58: | Riadok 101: | ||
=== Likvidácia binárneho vyhľadávacieho stromu === | === Likvidácia binárneho vyhľadávacieho stromu === | ||
− | Likvidáciu podstromu zakoreneného v danom uzle <tt> | + | Likvidáciu podstromu zakoreneného v danom uzle <tt>root</tt> realizujeme funkciou <tt>destroy</tt>, obdobne ako pri všeobecných binárnych stromoch. Používateľovi navyše dáme k dispozícii aj funkciu <tt>destroy</tt>, ktorá dostane množinu implementovanú ako strom a tento strom zlikviduje. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 70: | Riadok 113: | ||
} | } | ||
− | + | /* Zlikviduje množinu s (uvoľní pamäť). */ | |
− | + | void destroy(set &s) { | |
− | + | destroy(s.root); | |
− | |||
− | /* Zlikviduje | ||
− | void | ||
− | destroy( | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Riadok 82: | Riadok 121: | ||
=== Hľadanie v binárnom vyhľadávacom strome === | === Hľadanie v binárnom vyhľadávacom strome === | ||
− | + | Funkcia <tt>findNode</tt> v podstrome s koreňom <tt>root</tt> hľadá uzol, ktorého položka dáta obsahuje hľadaný kľúč <tt>key</tt>. 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 <tt>contains</tt> zavolá funkciu <tt>findNode</tt> pre koreň daného binárneho vyhľadávacieho stromu <tt>t</tt> a pomocou nej zistí, či tento strom obsahuje uzol s kľúčom <tt>key</tt>. | |
− | + | <syntaxhighlight lang="C++"> | |
+ | /* 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) { |
− | node * | + | if (root == NULL || key == root->data) { |
− | if (root == NULL || root-> | ||
return root; | return root; | ||
− | } else if (key < root-> | + | } else if (key < root->data) { |
− | return | + | return findNodeR(root->left, key); |
− | } else { | + | } else { // key > root->data |
− | return | + | 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; | |
− | /* Zisti, ci strom | ||
− | bool | ||
− | return findNode( | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Čas výpočtu je v najhoršom prípade úmerný výške stromu. | + | Čas výpočtu je v najhoršom prípade úmerný výške stromu. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== Vkladanie do binárneho vyhľadávacieho stromu === | === Vkladanie do binárneho vyhľadávacieho stromu === | ||
− | Nasledujúca funkcia <tt>insertNode</tt> vloží uzol <tt>*v</tt> na správne miesto podstromu zakoreneného v <tt>*root</tt> ako jeho list. | + | Nasledujúca funkcia <tt>insertNode</tt> vloží uzol <tt>*v</tt> na správne miesto podstromu zakoreneného v <tt>*root</tt> 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 <tt>add</tt> vytvorí uzol s daným kľúčom <tt>key</tt> a pomocou funkcie <tt>insertNode</tt> ho vloží do binárneho vyhľadávacieho stromu. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | /* | + | /* Vloží uzol v na správne miesto podstromu zakoreneného v root */ |
void insertNode(node *root, node *v) { | void insertNode(node *root, node *v) { | ||
assert(root != NULL && v != NULL); | assert(root != NULL && v != NULL); | ||
− | if (v-> | + | if (v->data < root->data) { |
if (root->left == NULL) { | if (root->left == NULL) { | ||
root->left = v; | root->left = v; | ||
Riadok 153: | Riadok 197: | ||
} | } | ||
− | + | /* Vloží do stromu pre mnozinu s nový uzol s kľúčom key. */ | |
− | + | void add(set &s, int key) { | |
− | |||
− | |||
− | /* | ||
− | void | ||
node *v = new node; | node *v = new node; | ||
− | v-> | + | v->data = key; |
v->left = NULL; | v->left = NULL; | ||
v->right = NULL; | v->right = NULL; | ||
v->parent = NULL; | v->parent = NULL; | ||
− | if ( | + | if (s.root == NULL) { |
− | + | // specialny pripad, ked vkladame prvy uzol | |
+ | s.root = v; | ||
} else { | } else { | ||
− | insertNode( | + | insertNode(s.root, v); |
} | } | ||
} | } | ||
Riadok 174: | Riadok 215: | ||
Čas vkladania je tiež v najhoršom prípade úmerný hĺbke stromu. | Čas vkladania je tiež v najhoršom prípade úmerný hĺbke stromu. | ||
− | '' | + | '''Cvičenia''' |
− | + | * Ako bude vyzerať strom po nasledujúcej postupnosti operácií? | |
− | + | <pre> | |
− | + | set s; | |
− | + | init(s); | |
+ | add(s, 2); | ||
+ | add(s, 5); | ||
+ | add(s, 3); | ||
+ | add(s, 10); | ||
+ | add(s, 7); | ||
+ | </pre> | ||
+ | * Napíšte nerekurzívny variant funkcie <tt>insertNode</tt>. | ||
+ | * Do funkcie doplňte <tt>assert</tt>, ktorý deteguje prípad, že vkladaná hodnota sa už v strome nachádza. | ||
+ | * Napíšte funkciu <tt>treeSort</tt>, ktorá z poľa celých čísel <tt>a</tt> pomocou volaní funkcie <tt>add</tt> vytvorí binárny vyhľadávací strom a následne pomocou prehľadávania tohto stromu v poradí ''inorder'' pole <tt>a</tt> utriedi. | ||
− | + | ===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 <tt>minNode</tt> 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 <tt>min</tt>, ktorá pomocou funkcie <tt>minNode</tt> nájde minimálny kľúč v danej množine. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | /* Vrati | + | /* Vrati uzol s minimalnou hodnotou data v podstrome s korenom v. */ |
− | node *minNode(node * | + | node *minNode(node *v) { |
− | assert( | + | 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; | |
− | /* Vrati | ||
− | int | ||
− | assert( | ||
− | return minNode( | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | '' | + | ''Cvičenia'': |
− | + | * Napíšte rekurzívny variant funkcie <tt>minNode</tt>. | |
− | + | * Ako by bolo treba funkciu zmeniť, aby hľadala maximum? | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Funkcia <tt>successorNode</tt> nájde pre daný uzol <tt> | + | Funkcia <tt>successorNode</tt> nájde pre daný uzol <tt>v</tt> 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 <tt>v</tt>. |
− | * Ak má uzol <tt> | + | * Ak má uzol <tt>v</tt> pravé dieťa, následník uzla <tt>v</tt> bude vrchol s minimálnou hodnotou data v pravom podstrome |
− | * V opačnom prípade môže byť následníkom uzla <tt> | + | * V opačnom prípade môže byť následníkom uzla <tt>v</tt> jeho rodič, ak <tt>v</tt> je jeho ľavé dieťa. |
+ | * Ak je <tt>v</tt> pravým dieťaťom svojho rodiča, môže to byť jeho prarodič (ak je rodič uzla <tt>v</tt> ľavým dieťaťom tohto prarodiča), atď. | ||
+ | * Vo všeobecnosti teda ide o najbližšieho predka uzla <tt>v</tt> takého, že <tt>v</tt> 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ť? | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | /* Vrati uzol, ktory vo vzostupnom poradi uzlov podla klucov nasleduje za | + | /* Vrati uzol, ktory vo vzostupnom poradi uzlov podla |
+ | * klucov nasleduje za v. | ||
+ | * Ak taky uzol neexistuje, vrati NULL. */ | ||
node *successorNode(node *v) { | node *successorNode(node *v) { | ||
assert(v != NULL); | assert(v != NULL); | ||
Riadok 274: | Riadok 289: | ||
=== Mazanie z binárneho vyhľadávacieho stromu === | === Mazanie z binárneho vyhľadávacieho stromu === | ||
− | Nasledujúca funkcia <tt> | + | Nasledujúca funkcia <tt>remove</tt> zmaže z binárneho vyhľadávacieho stromu uzol s kľúčom <tt>key</tt> (ak sa taký uzol v strome vyskytuje). |
+ | |||
+ | * Najprv pomocou funkcie <tt>findNode</tt> nájde uzol <tt>v</tt> s kľúčom <tt>key</tt>. | ||
+ | * 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. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | /* Zmaze zo stromu | + | /* Zmaze zo stromu pre mnozinu s uzol s klucom key, ak tam taky je. */ |
− | void | + | void remove(set &s, int key) { |
− | node *v = findNode( | + | // Najde uzol s hodnotou, ktoru treba vymazat. |
+ | node *v = findNode(s.root, key); | ||
if (v == NULL) { | if (v == NULL) { | ||
+ | // pozadovany uzol neexistuje | ||
return; | return; | ||
} | } | ||
− | + | // Najde uzol *rm, ktory sa napokon realne zmaze. | |
+ | node *rm; | ||
if (v->left == NULL || v->right == NULL) { | if (v->left == NULL || v->right == NULL) { | ||
rm = v; | rm = v; | ||
} else { | } else { | ||
rm = successorNode(v); | rm = successorNode(v); | ||
+ | // Presunie kluc uzla *rm do uzla *v. | ||
+ | v->data = rm->data; | ||
} | } | ||
− | + | ||
− | + | // ak ma uzol rm dieta, jeho rodicom bude rodic rm | |
− | + | node *child; | |
− | |||
− | |||
− | node *child; | ||
if (rm->left != NULL) { | if (rm->left != NULL) { | ||
child = rm->left; | child = rm->left; | ||
} else { | } else { | ||
child = rm->right; | child = rm->right; | ||
− | } | + | } |
if (child != NULL) { | if (child != NULL) { | ||
child->parent = rm->parent; | child->parent = rm->parent; | ||
} | } | ||
if (rm->parent == NULL) { | if (rm->parent == NULL) { | ||
− | + | s.root = child; | |
} else if (rm == rm->parent->left) { | } else if (rm == rm->parent->left) { | ||
rm->parent->left = child; | rm->parent->left = child; | ||
Riadok 311: | Riadok 336: | ||
rm->parent->right = child; | rm->parent->right = child; | ||
} | } | ||
+ | // rm uz nie je v strome, uvolnime jeho pamat | ||
delete rm; | delete rm; | ||
} | } | ||
Riadok 317: | Riadok 343: | ||
=== Zložitosť jednotlivých operácií === | === Zložitosť jednotlivých operácií === | ||
− | * Časová zložitosť operácií <tt> | + | * Časová zložitosť operácií <tt>contains</tt>, <tt>add</tt> aj <tt>remove</tt> je úmerná výške stromu, ktorú označíme <tt>h</tt>. |
− | * Minule sme ukázali, že pre | + | * Minule sme ukázali, že pre strom s ''n'' uzlami máme log<sub>2</sub>''(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). | * 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 | + | * 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. | * 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. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Aktuálna revízia z 10:20, 4. december 2023
Oznamy
- Tretiu domácu úlohu odovzdávajte do zajtra 22:00.
Prednášky
- V stredu v prvej polovici prednášky informácie k skúške a rady k skúškovému všeobecne, potom doberieme posledné učivo
- Budúci pondelok nepovinná prednáška o nepreberaných črtách jazykov C a C++
- Budúcu stredu 13.12. o 18:10 semestrálny test
Cvičenia
- Zajtra bude rozcvička na papieri, potom pokračujte riešením úloh na testovači
- Piatkové cvičenia nepovinné, avšak odporúčame účasť, ak chcete pomôcť s príkladmi alebo máte otázky
- Budúci utorok v rámci cvičení tréning na skúšku
- Na testovači už je niekoľko tréningových príkladov, za niektoré môžete dostať aj bonusový bod do cvičení, ešte dva príklady pribudnú neskôr
- V piatok 15.12. od 13:10 predtermín skúšky, cvičenia nebudú
Opakovanie: aritmetický výraz ako strom
Uzol takéhoto stromu môžeme reprezentovať nasledujúcou štruktúrou:
struct treeNode {
// číselná hodnota (len v listoch)
double val;
// operátor vo vnútorných uzloch, pre listy medzera
char op;
// smerníky na podstromy
treeNode * left, * right;
};
- Vnútorné uzly stromu zodpovedajú operátorom
- Listy zodpovedajú číselným hodnotám
Videli sme
- Štruktúru treeNode
- Vytvorenie stromu z postfixového výrazu (podobné na vyhodnocovanie, využíva sa zásobník hotových podstromov)
- Vyhodnotenie výrazu, výpis v postfixovej, prefixovej a infixovej forme, uvoľnenie pamäte stromu (jednoduché rekurzívne funkcie)
Zaoberali sme sa aj všeobecnými binárnymi stromami, videli sme
- Terminológiu
- Štruktúru node
- Výpis v poradí preorder, inorder, postorder, uvoľnenie pamäte stromu (jednoduchá rekurzia, podobne ako pre výrazy)
- Hĺbka vrchola a výška stromu
Dokončime teraz cvičenie z minulej prednášky.
Binárne vyhľadávacie stromy
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), tieto dáta niekedy voláme aj kľúč
- 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.
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
- 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);
- Napíšte nerekurzívny variant funkcie insertNode.
- Do funkcie doplňte assert, ktorý deteguje prípad, že vkladaná hodnota sa už v strome nachádza.
- 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.
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 min, ktorá pomocou funkcie minNode nájde minimálny kľúč v danej množine.
/* 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);
// Presunie kluc uzla *rm do uzla *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 log2(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.