581325-0 Tietorakenteet, 2. kurssikoe 10.4.2002/AW

1. 1. Alunperin tyhjään AVL-puuhun viedään ensin avaimet 18, 21, 30, 15, 10, 5. Piirrä AVL-puu näiden lisäysten jälkeen. Sitten puuhun lisätään vielä avaimet 42, 44, 19, 20 ja 27. Piirrä AVL-puu näiden lisäysten jälkeen.

      Lopuksi puu tulkitaankin vain tavalliseksi hakupuuksi ja siitä poistetaan remove-operaatiolla avain 15. Piirrä hakupuu näiden poistojen jälkeen,

      • kun kahdesta poisto-operaation vaihtoehtoisesta toteutuksesta käytetään periaatetta: "vasemman alipuun maksimi",
      • kun kahdesta poisto-operaation vaihtoehtoisesta toteutuksesta käytetään periaatetta: "oikean alipuun minimi".
      Häviääkö hakupuun AVL-ominaisuus näiden poistojen yhteydessä? Miksi tai miksi ei?

   2. Selitä ja toteuta Java-metodina AVL-puun operaatio kaksoiskierto vasemmalle. Käytössäsi ei ole valmiina yksinkertaisen kierron operaatioita.

                                                                 (8 pistettä)
   

2. Käytössäsi on rajapintaluokka Hashable, joka lupaa toteuttajiensa sisältävän hajauttimen public int hash(int taulunKoko). Käytössäsi on myös luokka Lista. Täsmennä (so. luonnehdi, älä ohjelmoi) sen operaatiot.

   Toteuta avoin hajautus Java-luokkana:

   • public AvoinHajautus (int koko) luo pyydetyn kokoisen hajautustaulun
   • public void insert(Hashable arvo)
     lisää "arvon" hajautustauluun; jos jo löytyi, mikään ei muutu
   • public void remove(Hashable arvo)
     poistaa "arvon" hajautustaulusta; jos ei löydy, mikään ei muutu
   • public Hashable find(Hashable arvo)
     palauttaa viitteen olioon, joka on equals-sama "arvon" kanssa; jos ei löydy, palautetaan null.

                                                                 (8 pistettä)
   

3. 1. Selitä kekojärjestämisen idea ja toteutus. Viimeisteltyä Java-ohjelmaa ei tarvitse laatia, mutta lukijan on ymmärrettävä sekä keon taulukkoon tallettamisen idea, että myös järjestettävän taulukon osien tulkinta milloin keoksi, milloin tavalliseksi taulukoksi.

   2. Vertaile ja selitä lisäys-, keko- ja pikajärjestämisen ominaisuuksia, hyvyyttä ja käyttökelpoisuutta sekä teoriassa että käytännössä.

                                                                 (8 pistettä)