binäärihakupuita

Binäärihakupuut ovat erikoistuneita tietorakenteita, jotka perustuvat solmuihin, joissa jokaisella solmulla on enintään kaksi lasta, joita kutsutaan vasemmaksi ja oikeaksi lapseksi. Niitä käytetään tehokkaasti tietojen hakemiseen, lisäämiseen ja poistamiseen.

Keskeinen ominaisuus binäärihakupuissa on niiden hakupuuominaisuus. Tämä tarkoittaa, että jokaiselle solmulle pätee, että kaikki sen vasemman alipuun solmujen arvot ovat pienempiä kuin solmun arvo, ja kaikki sen oikean alipuun solmujen arvot ovat suurempia kuin solmun arvo. Tämä järjestys takaa, että tiettyä arvoa etsittäessä voidaan nopeasti ohittaa suuri osa puusta.

Yksinkertaisimmassa tapauksessa binäärihakupuu on tyhjä. Jos siinä on solmuja, se koostuu juurisolmusta sekä vasemmasta ja oikeasta alipuusta, jotka ovat myös binäärihakupuita. Hakutoiminto alkaa juurisolmusta. Jos etsittävä arvo on pienempi kuin nykyisen solmun arvo, haku jatkuu vasempaan lapseen. Jos arvo on suurempi, haku jatkuu oikeaan lapseen. Jos arvo on sama, solmu löytyy. Jos etsittävä polku päätyy tyhjään solmuun, arvoa ei löydy puusta.

Binäärihakupuiden käyttökohteita ovat esimerkiksi hakemistot, tietokantojen indeksit ja jäsenyyden tarkistukset. Niiden tehokkuus riippuu kuitenkin puun tasapainosta. Epätasapainoinen puu voi muuttua käytännössä linkitetyksi listaksi, mikä heikentää hakutoimintojen suorituskykyä. Tämän vuoksi käytetään usein itse tasapainottuvia binäärihakupuita, kuten AVL-puita tai punamusta puita, jotka ylläpitävät puun tasapainoa lisäys- ja poisto-operaatioiden aikana.

---