En Binary Search Tree (BST) er et tre der alle nodene følge de nedenfor nevnte egenskaper −
-
verdien av-tasten på venstre sub-treet er mindre enn verdien av sin overordnede (root) – noden er nøkkelen.
-
verdien av-tasten på høyre sub-treet er større enn eller lik verdien av sine foreldre (root) – noden er nøkkelen.,
Derfor, BST deler alle sine sub-trær i to segmenter; venstre sub-treet og rett sub-treet og kan defineres som −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Representasjon
BST er en samling noder arrangert på en måte hvor de opprettholder BST egenskaper. Hver node har en nøkkel og en tilhørende verdi. Mens du søker, ønsket tast er sammenlignet med nøklene i BST og hvis det blir funnet, tilhørende verdi er hentet.,
Følgende er en billedlig fremstilling av BST −
Vi observere at rot-node-tasten (27) har alle mindre verdsatt tastene på venstre sub-treet og høyere verdsatt tastene på høyre sub-treet.
Grunnleggende Operasjoner
Følgende er grunnleggende operasjoner av et tre −
-
Søk − Søk som et element i et tre.
-
Sett inn − sett inn et element i et tre.
-
Pre-order Traversal − beveger seg rundt et tre i en pre-order måte.
-
På-for Traversal − beveger seg rundt et tre i en ordre måte.,
-
Post-order Traversal − beveger seg rundt et tre i en post-order måte.
Node
Angi på en node for å ha noen data, referanser til venstre og høyre barn noder.
struct node { int data; struct node *leftChild; struct node *rightChild;};
Søk Drift
Når et element er som det skal søkes i, begynne å søke fra rotnoden. Så hvis dataene er mindre enn tasten verdi, søk etter element i venstre undertreet. Ellers søk etter element i høyre undertreet. Følg samme algoritme for hver node.,
Algoritme
Sett inn Operasjon
Når et element er å bli satt inn, må du først finne riktig sted. Begynne å søke fra rotnoden, så hvis dataene er mindre enn tasten verdi, søker du etter tomt sted i venstre undertreet og sette inn data. Ellers, søker du etter tomt sted på rett undertreet og sette inn data.