Hakurakenne
Wikipedia
Hakurakenne on abstrakti tietotyyppi, jolla on määritelty seuraavat perusoperaatiot: haku, lisäys ja poisto. Lisäksi hakurakenteen toteutuksesta riippuen voidaan määritellä muita operaatioita, kuten aluehaku (hae kaikki avaimet annetulta väliltä) tai seuraaja (hae löydetystä avaimesta järjestyksessä seuraava).
Esimerkki hakurakenteesta on vaikkapa puhelinluettelo, jossa avaimena toimii henkilön tai yrityksen nimi, ja avaimen kohdalta löytyy datana kohteen osoite tai puhelinnumero. Hakurakennetta voidaan indeksoida haun nopeuttamiseksi, tällainen olisi esimerkiksi sisällysluettelo.
Monissa ohjelmointikielissä, kuten Pythonissa, Smalltalkissa, Perlissä, Rubyssä ja Javassa, hakurakenteet on toteutettu valmiiksi kielen tasolla. Tällöin ohjelmoijan ei tarvitse välittää toteutuksen yksityiskohdista, paitsi jos hän haluaa huippuoptimoitua koodia.
Hakurakenteiden toteutusratkaisut ja nimeäminen vaihtelevat eri ohjelmointikielissä, mutta periaate on aina samanakaltainen. Yleinen kongreettinen hakurakenne on Dictionary tai Map (suom. Kuvaus), jotka ovat sanakirjatyppisiä avain-arvo -rinnastuksia. Esimerkiksi Java-kielessä on useita erilaisia toteutuksia hakurakenteille, joista valitaan kulloiseenkin tehtävään parhaiten soveltuva ratkaisu. Valinnalle voidaan asettaa useita kriteereitä, joista tärkeimmät ovat avainjoukon järjestäminen (järjestetty tai järjestemätön), aikavaativuus sekä tilavaativuus.
[muokkaa] Hakurakenteita
- Binäärinen hakupuu
- AVL-puu
- Punamusta puu
- Hajautus