Hakualgoritmi

Hakualgoritmilla voidaan tarkoittaa mitä tahansa algoritmia, jolle kerrotaan ongelma ja joka etsii siihen vastauksen. Yleensä merkitys on suppeampi, ja haulla tarkoitetaan arvon etsimistä tietorakenteesta. Tällaiset hakualgoritmit ovat keskeisiä ohjelmoinnissa ja tietojenkäsittelytieteessä, ja niitä on hyvinkin monenlaisia käytettävästä tietorakenteesta riippuen.

Yksinkertaisin ja yleiskäyttöisin hakualgoritmi on peräkkäishaku, joka etsii etsii arvoa säiliöstä käymällä peräkkäin läpi jokaisen alkion. Se toimii jokaisessa tietorakenteessa, joka sallii alkioiden läpikäynnin ja yhtäsuuruusvertailun. Tyypillisesti sitä käytetään järjestämättömiin taulukoihin ja linkitettyihin listoihin.

Jos tietorakenteen alkioista tiedetään jotakin erityistä, algoritmi voi käyttää tätä tietoa hyväkseen. Suuruusjärjestyksessä olevaan taulukkoon puree puolitushaku eli binäärihaku (). Jos alkiot ovat vielä jakautuneet jokseenkin säännöllisesti, interpolaatiohaku () voi nopeuttaa hakua entisestään.

Puun läpikäyntialgoritmit liittyvät kiinteästi kyseisiin tietorakenteisiin. Alkeellisin esimerkki on binäärihakupuu, jossa jokaisessa solmussa on kaksi alipuuta: vasemmassa on vain solmua pienempiä alkioita ja oikeassa solmua suurempia alkioita. Tämä mahdollistaa nopean hakualgoritmin, jos puu on tasapainoinen.
 Binäärihakupuu
 Punamusta puu
 AVL-puu
 B-puu

Graafin eli verkon läpikäyntialgoritmit etsivät arvon lisäksi lyhimmän polun lähtösolmun ja etsittävään solmun välille. Ne ovat siis samalla polunhakualgoritmeja. Koska puutkin ovat verkkoja, niiden läpikäyntialgoritmeissa on paljon yhteistä.
 Syvyyssuuntainen läpikäynti eli syvyyshaku (, DFS)
 Leveyssuuntainen läpikäynti eli leveyshaku (, BFS)

Katso myös 
 Graafiteoria
 Hakurakenne
 Lajittelualgoritmi
 Tietorakenne