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 syvyysetsintä (, DFS)
• Leveyssuuntainen läpikäynti eli leveysetsintä (, BFS)

Katso myös

• Graafiteoria
• Hakurakenne
• Lajittelualgoritmi
• Tietorakenne