Aineistotehtävä

Binääripuu on tietorakenne, jolla on useita sovelluksia. Esimerkiksi binäärietsintäpuita käytetään nimensä mukaisesti tiedon hakemiseen puusta.
Binääripuu määritellään seuraavasti. Binääripuu joko ei sisällä solmuja, tai se koostuu juurisolmusta ja kahdesta erillisestä solmujoukosta: vasemmasta ja oikeasta alipuusta. Vasen ja oikea alipuu ovat myös binääripuita. Jos binääripuu ei sisällä solmuja, se on tyhjä puu. Binääripuissa on äärellinen määrä solmuja.
Jos binääripuun jollain solmulla x on ei-tyhjä vasen alipuu t, sanotaan alipuun t juurisolmua solmun x vasemmaksi lapseksi. Vastaavasti ei-tyhjän oikean alipuun juurisolmu on solmun xoikea lapsi. Jos toinen tai molemmat alipuista ovat tyhjiä, puuttuu solmulta x lapsi.
Solmuja, joilta puuttuu kumpikin lapsi, kutsutaan lehtisolmuiksi. Jos solmulla x on lapsi y, on solmu x lapsen y vanhempi. Juurisolmu on ainoa solmu, jolla ei ole vanhempaa. Kullakin solmulla on korkeintaan yksi vanhempi. Muut solmut kuin lehtisolmut ja juuri ovat sisäsolmuja.

Binääripuita piirrettäessä tulee huomioida, että jos jollain binääripuuhun kuuluvalla solmulla on vain yksi lapsisolmu, tulee lapsisolmu selkeästi sijoittaa joko vasempaan tai oikeaan alipuuhun. Kaksi puuta eivät ole samoja, vaikka niiden ainoa ero olisi yhden lapsisolmun sijoittuminen joko vasempaan tai oikeaan alipuuhun.

Kuvassa 1 (a) on binääripuu. Siinä juurisolmu sisältää luvun 6. Lehtiä ovat solmut, jotka sisältävät luvut 2, 5 ja 8. Loput solmut ovat sisäsolmuja. Solmu 3 on solmujen 2 ja 5 vanhempi ja solmun 6 lapsi. Solmuun sisällytettyä tietoa sanotaan avaimeksi ¾ tähän puuhun on talletettu avaimet 2, 3, 5, 6, 7 ja 8. Kuten edellä, solmuun viitataan suoraan sen avaimella. Siten esimerkiksi solmusta 3 ja solmusta 5 puhuttaessa tarkoitetaan kahta solmua, joista toiseen on tallennettu avain 3 ja toiseen avain 5.

Kuva 1. Binääripuuesimerkkejä.



 
 

Myös kuvan 1 (b) ja (c) puut ovat binääripuita. Huomaa, että (a) ja (b) -kohtien puut eivät ole samoja.

Puu on binäärietsintäpuu, mikäli sen kaikille solmuille x pätee, että solmun x vasemman alipuun solmujen avaimet ovat pienempiä kuin avain x. Vastaavasti tulee solmun x oikean alipuun avainten olla suurempia kuin avain x. Kuvassa 1 (a) ja (c) puut ovat binäärietsintäpuita.

Alla oleva ohjelma etsii puusta annetun avaimen a. Se palauttaa avaimen a sisältävän solmun puusta, jonka juurisolmu on s. Lisäksi palautetaan solmun a vanhempi y. Jos avainta a ei löydy puusta, niin palautetaan tyhjä solmu x ja solmu y, johon päädyttiin avainta a etsittäessä. Myös y voi olla tyhjä, mikäli puu on tyhjä tai mikäli avain on juuressa.

Avaimen a etsiminen puusta, jonka juurisolmu on s.

    Sijoita y := tyhjä.
    Sijoita x := s.
    Toista rivejä (4)-(8) niin kauan, kun solmu x¹ tyhjä ja a ¹ solmu x
            Sijoita y := x.

            Jos a < solmu x, niin

                    sijoita x := solmun x vasemman alipuun juurisolmu,

            muutoin

                    sijoita x := solmun x oikean alipuun juurisolmu.

    Palautetaan solmu x ja sen vanhempi y.

Etsitään kuvan 1 (a) binäärietsintäpuusta avainta 5. Puun juurisolmu s sisältää avaimen 6. Aluksi asetetaan solmun x arvoksi s eli 6 ja alustetaan solmu y tyhjäksi. Koska solmu x ei ole tyhjä ja avaimet eivät ole samoja, sijoitetaan rivillä (6) muuttujaan x vasemman alipuun juurisolmu (solmu 3).

 
 

Nyt rivillä (3) solmu x ei ole tyhjä eivätkä avaimet ole samoja, joten rivillä (8) tulee muuttujan x arvoksi solmu 5. Koska avaimet ovat samoja, ei enää toisteta rivejä (4)-(8). Siis rivillä (9) palautetaan solmu x (jonka avain vastaa etsittyä avainta) ja sen

vanhempi eli solmu 3 (muuttujan y arvo).
 
 

Jos etsittäisiin avainta 4, niin riveillä (4)-(8) tulisi muuttujan x arvoksi lopulta vasemman alipuun juurisolmu. Koska solmulla 5 ei ole alipuuta, tulisi muuttujan x arvoksi tyhjä. Muuttujan y arvoksi tulisi solmu 5. Nämä solmut x ja y myös palautettaisiin vastaukseksi (eli puusta ei löydy avainta 4 ja etsintä loppuisi solmun 5 kohdalla).
 
 

Esitetään seuraavaksi avaimien lisäys binääripuuhun. Ideana on etsiä aluksi sopiva kohta, johon lisättävän avaimen sisältävä solmu voidaan liittää. Sen jälkeen solmu liitetään paikalleen joko juureksi tai vasemmaksi tai oikeaksi lapseksi. Sopivan kohdan etsimisessä voidaan käyttää edellä esitettyä avaimen etsintää.
 
 

Avaimen a sisältävän solmun lisäys binääripuuhun t.

    Etsitään avainta a puusta t aiemmin esitetyllä menetelmällä. Olkoon x menetelmän palauttama solmu ja y sen vanhempi.
    Jos solmu y on tyhjä, niin
            aseta puun t juureksi solmu a,
    muutoin jos solmu a < solmu y, niin

            liitä solmun y vasemmaksi lapseksi solmu a,

    muutoin

            liitä solmun y oikeaksi lapseksi solmu a.
     
     

Huomaa, että solmua x ei tarvita ohjelman loppuosan suorittamisessa. Se on mukana, koska avaimien etsimiseen käytettävä ohjelma palauttaa kaksi solmua (solmut x ja y).

 
 

Esimerkiksi kuvan 1 (a) binääripuu on muodostettu lisäämällä alkujaan tyhjään puuhun siinä esiintyvät avaimet järjestyksessä 6, 7, 8, 3, 2 ja 5. Toinen mahdollinen järjestys on 6, 3, 7, 2, 5 ja 8. Jos puuhun vielä lisätään solmu, jonka avain on 4, ensimmäisellä rivillä etsitään ensin solmu 5 (muuttujan y arvo). Tämän jälkeen riveillä (2)-(7) sijoitetaan solmu 4 solmun 5 vasemmaksi lapseksi.
 
 
 
 
 

Kysymykset

      Mikä on vieressä olevan puun juurisolmu?
      Mitkä ovat vieressä olevan puun sisäsolmuja?
      Mitkä ovat vieressä olevan puun lehtisolmuja?

       
      Mitkä kuvan 2 (a)-(e) kohdista ovat binääripuita. Perustele, miksi loput kuvan 2 (a)-(e) kohdista eivät ole binääripuita.
      Mitkä kuvan 2 (a)-(e) kohdista ovat binäärietsintäpuita. Perustele, miksi muut binääripuut eivät ole binäärietsintäpuita.
       
      Kuva 1. Binääripuuesimerkkejä.

      Kuva 2. Kuva kysymykseen 2.

       
    Piirrä kaikki mahdolliset avaimien 1, 2 ja 3 binäärietsintäpuut (kunkin näistä kolmesta avaimesta on esiinnyttävä täsmälleen kerran kussakin puussa).

     

    Muodosta binäärietsintäpuut (a) ja (b) lisäämällä aluksi tyhjiin puihin (a)- ja (b)-kohdissa luetellut avaimet annetussa järjestyksessä (aineistossa esitetyllä avainten lisäysmenetelmällä). Piirrä jokainen vaihe selkeästi paperille. (Esimerkiksi (a)-kohdassa sinun tulee piirtää neljä erillistä binäärietsintäpuuta: ensin puu, jossa on avain 4, sitten puu, jossa avaimet 4 ja 3, jne.)
     

      Avaimet: 4, 3, 2 ja 1.
      Avaimet: 5, 2, 4, 8, 10, 9, 3, 7, 1 ja 6.