Osaisiko joku heittää yksinkertaisen esimerkin (vaikka pseudokoodilla) siitä, millä logiikalla binäärihakupuun rekursiivisen lisäysfunktion yhteydessä saisi myös päivitettyä solmujen alipuiden korkeudet? Oletetaan siis, että solmut ovat tietueita, joilla on varsinaisen datan (esim. kokonaisluku) lisäksi tieto vasemmasta ja oikeasta alipuusta ja niiden korkeuksista (ei koosta). Jollain rekursiivisella menetelmällä tuon varmasti saisi toteutettua, mutta en saa päähäni sitä logiikkaa.
Jos joku haluaa vastata jollain ohjelmointikielellä, niin toivoisin C:tä tai Javaa.
En ole nyt varma mitä tarkoitat alipuun korkeudella, mutta jos se tarkoittaa "korkeimman" haaran "korkeutta", niin eikö haaran korkeus ole aina haaran haaroista "korkeampi" plus yksi.
Eli jos lisätessä etenet puussa ylemmäksi niin takaisin päin tullessa vaan päivität alipuiden korkeudet edellä kuvatun mukaisiksi.
Jos ymmärsin väärin, mitä hait, niin ehkä kannattaisi laittaa nykyinen koodi näkyville.
Jostakin tiedät, milloin se rekursiivinen funktio on saanut arvon lisättyä. Tämän jälkeen palatessa ylemmille tasoille pitää tarkistaa, tuliko päivitetystä alipuusta korkeampi, ja tarvittaessa päivittää ylemmän tason korkeutta. Joka tason korkeudeksi pitää siis asettaa suurempi sen kahden alipuun korkeuksista (plus yksi), mutta toisen alipuun tarkastamisen sijaan voi hyödyntää tietoa, että jos se on aiemmin ollut näistä korkeampi, sen korkeutta on aiemmin käytetty ylemmän tason solmussa. Poistofunktio taas ei voi toimia näin, vaan sen täytyy tarkistaa kummatkin alipuut.
Grez: oikein ymmärsit.
Kiitos neuvoista, tämä selvisi!
Aihe on jo aika vanha, joten et voi enää vastata siihen.