3 (a)

Lehisolmut poistetaan laittamalla vanhempi viittaamaan NIL:iin.
Yksilapsiset poistetaan korvaamalla poistettava lapsellaan.
Kaksilapsiset poistetaan korvaamlla solmun sisältö seuraajalla (oikean alipuun minimi) 
ja poistamalla seuraajan tallettanut solmu.

     5                 
   /   \
  4     10
 /     /  \
2     7   12
       \    \  
        8    14    

Kaksilapsinen: korvautuu seuraajallaan eli seiskalla. Seiskan tallettanut solmu poistuu 
ja korvautuu lapsellaan

     7                 
   /   \
  4     10
 /     /  \
2     8   12
            \  
            14 

0.5p periaate, 0.5p sovellus


3 (b)

AVL-lisätään solmu samoin kuten normaaliin hakupuuhun, eli lehdeksi sille paikalle mistä 
search solmun löytäisi jos se olisi puussa.

Lisäys saattaa viedä puun epätasapainoon. Mahdollinen epätasapaino löytyy polulla lisätystä 
juureen. Kuljetaan polku läpi ja jos havaitaan solmun olevan epätasapainossa, tehdään 
kierto-operaatiot jotka palauttavat tasapainon. Kiertoja on 4 erilaista riippuen epätasapainon
syystä. 

lisätään 9:

     5                 
   /   \
  4     10
 /     /  \
2     7   12
       \    \  
        8    14   
         \
          9

7 epätasapainossa. syy oikean lapsen oikea alipuu => kierretään 7 oikealle

     5                 
   /   \
  4     10
 /     /  \
2     8   12
     / \    \  
    7   9   14   
         
lisätään 6:

     5                 
   /   \
  4     10
 /     /  \
2     8   12
     / \    \  
    7   9   14   
   /
  6

juuri epätasapainossa. syy oikean lapsen vasen alipuu => kaksoiskierto

ensin kierretään 10 oikealle

     5                 
   /   \
  4     8
 /     /  \
2     7   10
     /   /  \  
    6   9   12  
              \
              14

sitten 5 vasemmalle

                     
      
         8
      /     \
     5      10
    / \    /  \  
   4   7  9   12  
  /   /         \
 2   6          14

periaate 1p, molemmat lisäykset 1p
yleinen virhe oli unohtaa kertoa mistä kohtaa puuta tasapainoehdon mahdollinen rikkoutuminen pitää tarkastaa (matkalla lisätystä juureen), tämä vähensi 0.5p


3 (c)

Strategia: 
- mitataan ensin puun korkeus, eli tasojen määrä. 
- tämän jälkeen tehdään puun rekursiivinen läpikäynti joka muistaa millä ollaan menossa
- kun taso on sama kun puun korkeus, tulostetaan solmun sisältö
- tason muistaminen toteutetaan siten, että lasketaankin niiden tasojen määrä mikä on 
  mentävä alaspäin että ollaan alimmalla tasolla

pääohjelma:

korkeus = laskeKorkeus( T.root )
eteneJaTulosta(T.root,  korkeus )

metodit:

laskekorkeus(solmu)
  if solmu==NIL 
    return -1
  return 1 + max( laskeKorkeus(solmu.left), laskeKorkeus(solmu.right) ) 

eteneJaTulosta( solmu, korkeus )
  if solmu==NUL 
    return
  if korkeus == 0 
    print solmu.key
    return
  eteneJaTulosta( solmu.left, korkeus-1 )
  eteneJaTulosta( solmu.right, korkeus-1 )

Algoritmi sisältää kahdesta peräkkäin suoritettavasta melkein samanlaisesta osasta. 
Molemmissa rekursiivisen metodin runko vakioiaikainen. 

Metodia kutsutaan (pahimmassa tapauksessa) kaikille puun solmuille. Korkeuden 
laskemisessa itseasiassa myös lehtien olemattomille lapsille. Kutsuja on siis O(n) kpl 
jos puun solmumäärä on n. Yhteensä aikavaatiuus siis O(n)

Pahimmillaan rekursiivisia metodeja on yhtä aikaa käynnissä puun korkeuden verran, eli jos 
merkitään puun korkeutta h:lla, on algoritmin tilavaativuus rekursiosta johtuen O(n)


Pisteytys:

algoritmi oikein 3p
aika- ja tilavaativuus 1p

miinusta väärin toimivista algoritmeista, vakaavuudesta riippuen
esim: kaikkien lehtien tulostus -3p

HUOM: tehtävän voi myös ratkaista käymällä puuta läpi esim. jonon avulla tasoittain, viikon 5 
laskaritehtävän 4 tyyliin.