binäärihakupuu (BST) on puu, jossa kaikki solmut seuraa alla mainitut ominaisuudet −
-
arvo näppäin vasen sub-puu on vähemmän kuin arvo sen vanhemman (root) solmun avain.
-
oikean alapuun avaimen arvo on suurempi tai yhtä suuri kuin sen vanhemman (juuri) solmun avaimen arvo.,
Näin, BST-jakaa sen kaikkien osa-puita kahteen segmenttiin; vasen sub-puu ja oikea sub-puu, ja se voidaan määritellä −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Esitys
BST on kokoelma solmuja järjestetty tavalla, jossa ne säilyttää BST ominaisuuksia. Jokaisella solmulla on avain ja siihen liittyvä arvo. Etsinnän aikana haluttua avainta verrataan BST: n avaimiin ja jos se löytyy, siihen liittyvä arvo haetaan.,
Seuraavassa on kuvallinen esitys BST −
huomaamme, että root-solmu-näppäintä (27) on vähemmän arvostettu avaimet vasemmalla sub-puu ja korkeampi arvostettu avaimet oikealla sub-puu.
peruskäyttö
Seuraavat ovat perustoiminnot puu −
-
Haku − Haut elementti puu.
-
Insert − Inserts an element in a tree.
-
Pre-order Traversal − Kulkee puun pre-order tavalla.
-
in-order Traversal − Traverses a tree in-order manner.,
-
Post-jotta Traversal − Kulkee puun post-order tavalla.
solmu
Määrittele solmu, jolla on joitakin tietoja, viittaukset sen vasempaan ja oikeaan lapsisolmuun.
struct node { int data; struct node *leftChild; struct node *rightChild;};
Etsi Toimintaa
Aina kun elementti on etsinyt, aloittaa haun juuresta solmuun. Jos tieto on pienempi kuin avainarvo, etsi Elementti vasemmassa alakulmassa. Muuten, etsi Elementti oikeassa subtree. Seuraa samaa algoritmia jokaiselle solmulle.,
Algoritmi
Lisää Käyttö
Aina kun elementti lisätään, ensin paikantaa sen oikea sijainti. Aloita haku juurisolmusta, niin jos tiedot ovat alle avaimen arvon, etsi tyhjä sijainti vasemmasta alalajista ja lisää tiedot. Muussa tapauksessa etsi tyhjä sijainti oikeassa alakulmassa ja lisää tiedot.