ITI0140:Ülesanne 20

JõuluvAIna

Jep. Jõulud saabuvad. Kuna aga häid lapsi on imelikul kombel sellel aastal eriti palju, ei jõua jõuluvanad neid kõiki külastada. Appi tuleb moodne tehnika - jõuluvanad realiseerivad AI, kes käiks nende eest lastel külas. Kõik on tore, aga neil on tekkinud probleem ühe pisikese asjaga. Nimelt nad tahaksid, et lapsed ikka toredaid salme robot-jõuluvanale loeksid. Robot omakorda võiks kuidagi hinnata, kas salm oli tore või mitte. Kuna nad põhjalikku sisuanalüüsi ei jõua enam realiseerida, mõtlesid nad välja natuke teise hindamisalgoritmi.

Nimelt paneb robot kuuldud sõnad salmis kahendpuusse. Seejärel saab hinnata, kui "ilus" see puu on. Teatud puustruktuuri korral tuleb lapsel salm uuesti lugeda. Õnneks ei jõua jõuluvanad realiseerida olukorda, kus puustruktuur on väga kehva ning välja on vaja võtta vits.

Jõuluvanad on pöördunud sinu poole abipalvega - pane puusse, pane sõnad puusse. Kuna aga päkapikud on käinud su akna taga luuramas (big brother), siis nad teavad, et ka sinul on kiired ajad ning väga palju vaba aega pole. Seetõttu on jõulumehe soov helde, puustruktuur hindamise funktsionaalsust sa realiseerima ei pea.

Mis siis täpsemalt on vaja teha:

Realiseeri kahendpuu. Kahendpuu peab olema objekt, millel on järgmised meetodid:

add(word) - võtab sõna ja lisab selle puusse õigesse kohta. Kui selline sõna juba on puus, tuleb vastava sõna kogust suurendada.
find(word) - otsib sõna puust. Kui sõna eksisteerib puus, tuleb tagastada ennik kujul (sõna, sõnade kogus, sügavus puus). 
Kui sõna puus ei eksistreeri, tagastab None
print_ordered() - prindib kogu puu välja selliselt, et alustab kõige väiksemast (tähestiku järjekorras) ja lõpetab kõige suuremaga. 
Iga elemendi kohta printida sõna ja selle kogus.

Iga element kahendpuus peaks hoidma järgmist infot:

sõna kogus - mitu sellist sõna on puusse lisatud viide vasakule alampuule - selles puus peaksid kõik väärtused olema väiksemad kui sõna antud harus viide paremale alampuule - selles puus peaksid kõik väärtused olema suuremad kui sõna antud harus

Selleks, et saaksime kahendpuud testida, on vaja järgmist funktsiooni:

get_tree() - tagastab instantsi kahendpuust (millel on siis kõik eelnevalt mainitud meetodid).

Näiteks võiks su kood töötada sedasi:

t = get_tree()
t.add('c')
t.add('a')
t.add('b')
t.add('a')
t.print_ordered()
print(t.find('a'))
print(t.find('b'))
print(t.find('c'))

Ja väljund oleks:

a 2
b 1
c 1
('a', 2, 1)
('b', 1, 2)
('c', 1, 0)

Puu näeks välja umbes selline:

    c
  /
a
 \
  b

Boonusülesanne.

Realiseeri tasakaalustatud (balansseeritud) kahendpuu. Selleks on sul kaks varianti:

1) Iga elemendi lisamisel tõstad elemente nii ringi, et peale lisamist oleks puu jälle tasakaalus.

2) Peale elementide lisamist puusse teed uue puu, mis on tasakaalus.

Testimiseks on sul vaja realiseerida funktsioon:

get_balanced_tree(tree) - saab ette kahendpuu (samat tüüpi, mis get_tree() tagastab) ja tagastab tasakaalustatud puu (samade andmetega).

Kui sa teed puu, mis peale igat lisamist ennast tasakaalustab, võib su funktsioon olla selline:

def get_balanced_tree(tree):
    return tree

Ehk siis kuna su puu "tree" on juba tasakaalus, siis midagi selles funktsioonis tegema ei pea. Kui aga sa puud jooksvalt ei tasakaalusta, saad selles funktsioonis teha uue puu, mis on tasakaalus.