Helsingin yliopisto, University of Helsinki
MOOC.FI

Esimerkki rekursiosta binääripuussa

Seuraavan esimerkin on tarkoitus valottaa, miten rekursiota voi käyttää viikon 6 TMC tehtävissä. Kutsumme solmusta s alkavaksi alipuuksi sitä alipuuta, joka sisältää solmun s lapset ja lapsenlapset jne.

Esimerkiksi jos merkitsemme solmua s seuraavassa kuvassa punaisella:

       0
      / \
     0   0
    / \   \
   0   0   0
  / \
 0   0 
	
niin tällöin solmista s alkava alipuu on seuraavanlainen (väritetty kokonaan punaisella):
       0
      / \
     0   0
    / \   \
   0   0   0
  / \
 0   0 
	

Jos taas s olisi seuraava solmu:

       0
      / \
     0   0
    / \   \
   0   0   0
  / \
 0   0 
niin solmusta s alkava alipuu olisi:
       0
      / \
     0   0
    / \   \
   0   0   0
  / \
 0   0 


Puiden korkeudesta

Rekursiosta on erityisen paljon hyötyä toteuttaessa erilaisia metodeja binääripuille. Tässä esimerkissä katsotaan, miten binääripuun korkeuden laskeminen onnistuu rekursiolla. Meillä on käytössä viikon 6 TMC-pohjia vastaava toteutus puusta. Puu sisältää siis arvon, sekä viittauksen vasempaan ja oikeaan lapseensa.

Tarkastellaampa esimerkkiä, olkoon meillä seuraavanlainen puu:

       0
      / \
     0   0
    / \   \
   0   0   0
  / \
 0   0 
Tämän puun kaikissa solmuissa arvo on 0, arvot voisivat olla jotain ihan muuta vaikuttamatta puun korkeuteen. Arvoja voi kuitenkin käyttää hyödyksi visualisoimaan tämän esimerkin pointtia: asetetaan ylläolevan puiden solmujen arvoksi näistä solmuista alkavan alipuun korkeus. Nyt puumme näyttää tältä:
       3
      / \
     2   1
    / \   \
   1   0   0
  / \
 0   0 
Ylläolevasta visualisaation perusteella näyttäisi siltä, että puun korkeus on aina 1 + korkeamman alipuun (oikea/vasen) korkeus. Eli esimerkiksi kun tarkastellaan punaisella merkittyä solmua seuraavassa kuvassa:
       3
      / \
     2   1
    / \   \
   1   0   0
  / \
 0   0 
Sen vasemman alipuun korkeus on 1, oikean alipuun korkeus on 0 ja punaisesta solmusta alkavan alipuun korkeus on
max(1, 0) + 1 = 2.
Syy tähän on varsin luonnollinen, jos haluamme päästä juurisolmuun puun juuresta, niin joudumme ensin kulkemaan toisen sen alipuiden juurien kautta. Täten saamme siis puun korkeudelle seuraavan kaavan:
korkeus(puu) = max(korkeus(puu.vasen), korkeus(puu.oikea)) + 1.
Eli jos tiedämme puun kummankin alipuun korkeuden, niin voimme laskea itse puun korkeuden. Tässä rekursio astuu kuvaan.


Puun korkeuden laskeminen koodina

Edellisen analyysin perusteella voisimme kuvitella, että puun korkeuden laskisi seuraava koodinpätkä:

public static int korkeus(Puu puu){
    return 1 + Math.max(korkeus(puu.vasen), korkeus(puu.oikea));
}

Kuitenkin jos koitat ajaa kyseistä koodia, niin huomaat ettei se toimi. Tämä johtuu siitä, että toinen rekursiivisen ratkaisun tärkeistä osista, pohjatapaus , on jätetty kokonaan huomioimatta. Emme koskaan saa koskaan oikeasti laskettua yhdenkään alipuun korkeutta, vaan yritämme aina jokaisen solmun kohdalla laskea ensin sen lapsien alipuiden korkeudet. Tämä johtaa ongelmiin viimeistään siinä vaiheessa, kun yritämme laskea sellaisen alipuun korkeutta, jota ei ole olemassa. Sopiva pohjatapaus saadaan kun muistetaan, että lehtisolmusta alkavan alipuun korkeus on 0 .

Eli nyt koodimme muuttuu muotoon

public static int korkeus(Puu puu){
    if (puu.oikea == null && puu.vasen == null)
        return 0;
    return 1 + Math.max(korkeus(puu.vasen), korkeus(puu.oikea));
}
joka on jo hyvin lähellä toimivaa versiota. Jos ainoastaan toinen puun alipuista on olemassa, niin koodimme yrittää kuitenkin laskea kummankin alipuun korkeudet. Tämä saadaan kierrettyä helposti lisäämällä sopivat tarkastukset:
public static int korkeus(Puu puu){
    if (puu.oikea == null && puu.vasen == null) {
        return 0;
    }

    int h_vasen = -1;
    int h_oikea = -1;
    
    if (puu.vasen != null) {
        h_vasen = korkeus(puu.vasen);
    }

    if (puu.oikea != null) {
        h_oikea = korkeus(puu.oikea);
    }

    return 1 + Math.max(h_vasen, h_oikea);
}
Tämä koodi tolella laskee puun korkeuden. Visualisoidaampa tämän koodin toimintaa esimerkkipuullamme. Asetetaan kaikkien solmujen arvoksi x ja muutetaan niitä vastaamaan aina kyseisestä solmusta alkavan alipuun korkeutta sitä mukaan kun saamme korkeudet laskettua. Tietyllä hetkellä käsiteltävää solmua merkitsemme punaisella värillä.

Seuraava visualisaatio on melko pitkä, mutta se toivottavasti avaa rekursion toimintaa.


1. x / \ x x / \ \ x x x Puun vasen alipuu on olemassa, lasketaan siis sen korkeus. / \ x x
2. x / \ x x / \ \ x x x Puun vasen alipuu on olemassa, lasketaan siis sen korkeus. / \ x x
3. x / \ x x / \ \ x x x Puun vasen alipuu on olemassa, lasketaan siis sen korkeus. / \ x x
4. x / \ x x / \ \ x x x Puulla ei ole vasenta, eikä oikeaa alipuuta, joten sen korkeus on 0. / \ x x
5. x / \ x x / \ \ x x x Puun oikea alipuu on olemassa, lasketaan siis sen korkeus. / \ 0 x
6. x / \ x x / \ \ x x x Puulla ei ole vasenta, eikä oikeaa alipuuta, joten sen korkeus on 0. / \ 0 x
7. x / \ x x / \ \ x x x Puun oikean ja vasemman alipuun korkeudet on laskettu, joten sen korkeus voidaan laskea. / \ 0 0
8. x / \ x x / \ \ 1 x x Puun oikea alipuu on olemassa, lasketaan siis sen korkeus. / \ 0 0
9. x / \ x x / \ \ 1 x x Puulla ei ole vasenta, eikä oikeaa alipuuta, joten sen korkeus on 0. / \ 0 0
10. x / \ x x / \ \ 1 0 x Puun oikean ja vasemman alipuun korkeudet on laskettu, joten sen korkeus voidaan laskea. / \ 0 0
11. x / \ 2 x / \ \ 1 0 x Puun oikea alipuu on olemassa, lasketaan siis sen korkeus. / \ 0 0
12. x / \ 2 x / \ \ 1 0 x Puun vasenta alipuuta ei ole olemassa. / \ 0 0
13. x / \ 2 x / \ \ 1 0 x Puun oikea alipuu on olemassa, lasketaan siis sen korkeus. / \ 0 0
14. x / \ 2 x / \ \ 1 0 x Puulla ei ole vasenta, eikä oikeaa alipuuta, joten sen korkeus on 0. / \ 0 0
15. x / \ 2 x / \ \ 1 0 0 Puun oikean ja vasemman alipuun korkeudet on laskettu, joten sen korkeus voidaan laskea. / \ (Muista: vasemman alipuun korkeus on nyt -1, sillä sitä ei ollut olemassa!!!) 0 0
16. x / \ 2 1 / \ \ 1 0 0 Puun oikean ja vasemman alipuun korkeudet on laskettu, joten sen korkeus voidaan laskea. / \ 0 0
17. 3 / \ 2 1 / \ \ 1 0 0 Puun korkeuden laskeminen on saatu valmiiksi. / \ 0 0

Mutta miten tämä hyödyttää viikon 6 TMC tehtävissä?

Viikolla 6 ei ole (ainakaan suoraan) tehtävänä laskea binääripuun korkeutta. Tämä tapa laskea puun korkeus tuo kuitenkin esille erittäin tärkeän ajattelutavan ja on siksi mielestäni hyödyllinen esimerkki. Laskemme puun korkeuden laskemalla ensin sen alipuiden korkeudet, ja alipuiden korkeuksien avulla saamme laskettua alkuperäisen puun korkeuden. Monet puuihin liittyvistä ongelmista rakteavatkin juuri tätä ajattelutapaa hyödyntäen, esimerkkeinä:

Lukijan on syytä miettiä, miten yllämainitut ongelmat rakteavat rekursion avulla. Puutehtävää tehdessä kannattaa siis miettiä, voisiko kyseisen ongelman ratkaista ratkaisemalla ongelman ensin puun alipuille ja sitten niitä hyödyntäen alkuperäiselle puulle.

Vaikka rekursio saattaa vielä tuntua haastavalta tekniikalta, ei sen tärkeyttä algoritmeissa voi liioitella. Rekursion haastavuuteen, kuten vähän kaikkeen muuhunkin, auttaa yleensä harjoittelu. Ainakin TMC tehtävät 6.1 ja 6.3 kannattaa tehdä rekursiota hyväksikäyttäen, vaikka keksisitkin rekursiota käyttämättömän ratkaisun.