Osa I: Haku binäärisestä hakupuusta

Binäärinen hakupuu on hakurakenne, jossa haku, lisäys ja poisto voidaan ideaalisessa tapauksessa tehdä logaritmisessa ajassa. Rakenteen tehokkuus perustuu siihen, että puu on järjestetty siten, että jokaisen solmun vasemmassa alipuussa on vain sitä pienempiä, ja oikeassa sitä suurempia avaimia.

Esitiedot

• Tietorakenteet
  • Binääripuu
• Algoritmit
  • Rekursio

Oppimistavoitteet

• Hakurakenteet
  • Binäärinen hakupuun
    • Haku binäärisestä hakupuusta
    • Lisäys binääriseen hakupuuhun
    • Poisto binrääisestä hakupuusta

Etsi annettua avainta molemmista binäärisistä hakupuista. Haku suoritetaan valitsemalla jokaisella askeleella se minimoitu alipuu, johon haku etenee.

Haku binäärisestä hakupuusta tapahtuu etenemällä puun juuresta kohti lehtiä. Haettavaa avainta verrataan juuressa olevaan avaimeen. Mikäli haettava avain on pienempi kuin juuressa oleva avain, edetään puun vasempaan haaraan. Mikäli haettava avain on suurempi, edetään oikeaan haaraan. Mikäli avain on yhtä suuri, haku onnistui. Mikäli edetään tyhjään alipuuhun, haku epäonnistui (avainta ei ole hakurakenteessa).

Hahmottele edellä esitettyä kuvausta vastaava pseudokielinen algoritmi. Vertaa ratkaisuasi oheiseen algoritmiin (Search). Ratkaise sen jälkeen annettu tehtävä.

Search(Node root, Key k)
1 if (root == null) //epäonnistunut haku
2     return null;
3 if (k == root.key) //onnistunut haku
4     return root;
5 if (k < root.key) //k vasemmassa haarassa
6     return Search(root.left, k);
7 else //k > root.key, ts. k oikeassa haarassa
8     return Search(root.right, k);