2. Rýchle hľadanie kontaktov
Zadanie
Novinka: popis nemusíš odovzdávať len na konci kola, ale môžeš už priebežne. My sa ti ho pokúsime čo najskôr opraviť a ak nebudeš mať všetko alebo niečo nebude správne, tak tvoj popis môžeš doplniť/opraviť a znovu ho odovzdať.
Červená Čiapočka bola rada, že sa z bludiska dostala živá a zdravá, ale aj tak sa stretnutia s Vlkom veľmi zľakla. Rozhodla sa, že pre istotu zavolá mame a povie jej, čo sa stalo. V tých dávnych dobách, keď vznikla táto rozprávka, si ale ešte telefóny nevedeli ukladať kontakty a všetky tie ďalšie veci, čo dnes už vedia. Dalo sa len vytočiť číslo a volať. Čiapočka mala hrozne zlú pamäť a telefónne čísla vždy zabúdala, a tak si spolu s telefónom nosila aj papierik, na ktorom mala napísané všetky čísla, ktoré potrebovala vedieť. Bohužiaľ, písala si ich tam dosť chaoticky v náhodnom poradí, a tak jej hodnú chvíľu trvalo, kým vôbec našla, kde v zozname je mama. Potom sa jej už podarilo jej zavolať, ale rozmýšľala, či by sa nedalo mať telefónne čísla uložené nejak lepšie.
Úloha
Červená Čiapočka by si chcela telefónne čísla uložiť tak, aby potom vedela z mena kontaktu rýchlo dostať jeho telefónne číslo. Na to jej môže pomôcť písmenkový strom.
Písmenkový strom sa skladá z niekoľkých vrcholov, v ktorých môže byť uložená nejaká informácia, napríklad telefónne číslo. Rôzne vrcholy môže byť pospájané šípkami. Každá šípka je označená nejakým písmenom, a z každého vrcholu vedie najviac jedna šípka s každým písmenom. Jeden vrchol je špeciálne označený a voláme ho koreň. Môže to vyzerať napríklad takto:
Do písmenkového stromu si môžeme k nejakému slovu (napríklad mena kontaktu) uložiť nejakú ďalšiu informáciu (napríklad telefónne číslo), a túto informáciu vieme potom rýchlo nájsť. To spravíme tak, že začneme v koreni a postupne pôjdeme po šípkach s takými písmenami, ako sú písmená toho slova, ktoré hľadáme. Vo vrchole, kde skončíme, je tá informácia, čo hľadáme. Vrcholy, v ktorých je niečo uložené, sú na obrázku označené hrubou čiarou.
Napríklad v strome na obrázku vyššie sú uložené kontakty BABKA, BRANO, MAMA a MATEJ.
a. V ktorom vrchole by malo byť uložené Braňove telefónne číslo?
b. Ako by vyzeral strom, v ktorom sú uložené kontakty JAN, JANKA, LUCKA a LUKAS? Nemusíš k nim písať žiadne údaje, iba označ vrcholy, kam by sa ukladalo niečo, čo patrí k tým menám.
c. Keď máš nejaký písmenkový strom a chceš doňho pridať nový kontakt, ako to urobíš?
d. Ako vieš vymazať kontakt? Ak potom ostanú nejaké vrcholy zbytočné, tak vymaž aj tie, ale nevymazávaj vrcholy, ktoré tam ešte stále treba.
e. Predstav si, že chceš vypísať zoznam všetkých kontaktov v abecednom poradí. Ako to spravíš?
f. Predstav si, že máš uložené kontakty ADAM, ALEXANDRA, ALICA, ANICKA a ANTON. Už keď začneš hľadať ALE, je jasné, že hľadáš ALEXANDRA, lebo žiadne iné meno nezačína na ALE. Nechce sa ti ísť cez všetky tie ďalšie písmenká. Chceš ku každému začiatku mena vedieť rýchlo nájsť vrchol s nejakým menom, ktoré začína na tento začiatok.
Môžeš si do stromu ku každému vrcholu pridať ešte jednu špeciálnu šípku, ktorá bude ukazovať na iný vrchol. Aké si tam dáš šípky a ako pomocou nich budeš vedieť hľadať mená k začiatkom? A ako tie šípky čo najrýchlejšie nájdeš, keď ich ešte v strome nemáš?
a
b
c
Ideme postupne po písmenkách nového mena. Kým máme v strome také šípky, ako potrebujeme, tak použijeme tie, a keď už nie, tak začneme vyrábať nové vrcholy.
Napríklad keby sme do stromu z úlohy (b) chceli pridať meno JARO,
tak ideme najprv po šípkach s J a A,
ale šípku s R tam už nemáme, takže pridáme nový vrchol a šípku s R k nemu,
a podobne pridáme aj šípku s O.
d
Ideme od konca mena a kým sa tie vrcholy používajú iba v tom jednom mene, tak ich vymazávame. Akonáhle ale z toho vrcholu vedie aj nejaká iná šípka než tá, po ktorej sme prišli, tak sa ten vrchol používa aj pre iné meno, a teda ho tam musíme nechať. Ak teda narazíme na nejakú inú šípku, už môžeme rovno skončiť, lebo žiadne ďalšie vrcholy už nemôžeme vymazať.
Napríklad v strome z (b) keby sme chceli vymazať Lucku, tak vymažeme vrcholy, nad ktorými sú šípky A, K, C,
ale vedľa C je ešte šípka K (ktorá sa používa pri Lukášovi), takže ten vrchol tam už necháme a skončíme.
e
Zopakujme si najprv, ako zistíme, ktoré z nejakých dvoch slov je skôr v abecede. Ak majú rôzne prvé písmeno, tak sa rozhodne podľa toho, ktoré z tých písmen je skôr. Ak sú prvé písmená rovnaké, tak sa rozhodne podľa druhých písmen, ak aj tie sú rovnaké, tak podľa tretích, a tak ďalej. Ak je jedno zo slov začiatok druhého, tak skôr je to kratšie z nich.
Budeme teda v strome prechádzať presne v abecednom poradí. Predstavme si, že máme strom nakreslený tak, že to čo je skôr v abecede je viac vľavo. Ideme postupne z koreňa a ideme vždy čo najviac doľava, až kým sa nedostaneme na koniec cesty – tak dostávame postupne slová najskoršie v abecede. Potom sa vrátime k najbližšiemu vrcholu nad nami a vezmeme druhú najľavejšiu cestu, a takto pokračujeme. Keď sa nám pod nejakým vrcholom minú všetky cesty, tak sa z neho vrátime zase hore k najbližšiemu ďalšiemu vrcholu a pokračujeme tam. Skončíme, keď prejdeme všetky cesty spod koreňa a vrátime sa.
Skúsení riešitelia (alebo tí, čo riešili úlohu 1 s bludiskom) si určite všimnú, že toto je presne prehľadávanie grafu do hĺbky (alebo spôsob, akým vie Červená Čiapočka prejsť bludisko bez cyklov.
f
Môžeme si z každého vrcholu dať šípku k nejakému menu, ktoré je v strome pod ním (teda sa začína na taký začiatok). Takých mien môže byť viac, tak povedzme, že keď máme viac možností, tak si vyberieme to meno, ktoré je prvé v abecede. Hľadanie je potom jednoduché, keď sme v nejakom vrchole, tak meno nájdeme tak, že sa pozrieme po šípke.
Otázka je, ako tieto šípky nájsť. Mohli by sme sa z každého vrcholu osobitne pustiť dole a hľadať, až kým nenájdeme nejaké meno,
ale to by pre veľké stromy mohlo trvať veľmi dlho.
Napríklad ak mám meno ALEXANDRA ako v zadaní, tak od vrcholu, ktorý zodpovedá začiatku ALE už všetky šípky ukazujú až na koniec,
ale nechceme z každého vrcholu po ceste osobitne hľadať to isté meno.
Vyriešiť to môžeme tak, že budeme šípky vyrábať “od konca”. Nájdeme si nejaké meno a potom od neho pôjdeme v strome hore a z každého vrcholu po ceste budeme smerovať šípky na toto meno. Toto robíme až dovtedy, kým sa nedostaneme k vrcholu, ktorý má pod sebou aj niečo menšie v abecede (teda šípku viac doľava, alebo má nejaké meno rovno v sebe). Keď toto spravíme postupne so všetkými menami, tak budeme mať šípky vo všetkých vrcholoch.
