Harjutus

Teema: Kahendotsingupuu

Ülesanne 1
Antud võtmete hulk (mitte lisamise järjekord!!): {1, 4, 5, 10, 16, 17, 21}.
Moodusta nendest kaks kahendotsingupuud:
kõrgusega 2 
kõrgusega 3
Milline puu tekib, kui paigutada need võtmed puusse sellises järjekorras: 5, 1, 4, 16, 10, 17, 21?
Mis on puu kõrgus?

Kirjuta viimasena joonistatud puu sisu välja keskjärjekorras (inorder), eesjärjekorras (preorder) ja 
lõppjärjekorras (postorder) (Puude loengumaterjal!).

Ülesanne 2
Paigutame rühma eesnimede järgi kahendotsingupuusse. Sama eesnimega üliõpilased järjestuvad perekonnanime esitähe järgi. Igaüks hoolitseb selle eest, et ta õigesse kohta satuks.

Ülesanne 3
Kuidas otsid puust mõnda nime, mis olemas on (nt enda nime)? Kuidas saad aru, et nime Maali puus ei ole?

Ülesanne 4
AVL puu loomiseks ja tasakaalustamiseks lisame puusse võtmed järgmises järjekorras: 
3, 6, 7, 1, 2, 4, 5, 8

Ülesanne 5
Vaatame üle puna-musta puu reeglid (slaid 28) ja pööramise võtted(slaid 33).
Veebiaadressil:
http://www.cs.usfca.edu/~galles/visualization/RedBlack.html
on puna-musta puu animatsioon - vaatame ja mängime sellega.

Proovime kõigepealt lisada arvud järgmiselt:
50 - 25 - 15 - 10 - 12

Leidke sobivad arvulised väärtused, mida puusse lisada, et puusse lisanduvad tipud tekitaksid tasakaalustamise 
vajaduse peegelpildis.

1. olukord - ainult värvitakse
2. olukord - pööre lapse ja isa juures + värvimine
3. olukord - pööre isa ja vanaisa juures