Cvičenie č.12

Ciele

Konfigurácia vývojového prostredia pre potreby výpisu ADT BVS a AVL.
Porozumieť dodanej implementácii ADT binárny vyhľadávací strom (BVS).
Podľa pokynov doplniť implementáciu.
Porozumieť dodanej implementácii ADT vyvážený strom (AVL).
Podľa pokynov doplniť implementáciu...

Úvod

množina

Postup

Konfigurácia prostredia Code::Blocks pre potreby zobrazenia stromov.

Úloha: Nastavenie vývojového prostredia tak, aby bolo možné realizovať úhľadný výpis stromových údajových štruktúr.
Pre účely zobrazenia stromových údajových štruktúr budeme využívať volania funkcií, ktoré nie sú súčasťou štandardného balíka vývojového prostredia. Bude preto potrebné, aby sme toto vývojové prostredie nakonfigurovali spôsobom opísaným v nasledujúcich krokoch:
- Stiahnúť a nainštalovať balík Conio, ktorý obsahuje knižničné funkcie pre grafickú prácu v konzolovom okne.
- Nastaviť projekt tak, aby vedel využívať nainštalovaný balík Conio.
Stiahnúť balík Conio je možné na tejto adrese. Po následnom uložení daného balíka na disk je ďalej potrebné tento balík spustiť. Po jeho spustení, Dev C++ Package Manager spustí inštaláciu tohto knižničného balíka, pričom je potrebné sa ďalej riadiť jeho pokynmi.

Ak je už daný balík nainštalovaný, je potrebné ešte nastaviť náš projekt tak, aby vedel využívať tento balík. Je preto potrebné v hlavnom okne Dev C++ zvoliť ponuku: Projekt - Nastavenie projektu. Následne sa otvorí okno zobrazené na nasledujúcom obrázku.

V tomto okne zvolíme ponuku Parametre na vrchnej lište a do textového poľa označeného ako Linker zadáme reťazec "-lconio". Nastavenia ešte potvrdíme a všetko je pripravené na to, aby sme mohli volať knižničné funkcie pre grafickú podporu v konzolovom okne. Pomocou funkcií z tohto balíka je teda možný úhľadný výpis ÚŠ BVS a ÚŠ AVL na monitor počítača.
Implementácia ADT binárny vyhľadávací strom (BVS).

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

Pripravený archív obsahuje tieto súbory:
- fatal.h - definičný modul pre ošetrenie chýb.
- bvs.h - definičný modul ADT binárny vyhľadávací strom (BVS). Obsahuje definície údajových typov a prototypov operácií.
- bvs.c - implementačný modul ADT binárny vyhľadávací strom. Definícia štruktúry vrcholu BVS (Node), implementácia operácií.
- test.c - modul pre testovanie činnosti ADT binárny vyhľadávací strom.
Binárny vyhľadávací strom je taký binárny strom, ktorý má svoje vrcholy usporiadané tak, že pre každý vrchol t_i budú všetky kľúče ľavého podstromu vrcholu t_i menšie ako kľúč vrcholu t_i a všetky kľúče v pravom podstrome väčšie ako kľúč t_i.

Z definície BVS je zrejmá činnosť jednotlivých operácii na binárnom vyhľadávacom strome.

Operácie pre ÚŠ binárny vyhľadávací strom:
- Insert - pridá zadaný kľúč do BVS.
- MakeEmptyNode - vyhradí pamäť pre jeden vrchol BVS.
- Delete - odstráni zadaný kľúč z BVS.
- DisposeNode - uvoľní pamäť pre vymazaný vrchol BVS.
- Member - zistí, či daný kľúč sa nachádza v BVS (uvedená rekurzívna, treba doplniť nerekurzívnu).
- PrintTree - vypíše obsah BVS na obrazovku (používa prehľadávanie typu preorder na textový výpis BVS).
Poznámka: Operácia Delete využíva funkciu Del, ktorá sa volá len vtedy, ak sa pokúšame odstrániť kľúč patriaci vrcholu, ktorý má oboch potomkov.

Poznámka: Pre overenie správnej činnosti operácie Member je dodaná aj funkcia FindOutKeyFromPointer, ktorá zistí kľúč v strome na základe vrátenej referencie funkciou Member.

Poznámka: Operácia PrintTree využíva funkciu LeftNodeCount a tá využíva funkciu NodeCount, ktoré predstavujú funkcie na získanie počtu vrcholov v ľavom podstrome a počtu vrcholov v celom strome.

Poznámka: Funkcia TreeHeight je využitá na získanie výšky stromu.

Poznámka: Dôkladne si preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.

Ilustrácia základných operácii na BVS.

Pridávanie vrcholov do BVS.
Do BVS sa postupne pridávajú vrcholy s kľúčmi: 6, 3, 18, 7, 5, 2

Poznámka: V niektorých prípadoch sa pri vytváraní BVS stromu môže stať, že vznikne značne deformovaný strom, v najhoršom prípade sa môže dokonca vytvoriť lineárna ÚŠ - zoznam (tento nedostatok odstraňujú napr. AVL stromy).

Odstraňovanie vrcholov z BVS.
Z uvedeného BVS sa postupne odstraňujú vrcholy s kľúčmi: 13, 15, 5, 10

Poznámka: Pri odstraňovaní vrchola z BVS, ktorý má dvoch (priamych) nasledovníkov sa postupuje tak, že sa tento odstraňovaný vrchol nahradí buď najpravejším vrcholom ľavého podstromu alebo najľavejším vrcholom pravého podstromu (dodaná implementácia využíva prvú voľbu, teda odstraňovaný vrchol sa nahradí najpravejším vrcholom ľavého podstromu).

Nájdenie zadaného kľúča v BVS.
Majme nasledujúci BVS:
Na obrázku je naznačený postup, akým sa hľadá kľúč v strome. Na začiatku sa hľadaný kľúč porovnáva s kľúčom koreňového vrcholu. Ak je hľadaný kľúč menší, tak sa postupuje ľavou vetvou, ak väčší, tak pravou. Tento postup sa opätovne aplikuje na ďalšie kľúče vrcholov, pokým sa hľadaný kľúč nenájde (ak existuje).
Výpis obsahu BVS.
Majme nasledovný BVS:
Funkcia PrintTree vypíše nasledovný obsah tohto BVS:
Doplnenie implementácie.

Úloha: Pridajte podporu operácie Member, ktorá bude implementovaná ako nerekurzívna funkcia (rekurzívna už bola uvedená).
Prototyp funkcie MemberNR (bvs.h):
```
Position MemberNR( Key x, Bvs t );
```
Poznámka: Funkciu navrhnite tak, aby jeden parameter udával kľúč ktorý sa má v BVS hľadať a druhý aby určoval smerník na koreň tohto stromu. Funkcia nech vráti smerník na vrchol BVS, ktorý obsahuje hľadaný kľúč alebo NULL, ak hľadaný kľúč nebol v strome nájdený. Pri tvorbe tejto funkcie môžte využiť preddefinovaný boolovský typ (pre zistenie, či už bol hľadaný kľúč nájdený).

Poznámka: Pre overenie činnosti operácie doplňte aj modul pre testovanie.
Implementácia ADT vyvážený strom (AVL).

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.
Pripravený archív obsahuje tieto súbory:
- fatal.h - definičný modul pre ošetrenie chýb.
- bvs.h - definičný modul ADT vyvážený strom (AVL). Obsahuje definície údajových typov a prototypov operácií.
- bvs.c - implementačný modul ADT vyvážený strom. Definícia štruktúry vrcholu AVL (Node), implementácia operácií.
- test.c - modul pre testovanie činnosti ADT vyvážený strom.
Strom je vyvážený vtedy a len vtedy, ak sa výšky dvoch podstromov každého vrcholu líšia najviac o 1.
Poznámka: Stromy spĺňajúce toto kritérium sa často nazývyjú AVL-stromy (podľa svojich objaviteľov).

Operácie na AVL stromoch je možno vykonať v čase O(log n).
Operácie pre ÚŠ vyvážený strom:
- Insert - pridá zadaný kľúč do AVL stromu a pritom zabezpečí, aby strom zostal vyvážený.
- MakeEmptyNode - vyhradí pamäť pre jeden vrchol AVL stromu.
- Delete - odstráni zadaný kľúč z AVL stromu a pritom zabezpečí, aby strom zostal vyvážený.
- DisposeNode - uvoľní pamäť pre vymazaný vrchol AVL stromu.
- Member - zistí, či daný kľúč sa nachádza v AVL strome.
- PrintTree - vypíše obsah AVL stromu na obrazovku (používa prehľadávanie typu preorder na textový výpis AVL stromu).
Poznámka: Operácia Delete využíva funkciu Del, ktorá sa volá len vtedy, ak sa pokúšame odstrániť kľúč patriaci vrcholu, ktorý má obidvoch potomkov.

Poznámka: Operácia Delete využíva aj funkciu Balance1 (dodaná v implementácii), ktorá sa volá v prípade zmenšenia výšky ľavého podstromu a funkciu Balance2 (treba doplniť), ktorá sa volá v prípade zmenšenia výšky pravého podstromu.

Poznámka: Všetky ostatné operácie - pre zistenie, či daný kľúč patrí do AVL stromu (funkcia Member) a pre výpis AVL stromu (PrintTree), ako aj ich pomocné funkcie vykonávajú takú istú činnosť ako zodpovedajúce funkcie pri ADT BVS.

Poznámka: Dôkladne si preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.
Vizualizácia činnosti ADT AVL strom.
Poznámka: Pri pridávaní vrcholov do AVL stromu tak už nemôže nastať prípad, že vznikne lineárna UŠ - ADT zoznam (vyvažovacie operácie to nedovolia).
Doplnenie implementácie.

Úloha: Pridajte operáciu vyváženia jednotlivých podstromov pre operáciu Delete v prípade, že výška pravého podstromu vyvažovaného vrchola sa zmenší.
Prototyp funkcie Balance2 (avl.h): void Balance2 ( Avl *p, Boolean *h );
Poznámka: Jeden parameter nech predstavuje smerník na smerník na koreň AVL stromu (ktorý treba vyvážiť), druhý predstavuje smerník na boolovsku hodnotu (true alebo false), pričom táto hodnota udáva, či došlo k zmenšeniu výšky stromu alebo nie. Iba v prípade, že h má hodnotu true, treba uvažovať o znovuvyvážení. Parameter h nadobudne hodnotu true buď vtedy, keď sa nájde a zruší príslušný vrchol, alebo keď samotné znovuvyváženie spôsobí zmenšenie výšky pravého podstromu. Funkcie Balance1 (dodaná) a Balance2 majú byť symetrické, pričom funkcia Balance1 sa má volať v prípade zmenšenia výšky ľavého podstromu, funkcia Balance2 v prípade zmenšenia výšky pravého podstromu. Obe funkcie sú bez návratovej hodnoty (void).

Poznámka: Všimnite si, že obe parametre oboch funkcií sa prenášajú referenciou (smerník na koreň AVL stromu aj boolovska hodnota) a nie hodnotou, nakoľko tieto funkcie majú mať možnosť ich meniť tak, aby táto zmena ovplyvnila aj správanie funkcií, z ktorých boli tieto funkcie volané.

Poznámka: Funkcie Balance1 a Balance2 sú používané funkciami Delete a Del, pričom vo funkcii Delete sa vyskytujú 3 takéto volania a vo funkcii Del sa vyskytuje jedno takéto volanie. Po skončení implementácie predpísanej funkcie - Balance2 nezabudnite odkomentovať volania implementovanej funkcie z funkcií, ktoré ju volajú (volania sú už predpripravené). Taktiež odkomentujte volania už predpripravenej funkcie Balance1 (takisto sú už predpripravené).

Poznámka: Pre overenie činnosti operácií doplňte aj modul pre testovanie.

Príklad: Chybné a správne odstraňovanie vrcholov v AVL strome.
Poznámka: V dodanej implementácii nie je uvedená definícia funkcie Balance2 (definícia funkcie Balance1 je síce uvedená, ale nie je zatiaľ volaná) a preto operácia odstraňovania vrcholov v AVL strome nefunguje správne. Výsledok tohto nesprávneho odstraňovania môžte vidieť na nasledujúcom obrázku:

Poznámka: Z obrázka je jasne vidieť, že pri odstraňovaní jednotlivých vrcholov z daného AVL stromu, tento strom stráca svoje vyváženie v niektorých prípadoch odstránenia vrcholov (lebo ešte nie sú volané vyvažovacie funkcie a teda daný strom sa pri rušení vrcholov správa ako BVS). Po správnej implementácii predpísanej vyvažovacej operácie má (správne) rušenie vrcholov v tom istom AVL strome vypadať nasledovne:

Z pôvodného vyváženého stromu (a) sa postupne odoberajú vrcholy s kľúčmi 4, 8, 6, 5, 2, 1 a 7; výsledkom sú stromy (b), ..., (h). Zrušenie vrcholu s kľúčom 4 je jednoduché, pretože tento vrchol je listom. Zrušením tohto vrcholu sa však naruší vyváženosť vrcholu 3. Operácia znovuvyváženia vrcholu vyžaduje jednoduchú LL-rotáciu. Znovuvyváženie bude opäť potrebné pri zrušení vrcholu 6. V tomto prípade treba vyvážiť pravý podstrom koreňa 7 a to pomocou jednoduchej RR-rotácie. Zrušenie vrcholu 2 je síce opäť priamočiare (pretože tento vrchol má iba jedného nasledovníka), spôsobí však zložitú dvojitú RL-rotáciu. Predtým ako zrušíme vrchol 7, je potrebné ho nahradiť najpravejším vrcholom jeho ľavého podstromu, t.j. vrcholom s kľúčom 3. Nasledujúca dvojitá LR-rotácia spôsobí znovuvyváženie stromu a jeho záverečnú podobu (h).

Poznámka: Je potrebné si všimnúť podstatný rozdiel medzi operáciou pridávania a rušenia vrcholov v AVL strome. Zatiaľ čo pridanie kľúča môže spôsobiť nanajvýš jednu rotáciu (dvoch alebo troch vrcholov), zrušenie môže vyžadovať rotáciu všetkých vrcholov absolvovanej cesty.

Poznámka: Odstráňte z disku vami vytvorené projekty a súbory. Zanechajte vývojové prostredie v pôvodnom stave.