Tietorakenteet, 2. välikoe, kevät 2001 Arvosteluperusteet, tehtävä 1. Olli Lahti Ratkaisun välivaiheita ei tarvinnut esittää, mutta ne otettiin lievästi huomioon virheellisten vastausten arvioinnissa. Puut, jotka tuli piirtää, on esitetty jäljempänä kehystettyinä. Huomattavaa: - Uuden avaimen lisäyspaikka etsitään kulkien juuresta lehtiin päin. Hakupuuominaisuuden tulee olla voimassa koko ajan, ts. minkään solmun vasemmassa alipuussa ei saa esiintyä arvoltaan suurempia avaimia eikä oikessa arvoltaan pienempiä. - Päivitykset ja tarkistukset suoritetaan lisätystä solmusta takaisin juurta kohti edeten. Algoritmi siis korjaa epätasapainot paluumatkalla juureen sitä mukaa kuin havaitsee ne. Liian lähellä juurta ei sovi tehdä kiertoja, jos vika on alempana! - Kierroissa solmujen sisäjärjestys säilyy aina samana - luonnollisesti. Jos (ali)puun juuri muuttuu, jotakin - ainakin tyhjä alipuu - siirtyy tuon juuren toiselle puolelle. 1) Alunperin tyhjään AVL-puuhun viedään ensin avaimet 21, 23, 165, 203, 204 ja 546. Välivaiheet, osa 1: ------------------- 21 21 23 23 23 \ / \ / \ / \ 23 21 165 21 165 21 203 \ / \ 203 165 204 Piirrä AVL-puu näiden lisäysten jälkeen. ************************* * * * 203 * * / \ * * 23 204 * * / \ \ * * 21 165 546 * 2 pistettä * * ========== ************************* 2) Sitten puuhun lisätään vielä avaimet 15, 14, 22, 12 ja 9. Välivaiheet, osa 2: (avaimen 22 lisäyksen seurauksena ------------------- kaksoiskierto oikealle 23:ssa) 203 203 203 203 / \ / \ / \ / \ 23 ... 23 ... 21 ... 21 ... / \ / \ / \ / \ 21 165 15 165 15 23 14 23 / / \ / / \ / \ / \ 15 14 21 14 22 165 12 15 22 165 Nyt avaimen 9 lisäys tuottaa epätasapainon nimenomaan koko puun juureen (203). Suoritetaan yksinkertainen kierto oikealle. Näin 21 nousee koko puun juureksi ja avaimesta 23 alkava alipuu siirtyy uuden juuren oikealle puolelle. Piirrä AVL-puu näiden lisäysten jälkeen. ******************************* * * * 21 * * / \ * * 14 203 * * / \ / \ * * 12 15 23 204 * * / / \ \ * * 09 22 165 546 * 2 pistettä * * ========== ******************************* 3) Lopuksi puu tulkitaankin vain tavalliseksi hakupuuksi ja siitä poistetaan remove-operaatiolla avaimet 203 ja 21. (Kahdesta poisto-operaation vaihtoehtoisesta toteutuksesta tässä käytetään periaatetta: "vasemman alipuun maksimi".) Poistetaan 203. 21 / \ 14 165 / \ / \ 12 15 23 204 / / \ 09 22 546 Poistetaan 21. Piirrä hakupuu näiden poistojen jälkeen. ******************************* * * * 15 * * / \ * * ===> 14 165 * * / / \ * * 12 23 204 * * / / \ * * 09 22 546 * kuva ja seuraava selvitys 2 pistettä * * ========== ******************************* Häviääkö hakupuun AVL-ominaisuus poistojen yhteydessä? Jos häviää, milloin ja miksi se häviää? Hakupuun AVL-ominaisuus menetetään jälkimmäisen poiston yhteydessä. Silloin solmun, jonka avainarvo on 14, vasemman ja oikean alipuun korkeuksien ero jää yli yhden.