Ministri sú zaneprázdnení ľudia. Často krát by sa chceli nachádzať na viacerých miestach naraz. V našom svete to ale nejde. Napíšte program, ktorý pomôže zaneprázdnenému ministrovi pri plánovaní svojho času (ženy si organizujú čas lepšie aj bez programu).

Minister nemá vždy voľný čas, a tak, keď sa s ním chce stretnúť, poviete mu kedy sa s ním chcete stretnúť a na ako dlho. On sa pozrie do svojho denníka, vyhľadá všetky prekrývajúce sa schôdzky a zváži či mu to stojí zato (sa s Vami stretnúť). Ak áno, zaradí si v danom intervale aj Vašu schôdzku do zoznamu... nikdy neviete, či minister na schôdzku príde, ale to už je iná úloha.

Každý návrh na stretnutie má tvar dvoch celých čísel OD, DO opisujúcich začiatok a koniec navrhovaného stretnutia (vrátane krajných časov OD a DO) a identifikačného čísla I. Keď ministrovi príde takáto požiadavka, potrebuje od Vášho programu vypísať všetky prekrývajúce sa schôdzky; teda schôdzky, ktoré aspoň čiastočne zasahujú do časového intervalu *OD,DO+. Po zvážení sa môže minister rozhodnúť schôdzku zaradiť do svojho programu. Z času načas tiež ministra zaujíma, ktoré schôdzky obsahujú nejaký konkrétny okamih (napr. polnoc).

Napíšte program, ktorý tieto požiadavky spracuje zo štandardného vstupu, a odpoveď vypíše na štandardný výstup. Na vstupe sa jednotlivé požiadavky nachádzajú vždy v novom riadku, začínajú názvom operácie.

Operácii na vstup môže byť veľmi veľa (až do 500 000), preto by mal Váš program fungovať rýchlo. Pri riešení úlohy použite modifikovaný binárny vyvážený vyhľadávací strom (napr. červeno čierny strom). Vyvážené vyhľadávacie stromy zaručujú zložitosť spracovania jednej operácie O(log N). Riešenie s nevyváženým stromom nestihne ukončiť prácu v časovom limite na všetkých vstupoch, a dostane menej bodov.

Navyše, ak použijete vlastnú implementáciu zreťazenej voľnej pamäti (ktorú ste implementovali v prvom zadaní; môžete si ju ešte opraviť, ak obsahovala chyby) môžete získať DVA prémiové body, ktoré sa započítavajú ku skúške.

Pre realizáciu zadania som využil binárny vyvážený vyhľadávací strom, konkrétne AVL strom. Jeho vynikajúcou vlastnosťou je rýchle vyhľadávanie. Keďže ide o binárny strom, každý vrchol má najviac dvoch nasledovníkov. Rozlišujeme ich na ľavý a pravý nasledovník. Najdôležitejšia vlastnosť AVL stromov je ich vyvažovanie. Aby bol strom vyvážený, musí byť každý vrchol vyvážený. Vyváženie v tomto prípade znamená, že rozdiel výšky jedného podstromu, nesmie byť väčší ako +/- 1. To znamená, že ak napr. výška pravého podstromu je 5, tak ľavý podstrom môže mať výška 4, 5 alebo 6. V mojej implementácií je použitý teda jej rozdiel ako jedna položka v každom vrchole. Môže nadobúdať hodnoty -1, 0 alebo 1. V prípade, ak sa rovná nule, ide o rovnako vyvážený strom, čiže výška ľavého aj pravého podstromu sú rovnaké.

Obrázok 1 Znázornenie rôznych prípadov výšky vrcholu

Implementácia vkladanie je robená rekurzívne. Do tejto funkcie dávame (okrem iného) ako vstupný parameter koreň stromu. Stromom postupne prechádzame rekurzívne, až pokiaľ nenájdeme vhodné miesto na uloženie tohto nového vrcholu. Ak miesto nájdeme, musíme ešte zaručiť integritu vyvažovania. To znamená, že po každom vkladaní sa musíme uistiť, že strom zostáva vyvážený. Pri operácií vkladania sa môžu meniť hodnoty vyváženia iba v predchodcoch vloženého vrcholu. Preto je dobré využiť rekurzívnu metódu, ktorá potom spätne prejde všetkých predchodcov a nastaví im tento parameter na správnu hodnotu. Na pomoc je tu využitá globálna premenná, ktorá slúži ako tzv. flag. Dalo by sa povedať, že je to premenná, ktorá uchováva akýsi stav v momente. Globálna je preto, lebo sa využíva v celej rekurzii. Dalo by sa to implementovať aj posielaním adresy premennej, no takéto obmedzenia neboli špecifikované v zadaní.

V prípade, že vrchol sa dostane do stavu, že porušuje pravidlo vyváženosti, musíme urobiť rotáciu. Rotácia znamená výmena vzťahov medzi vrcholmi tak, aby sa na tomto úseku strom dostal opäť do vyváženého stavu. Toto nám následne zaručí, že strom ako celok bude vyvážený. Viď obrázok.

Obrázok 2 Jednoduchá rotácia (jedným smerom)

Zároveň, v priebehu vykonávania opätovného vkladania môže nastať situácia, keď nám jednoduchá rotácia nebude stačiť. Vtedy musíme zavolať tzv. dvojitú rotáciu. Je to vlastne rotácia spojená z dvoch jednoduchých rotácií. Taktiež po vykonaní tejto rotácie musíme upraviť vzťahy medzi vrcholmi, ktoré rotujú a tiež treba nastaviť všetkým vrcholom do ktorých rotácia zasiahla, ich indikátor vyváženosti.

Obrázok 3 Dvojitá rotácia (jedným smerom)

Z uvedeného vyplýva, že výška AVL stromu nemôže presiahnuť log n , kde n je počet vrcholov. Práve tento fakt ovplyvňuje najhoršiu zložitosť vykonávania na hodnotu O(log n), pretože ak by sme mali obyčajný (nevyvážený) binárny vyhľadávací strom, jeho maximálna výška môže dosiahnuť hodnotu n, t.j. zložitosť v najhoršom prípade je O(n). Týmto sme teda dosť redukovali čas potrebný na vykonávanie operácií so stromom. Tento čas by sme mohli ešte viac redukovať, keby sme si pri každom vrchole pamätali aj informáciu o najväčšej položke v podstrome, t.j. najväčšiu hodnotu času konca schôdzky. Tým by sme sa pri prehľadávaní stromu mohli vyhnúť zbytočnému prehľadávaniu vrcholov, ktoré sa nachádzajú v podstrome, ktorého maximálna hodnota nadobúda menšiu hodnotu ako začiatok hľadanej schôdzky a tie by sme teda mohli preskočiť. V zadaní však bolo uvažovať o vyváženom vyhľadávacom strome vo všeobecnosti, bez akýchkoľvek modifikácií, ktoré by ovplyvňovali rýchlosť.

Na vyhľadávanie, t.j. operácie FINDPOINT a FINDINTERVAL som použil princíp vyhľadávania známym pod názvom inorder. Princíp je rekurzívne prehľadávanie, kde najprv prehľadáva ľavý podstrom, potom koreň a následne pravý podstrom. Funkcia FINDPOINT prehľadáva prvky postupne a ak nastane splnenie podmienky (ak daný čas patrí do intervalu jednotlivej schôdzky, ktorá je práve prehľadávaná) tak sa identifikátor tejto schôdzky zapamätá do pomocného poľa. V prípade funkcie FINDINTERVAL je jej implementácia analogická, jedinou zmenou je rozšírenie podmienky, ktorá porovnáva, či daný interval akokoľvek zasahuje do intervalu jednotlivých schôdzok.

Ďalším spôsobom na implementáciu tohto zadania by mohlo byť využitie Červeno-čierneho stromu. Princíp je skoro rovnaký, len založený na inej indikácií vyváženia. Zatiaľ čo pri AVL strome som si pamätal vyváženosť na základe jednotlivých podstromov vrcholu, pri červeno-čiernych stromoch sa pamätá údaj o farbe. Na základe tohto údaju sa potom vykonávajú operácie vyvažovania, tak aby boli splnené zásadné pravidlá tohto typu stromu. Napríklad, že nemôžu byť dva červené vrcholy za sebou (hierarchicky). Tento spôsob bol pôvodný plán mojej implementácie, no neskôr som zvolil použitie AVL, pretože vyvažovanie pri červeno-čiernych stromoch sa mi zdalo príliš chaotické, teda prefarbovanie vrcholov pri rotáciách a pod. Taktiež sa mi tým uľahčilo testovanie a nebolo nutné pri každom vrchole sledovať farby, a či týmito farbami neporušujú nejaké z pravidiel červeno-čiernych stromov.

Testovanie bolo za behu implementácie. Najprv som si vytvoril pár základných testov, ktorých úlohou bolo odhaliť základné chyby implementácie. Taktiež som využil metódu regresívneho testovania. V prvotnej fázy som si taktiež pomáhal pomôckou Jakuba Kováča. Jeho aplikácia v jazyku Java dokáže odsimulovať pridávanie a odstraňovanie vrcholov z a do rôznych stromov a interaktívne ukazuje stav stromu po každej operácií.1 Nakoniec som vytvoril väčšie scenáre na otestovanie programu pre otestovanie základných funkcií, rôznych výnimkách a pri zadaní veľkého množstva operácií (od 200 až po niečo pod 500 000).

Pri analýze problematiky som využil už spomínanú aplikáciu Jakuba Kováča. Okrem nej by som chcel odporučiť aj kanál siedmych Indických inštitútov technológií a vedy na video portály Youtube2. Konkrétne sériu prednášok Dátové štruktúry a algoritmy, ktoré vedie Dr. Naveen Garg. V týchto prednáškach podrobne rozoberá problematiku rôznych programovacích algoritmov, štruktúram programovanie atď. K problematiku zadania sú vhodné prednášky, kde rozoberá výšku AVL stromov3 a prednáška o vkladaní a odstraňovaní vrcholov z takéhoto stromu.

Aplikáciu sa dá nájsť na adrese http://people.ksp.sk/~kuko/bak/index-sk.html [13/11/2010]

Kanál indických inštitútov http://www.youtube.com/user/nptelhrd

Rozoberanie výšky AVL stromov http://www.youtube.com/watch?v=mRGQylRWAsI

Vkladanie a odstraňovanie v AVL stromoch http://www.youtube.com/watch?v=TbvhGcf6UJU