Binäärinen hakupuu (binäärihakupuu, , 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.
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.
Toteutus
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
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. Tasapainotetut hakupuut kuten punamusta puu ratkaisevat ongelman. Parhaassa tapauksessa puun korkeus on mahdollisimman pieni eli noin , missä on solmujen lukumäärä. Tällöin haun asymptoottinen suoritusaika on vastaavasti .
Lähteet
Aiheesta muualla
GeeksforGeeks: Binary Search Tree - Set 1 (Search and Insertion) GeeksforGeeks: Red-Black Tree - Set 1 (Introduction) InterviewBit: Binary Search Tree
Luokka:Tietorakenteet Luokka:Hakualgoritmit