Hakupuut

Hakupuut (lookup trees) ovat tietorakenteiden ryhmä, jonka tarkoituksena on järjestää avaimen perusteella tallennetut tiedot puumaisesti siten, että hakeminen, lisäys ja poisto voidaan suorittaa nopeasti. Jokaisessa solmussa on avain tai avaimia sekä viittaukset lapsiin; puu ylläpitää avaimien järjestystä. Hakupuut voivat olla suunniteltu erilaisia käyttötarkoituksia varten, ja niiden tavoitteena on nopea pääsy sekä tuki dynaamiselle tietomäärän kasvulle.

Keskeiset operaatiot ovat haku, lisäys, poisto ja päivitys. Haun aikavaikutus riippuu rakenteesta: perinteinen binäärinen hakupuu ilman tasapainotusta voi pahimmillaan olla O(n). Tasapainotetut hakupuut, kuten AVL- ja punamustat puut, pitävät korkeuden O(log n), jolloin perusoperaatiot ovat myös O(log n). B- ja B+-puut on suunniteltu suurten tietomäärien ulkoiseen hakuun: ne tukevat tehokasta levytoimintojen käyttöä ja pitävät hakupisteet korkeuden O(log n). Trie-puuta käytetään erityisesti merkkijonoihin perustuvissa hauissa ja sanakirjojen toteutuksessa; niiden hakuaika voi olla riippuvainen etsittävän merkkijonon pituudesta.

Hakupuita käytetään laajalti tietokannoissa, tiedostojärjestelmissä, hakemistopalveluissa sekä ohjelmointikielien symbolisissa tauluissa ja kompilaattorien sanakirjoissa. Ominaisuudet kuten tasapainotus, tilankäyttö ja levytoimintojen optimointi vaikuttavat valintaan sovelluksesta riippuen. Yleisesti haku, tietoarkiston hallinta ja suorituskyky muodostavat hakupuiden keskeiset suunnittelukriteerit.