Binäärihakupuiden

Binäärihakupuu, tai englanniksi Binary Search Tree (BST), on eräänlainen datan rakennetyyppi, joka perustuu solmuihin. Kuten nimestä voi päätellä, jokaisella solmulla on enintään kaksi lasta, joita kutsutaan vasemmaksi ja oikeaksi lapseksi. Tämän rakenteen keskeinen ominaisuus on järjestyssääntö: jokaisen solmun vasemmalla puolella olevan alipuun kaikki arvot ovat pienempiä kuin solmun oma arvo, ja oikealla puolella olevan alipuun kaikki arvot ovat suurempia. Juurisolmulla on koko puun pienin tai suurin arvo riippuen tarkasta määritelmästä, mutta yleensä se on kokoelman pienin arvo.

Binäärihakupuita käytetään tehokkaasti tiedon tallentamiseen ja hakemiseen. Kun etsitään tiettyä arvoa, aloitetaan juurisolmusta. Jos etsitty arvo on pienempi kuin nykyisen solmun arvo, siirrytään vasempaan lapseen. Jos se on suurempi, siirrytään oikeaan lapseen. Tätä prosessia jatketaan, kunnes arvo löytyy tai puu on käyty läpi. Keskimäärin haku, lisäys ja poisto ovat O(log n) aikakompleksisuudeltaan, missä n on solmujen määrä, mikä tekee niistä erittäin tehokkaita suurille datamäärille. Kuitenkin pahimmassa tapauksessa, jos puu on vinoutunut (esimerkiksi jos elementit lisätään jo järjestyksessä), aikakompleksisuus voi laskea O(n):ään, mikä vastaa linkitettyä listaa. Tämän takia tasapainotettuja binäärihakupuita, kuten AVL-puita tai punamusta-puita, käytetään usein parantamaan suorituskykyä.