Binäärihakupuissa

Binäärihakupuut, englanniksi binary search trees (BST), ovat tietorakenteita, jotka mahdollistavat tehokkaan tietojen tallennuksen ja hakemisen. Ne perustuvat puurakenteeseen, jossa jokaisella solmulla on korkeintaan kaksi lasta, vasen ja oikea. BST:n keskeinen ominaisuus on sen järjestysperiaate: vasemman lapsen arvo on aina pienempi kuin vanhemman solmun arvo, ja oikean lapsen arvo on aina suurempi. Tämä järjestys pätee rekursiivisesti koko puuhun.

Kun etsitään arvoa binäärihakupuusta, aloitetaan juurisolmusta. Jos etsittävä 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, että arvoa ei löydy puusta.

Binäärihakupuiden etuja ovat niiden yksinkertaisuus ja tehokkuus keskimääräisessä tapauksessa. Haku-, lisäys- ja poisto-operaatioiden aikakompleksisuus on O(log n), missä n on solmujen määrä, olettaen että puu on tasapainoinen. Epätasapainoisessa puussa, esimerkiksi jos solmut lisätään aina kasvavassa tai laskevassa järjestyksessä, puu voi degeneroitua linkitetyksi listaksi, jolloin aikakompleksisuus voi kasvaa O(n):iin. Tasapainotettuja binäärihakupuita, kuten AVL-puut ja punamusta puut, käytetään tämän ongelman ratkaisemiseksi.