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áš?