Binäärinen hakupuu

Kohteesta Wikipedia
Siirry navigaatioon Siirry hakuun
Binäärinen hakupuu, jossa on yhdeksän solmua.

Binäärinen hakupuu (binäärihakupuu, engl. binary search tree, BST) on hakurakenne, joka on toteutettu binääripuun avulla. Binäärisen hakupuun kaikille solmuille pätee, että solmun vasemmassa alipuussa on ainoastaan sitä pienempiä alkioita ja vastaavasti oikeassa alipuussa ainoastaan sitä suurempia alkioita.[1]

Binäärisiä hakupuita käyttävät haku- ja lajittelualgoritmit ovat tyypillisesti erittäin tehokkaita. Hyvin tunnettu binäärisen hakupuun kehitetty versio on punamusta puu.[2]

Toteutus[muokkaa | muokkaa wikitekstiä]

Binääripuun hakualgoritmi toteutetaan yleensä rekursiivisesti. Esimerkkitoteutus pseudokoodina:

  • key: avain, jonka arvoa haetaan
  • node: puun solmua kuvaava tietue; aluksi puun juuri
  • node.key: solmun avain
  • node.value: solmun arvo
  • node.left: solmun vasen alisolmu
  • node.right: solmun oikea alisolmu
 function search_binary_tree(node, key)
     if node = null
         return null  # ei löytynyt
     else if node.key = key
         return node.value  # löytyi
     else if key < node.key
         return search_binary_tree(node.left, key)
     else  # key > node.key
         return search_binary_tree(node.right, key)

Koska algoritmi on häntärekursiivinen, sen voi optimoida käyttämään toistoa rekursion sijaan. Jos tarvitaan säiliö eikä hakurakenne, niin avain ja arvo voidaan yhdistää.

Tehokkuus[muokkaa | muokkaa wikitekstiä]

Hakuoperaation suoritusaika on verrannollinen puun korkeuteen. Korkeus riippuu siitä, miten puu on muodostunut. Pahimmassa tapauksessa binääripuusta muodostuu täysin toispuolinen, jolloin hakuoperaation suoritusaika on kertaluokkaa eikä se ole lainkaan tehokkaampi kuin vaikkapa peräkkäishaku linkitetystä listasta.[3][4] Tasapainotetut hakupuut kuten punamusta puu ratkaisevat ongelman.[2] Parhaassa tapauksessa puun korkeus on mahdollisimman pieni eli noin , missä on solmujen lukumäärä. Tällöin haun asymptoottinen suoritusaika on vastaavasti .[3]

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. Binary Search Tree HackerEarth. Viitattu 22.03.2018.
  2. a b cpphamza: An Introduction to Binary Search and Red-Black Trees Topcoder. 2016. Viitattu 22.03.2018.
  3. a b Garg, Anuj: Trees HackerEarth. 2018. Viitattu 22.03.2018.
  4. Linear Search HackerEarth. 2018. Viitattu 22.03.2018.

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]

Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.