Binäärinen hakupuu
Wikipedia
Binäärinen hakupuu 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 ovat tyypillisesti erittäin tehokkaita. Hyvin tunnettu binäärisen hakupuun kehitetty versio on punamusta puu.
[muokkaa] Toteutus
Binääripuun hakualgoritmi toteutetaan yleensä rekursiivisesti. Esimerkkitoteutus Python-ohjelmointikielellä:
def search_binary_tree(node, key):
if node is None:
return None # not found
if key < node.key:
return search_binary_tree(node.left, key)
else if key > node.key:
return search_binary_tree(node.right, key)
else:
return node.value
