Hakupuu on tietorakenne, jota käytetään tietokoneohjelmoinnissa sisältämään ja järjestämään tietoluettelo. Jokainen hakupuu koostuu tilatusta solmukohdasta. Nämä solmut voidaan yhdistää nollaan tai useampaan muuhun Yksittäiset solmut sisältävät joitain tietoja sekä linkkejä muihin solmuihin. Puun solmuissa olevat tiedot on usein järjestetty jollakin tavalla, jotta tehokkaat algoritmit voivat etsiä, lisää ja poista solmut helposti.
Hakupuun solmut on kuvattu neljällä tärkeällä termillä. Puun yläosaa, jossa ensimmäinen solmu sijaitsee, kutsutaan juuriksi. Jos solmu sisältää linkkejä -solmuja, tätä solmua kutsutaan vanhemmaksi. Vanhemman alla olevia solmuja kutsutaan lapsiksi ja kaikkia solmuja, joissa ei ole lapsisolmuja, kutsutaan lehtiä. juurisolmu tunnistetaan, koska sillä ei ole vanhempaa, ja lehtisolmuilla ei ole lapsia.
Ohjelma pystyy siirtymään puuta etsien tietoja aloittamalla tietystä solmusta, suorittamalla ehdollisen tarkistuksen ja siirtymällä sitten seuraavaan loogiseen solmuun, jos vaaditut tiedot eivät ole käytettävissä. , tämä haku voi kestää vaihtelevan ajan. Jos hakupuu järjestetään solmujen lisäämis- ja poistoprosessin aikana, haku voi olla erittäin nopea. Kun puu kootaan satunnaisesti, on lajittelematon tai sallii useita vanhempia, haku voi kestää hyvin kauan.
Yksi tekijä, joka vaikuttaa hakupuiden käyttöön, on tasapaino. Tasapainoinen puu on sellainen, jossa sekä juurisolmun oikea että vasen lapsi sisältävät joko saman syvyyden lapsisolmuja tai ovat yhden solmun lukumäärän sisällä Puun syvyys on solmujen lukumäärä puun alimmasta lehdestä juuriin. Epätasapainossa olevassa puussa voi olla kaikki solmut vain toisella puolella tai kaikki solmut on järjestetty lineaarisesti ilman oksia.Kun puun syvyys kasvaa, hakualgoritmien nopeus voi laskea dramaattisesti.
On olemassa tietyntyyppisiä hakupuita, joita kuvataan itsetasapainottaviksi. Nämä puut käyttävät toimintoja, kuten puiden kierto, tasapainon ylläpitämiseksi ja lehtien tietojen järjestyksen säilyttämiseksi. puun kierto voi hidastaa ohjelmaa, kun lisätään ja poistetaan solmuja, tätä vastustaa tietojen noutamisen nopeus.
Vaikka hakupuita on monenlaisia, yleisin puun tietorakenne on binäärinen hakupuu. Tämä tietotyyppi koostuu solmuista, joissa kussakin on nollasta kahteen alisolmua. On vain yksi juurisolmu, ja kaikki puun lehdet järjestetään vasemmalta oikealle nousevina arvoina niiden tietojen mukaan. Binaarisia hakupuita varten on monia algoritmeja, jotka voivat tehdä tietojen tilaamisesta erittäin helppoa.
Hakupuusolmuille ei ole olemassa yhtä vakiototeutusta. Solmuja voi edustaa monenlaisia tietorakenteita. Voidaan käyttää matriisijoukkoja ja linkitettyjä luetteloita. Usein hakupuu käyttää mukautettua tietorakennetta, joka on suunniteltu auttamaan ohjelman edellyttämien toimintojen suorittamisessa.