Binääripuu
Binääripuu on tietojenkäsittelytieteessä käytetty järjestetty puumainen tietorakenne, jonka jokaisella solmulla voi olla enintään kaksi lapsisolmua. Yleensä näitä lapsisolmuja kutsutaan nimillä vasen ja oikea. Solmua, jolla ei ole yhtään lapsisolmua kutsutaan lehdeksi.
Binääripuiden yleisin käyttötapa ovat binääriset hakupuut sekä binääriset keot.
Binääripuun määritelmä muokkaa
Suunnattu kaari liittää vanhemman lapseen.
Solmu, jolla ei ole lapsisolmuja, on lehtisolmu.
Solmun n syvyys on matka juuresta solmuun. Joukkoa solmuja tietyllä syvyydellä kutsutaan joskus tasoksi.
Solmun n korkeus on matka solmusta sen kaukaisimpaan lehteen.
Solmuja, joilla on yhteinen vanhempi, kutsutaan sisaruksiksi.
Jos on olemassa polku solmusta p solmuun q, niin p on q:n esivanhempi ja q on p:n jälkeläinen.
Solmun koko on sen jälkeläisten lukumäärä solmu itse mukaan lukien.
Binääripuiden tyypit muokkaa
Binääripuu on juurellinen puu, jossa jokaisella solmulla on enintään kaksi lasta.
Kokonainen tai aito binääripuu on juurellinen puu, jossa jokaisella solmulla on nolla tai kaksi lasta.
Täydellinen binääripuu on juurellinen puu, jossa jokainen lehti on samalla syvyydellä. Toisen määritelmän mukaan täydellinen binääripuu on puu, jolla on jokainen taso alinta lukuun ottamatta täynnä ja alimman tason lehdet on järjestetty vasemmalle. Tällaista binääripuuta kutsutaan usein melkein täydelliseksi binääripuuksi.