binäärihakupuussa

Binäärihakupuu, lyhyesti BST (Binary Search Tree), on eräänlainen puurakenne, jota käytetään tietokantojen ja muiden tietojenkäsittelysovellusten tehokkaaseen hakemiseen. BST:ssä jokaisella solmulla on korkeintaan kaksi lasta, vasen ja oikea lapsi. Tärkein ominaisuus on se, että jokaiselle solmulle pätee seuraava sääntö: kaikki vasemmassa alipuussa olevat solmut ovat pienempiä kuin solmu itse, ja kaikki oikeassa alipuussa olevat solmut ovat suurempia.

Tämä ominaisuus tekee binäärihakupuusta erittäin tehokkaan hakuoperaatioissa. Kun etsitään tiettyä arvoa, aloitetaan juurisolmusta. Jos etsitty arvo on pienempi kuin nykyisen solmun arvo, siirrytään vasempaan lapseen. Jos arvo on suurempi, siirrytään oikeaan lapseen. Tätä prosessia jatketaan, kunnes arvo löytyy tai saavutetaan tyhjä solmu, mikä tarkoittaa, ettei arvoa löydy puusta.

BST:itä käytetään usein tehokkaiden hakualgoritmien toteuttamiseen, kuten avain-arvo -parien tallentamiseen ja hakemiseen. Niitä voidaan käyttää myös lajittelussa ja muiden tietorakenteiden rakentamisessa. BST:iden tehokkuus riippuu kuitenkin siitä, kuinka tasapainoisesti ne ovat rakentuneet. Huonosti tasapainotettu puu voi heikentää hakuoperaatioiden suorituskykyä merkittävästi, lähestyen pahimmillaan lineaarista hakua. Siksi on kehitetty erilaisia itseään tasapainottavia binäärihakupuita, kuten AVL-puut ja punamustat puut, jotka ylläpitävät puun tasapainoa automaattisesti lisäys- ja poisto-operaatioiden yhteydessä.