581325-0 Tietorakenteet, 2. välikoe 13.4.2000/AW

1. Alunperin tyhjään AVL-puuhun viedään ensin avaimet 15, 16, 17, 18, 19 ja 20. Piirrä AVL-puu näiden lisäysten jälkeen.

   Sitten puuhun lisätään vielä avaimet 9, 8, 7, 6, 5 ja 4. Piirrä AVL-puu näiden lisäysten jälkeen.

   Lopuksi puu tulkitaankin vain tavalliseksi hakupuuksi ja siitä poistetaan remove-operaatiolla avaimet 18, 7 ja 19. Piirrä hakupuu näiden poistojen jälkeen.

   Hävisiko hakupuun AVL-ominaisuus poistojen yhteydessä? Jos hävisi, milloin ja miksi se hävisi?

                                                                 (8 pistettä)
   

2. Rajapintaluokka Hashable on määritelty seuraavasti:

     public interface Hashable {
       public int hash(int taulunKoko);
     }
   

   Käytössäsi on luokka Lista listojen toteuttamiseen. Luokasta ei tunneta muuta kuin operaatiot:

     public Lista()   luo tyhjän listan
   
     public boolean insert(Hashable alkio, int paikka)
                lisää "alkion" "paikka"-kohdassa olevan alkion seuraajaksi;
                0:n seuraaja tarkoittaa listan alkua; palauttaa true, jos
                onnistui, false, jos "paikka" oli mahdoton
   
     public Hashable find(Hashable alkio) 
                palauttaa viitteen ensimmäiseen löytyvään "alkioon",
                palauttaa null, jos ei löydy
   
     public boolean remove(Hashable alkio) 
               poistaa ensimmäisen listasta löytyvän "alkion";
               palauttaa false, jos poistettavaa ei löydy 
   

   Toteuta avoin hajautusrakenne luokkana AvoinHajautus. Rakenteeseen talletetaan Hashable-olioita. Yhteentörmänneiden listat toteutetaan Lista-luokan ilmentyminä. Tietorakenne AvoinHajautus. muodostuu operaatioista (4 kpl):

     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. • Selitä esimerkein miten binäärikeon lisäysoperaatio toteutetaan.

   • Mikä on binäärikeon lisäysoperaation aikavaativuus (O-luokkana) pahimmassa tapauksessa? Entä keskimääräisessä tapauksessa?

   • Binäärikeon alkiot ovat Comparable-olioita:

       public interface Comparable {
         public int compareTo(Object toinen);
       }
     

     Ohjelmoi binäärikeon operaatio:

       public boolean insert(Comparable alkio)
          lisää parametrina saadun olion kekoon; metodi palauttaa true, jos
          lisäys onnistui, false, jos keko oli täynnä 
     

                                                                 (9 pistettä)