En Binary Search Tree (BST) er et træ, hvor alle knuder følg de nedenfor nævnte ejendomme −
-
værdien af nøglen til venstre sub-tree er mindre end værdien af dens parent (root) node-tasten.
-
værdien af nøglen til det højre undertræ er større end eller lig med værdien af dets overordnede (root) node nøgle.,
Således, BST opdeler alle dens sub-træer i to segmenter; det venstre undertræ og højre undertræ og kan defineres som −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Repræsentation
BST er en samling af noder, arrangeret på en måde, hvor de fastholder, BST egenskaber. Hver knude har en nøgle og en tilknyttet værdi. Under søgning sammenlignes den ønskede nøgle med tasterne i BST, og hvis den findes, hentes den tilknyttede værdi.,
Følgende er en billedlig repræsentation af BST −
vi observerer, at rodnodetasten (27) har alle mindre værdsatte taster på venstre undertræ og de højere værdsatte taster på højre undertræ.
grundlæggende operationer
Følgende er de grundlæggende operationer af et træ −
-
Søg − søger et element i et træ.
-
Indsæt − indsætter et element i et træ.
-
forudbestilt Traversal-krydser et træ på en forudbestilt måde.
-
in-order Traversal − krydser et træ på en ordre måde.,
-
post-order Traversal − krydser et træ på en post-order måde.
Node
Definer en node med nogle data, henvisninger til dets venstre og højre barn noder.
struct node { int data; struct node *leftChild; struct node *rightChild;};
søgefunktion
Når et element skal søges, skal du begynde at søge fra rodnoden. Så hvis dataene er mindre end nøgleværdien, skal du søge efter elementet i venstre undertræ. Ellers skal du søge efter elementet i den rigtige undertræ. Følg den samme algoritme for hver knude.,
algoritme
Indsæt Operation
når et element skal indsættes, skal du først finde den korrekte placering. Begynd at søge fra rodnoden, og hvis dataene er mindre end nøgleværdien, skal du søge efter den tomme placering i venstre undertræ og indsætte dataene. Ellers skal du søge efter den tomme placering i højre undertræ og indsætte dataene.