Menu

Binært søgetræ C ++: BST-implementering og operationer med eksempler

  • Vigtigste
  • Andet
  • Binært søgetræ C ++: BST-implementering og operationer med eksempler

binary search tree c

Prøv Vores Instrument Til At Fjerne Problemer

Detaljeret tutorial om binært søgetræ (BST) i C ++ inklusive operationer, C ++ implementering, fordele og eksempelprogrammer:

Et binært søgetræ eller BST, som det populært kaldes, er et binært træ, der opfylder følgende betingelser:

  1. De knudepunkter, der er mindre end rodknudepunktet, der er placeret som BST-venstrebørn.
  2. De noder, der er større end rodnoden, der er placeret som BST's rigtige børn.
  3. Venstre og højre undertræer er igen de binære søgetræer.

Dette arrangement med at bestille nøglerne i en bestemt rækkefølge letter programmøren til at udføre operationer som at søge, indsætte, slette osv. Mere effektivt. Hvis noderne ikke er bestilt, skal vi muligvis sammenligne hver eneste node, før vi kan få driftsresultatet.

=> Tjek den komplette C ++ træningsserie her.

Binært søgetræ i C ++

Hvad du lærer:

Binært søgetræ C ++

En prøve BST er vist nedenfor.

Prøve BST

Binære søgetræer kaldes også 'Bestilte binære træer' på grund af denne specifikke rækkefølge af noder.

Fra ovenstående BST kan vi se, at venstre undertræ har noder, der er mindre end roden, dvs. 45, mens det højre undertræ har de noder, der er større end 45.

Lad os nu diskutere nogle grundlæggende operationer af BST.

Grundlæggende funktioner

# 1) Indsæt

Indsætningsfunktion tilføjer en ny node i et binært søgetræ.

Algoritmen til binær søgetræsindsats er angivet nedenfor.

Android Interview spørgsmål og svar pdf
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; end

Som vist i ovenstående algoritme er vi nødt til at sikre, at noden placeres i den rette position, så vi ikke overtræder BST-ordren.

Indsæt operation i BST

Som vi ser i ovenstående diagramsekvens laver vi en række indsætningsoperationer. Efter at have sammenlignet nøglen, der skal indsættes med rodnoden, vælges venstre eller højre undertræ til nøglen, der skal indsættes som en bladnode i den rette position.

# 2) Slet

Sletning sletter en node, der matcher den givne nøgle fra BST. Også i denne operation er vi nødt til at placere de resterende knudepunkter efter sletning, så BST-ordren ikke overtrædes.

Derfor afhænger vi af hvilken node vi skal slette, følgende tilfælde til sletning i BST:

# 1) Når noden er en bladnode

Når noden, der skal slettes, er en bladnode, sletter vi noden direkte.

Node er en bladknude

# 2) Når noden kun har ét barn

Når noden, der skal slettes, kun har et barn, kopierer vi barnet til noden og sletter barnet.

Node har kun ét barn

# 3) Når noden har to børn

Hvis noden, der skal slettes, har to børn, finder vi efterfølgeren til noden og derefter kopierer efterfølgeren til noden. Senere sletter vi ordren efterfølger.

Node har to børn

I ovenstående træ for at slette knudepunkt 6 med to børn finder vi først ordren efterfølger for den knude, der skal slettes. Vi finder ordren efterfølger ved at finde minimumsværdien i det rigtige undertræ. I ovenstående tilfælde er minimumsværdien 7 i det rigtige undertræ. Vi kopierer det til noden, der skal slettes, og sletter derefter ordren efterfølger.

# 3) Søg

Søgningsfunktionen for BST søger efter et bestemt element identificeret som 'nøgle' i BST. Fordelen ved at søge på et element i BST er, at vi ikke behøver at søge i hele træet. I stedet for på grund af ordren i BST sammenligner vi bare nøglen med roden.

Hvis nøglen er den samme som root, returnerer vi root. Hvis nøglen ikke er rod, sammenligner vi den med roden for at afgøre, om vi skal søge i venstre eller højre undertræ. Når vi har fundet undertræet, er vi nødt til at søge nøglen ind, og vi søger rekursivt efter den i et af undertrærne.

Følgende er algoritmen for en søgning i BST.

Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end

Søgning i BST

Hvis vi vil søge på en nøgle med værdi 6 i ovenstående træ, sammenligner vi først nøglen med rodnoden, dvs. hvis (6 == 7) => Nej hvis (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Derefter nedstiger vi til venstre undertræ. Hvis (6 == 5) => Nej

Hvis (6 Nej; dette betyder 6> 5, og vi er nødt til at bevæge os mod højre.

Hvis (6 == 6) => Ja; nøglen findes.

# 4) gennemgange

Vi har allerede diskuteret gennemgange for det binære træ. Også i tilfælde af BST kan vi krydse træet for at komme i rækkefølge, forudbestilling eller efterbestilling. Faktisk når vi krydser BST i Inorder01 sekvens, så får vi den sorterede sekvens.

Vi har vist dette i nedenstående illustration.

gennemgange

Gennemgangene af ovenstående træ er som følger:

Inorder traversal (lnr): 3 5 6 7 8 9 10
Forudbestil traversal (nlr): 7 5 3 6 9 8 10
PostOrder traversal (lrn): 3 6 5 8 10 9 7

Illustration

gratis app til download af youtube-videoer

Lad os konstruere et binært søgetræ ud fra nedenstående data.

45 30 60 65 70

Lad os tage det første element som rodnoden.

# 1) 45

rodknude

I de efterfølgende trin placerer vi dataene i henhold til definitionen af ​​Binary Search-træ, dvs. hvis data er mindre end forældrenoden, placeres de ved det venstre barn, og hvis dataene er større end forældrenoden, så bliver det rigtige barn.

Disse trin er vist nedenfor.

# 2) 30

Binært søgetræ Trin 1 30

# 3) 60

Binært søgetræ Trin 2 60

# 4) 65

11 Binært søgetræ trin3

# 5) 70

Binært søgetræ trin 4

Når vi udfører ordren traversal på ovenstående BST, som vi netop konstruerede, er sekvensen som følger.

Bestil traversal sekvens

Vi kan se, at traversalsekvensen har elementer arrangeret i stigende rækkefølge.

Binær søgetræsimplementering C ++

Lad os demonstrere BST og dets operationer ved hjælp af C ++ implementering.

#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'<

Produktion:

Binært søgetræ oprettet (Bestil traversal):

30 40 60 65 70

Slet node 40

Bestil gennemgang af det modificerede binære søgetræ:

30 60 65 70

I ovennævnte program sender vi BST'en ind i rækkefølge i rækkefølge.

Fordele ved BST

# 1) Søgning er meget effektiv

Vi har alle noderne i BST i en bestemt rækkefølge, og derfor er søgning efter en bestemt vare meget effektiv og hurtigere. Dette skyldes, at vi ikke behøver at søge i hele træet og sammenligne alle knudepunkter.

Vi skal bare sammenligne rodnoden med det element, som vi søger efter, og så beslutter vi, om vi skal søge i venstre eller højre undertræ.

# 2) Effektivt arbejde i sammenligning med arrays og sammenkædede lister

Når vi søger på et element i tilfælde af BST, slipper vi for halvdelen af ​​venstre eller højre undertræ ved hvert trin og forbedrer dermed søgeoperationens ydeevne. Dette er i modsætning til arrays eller sammenkædede lister, hvor vi skal sammenligne alle emnerne sekventielt for at søge efter et bestemt emne.

# 3) Indsæt og slet er hurtigere

Indsæt og slet operationer er også hurtigere sammenlignet med andre datastrukturer som sammenkædede lister og arrays.

Anvendelser af BST

Nogle af de største anvendelser af BST er som følger:

  • BST bruges til at implementere indeksering på flere niveauer i databaseapplikationer.
  • BST bruges også til at implementere konstruktioner som en ordbog.
  • BST kan bruges til at implementere forskellige effektive søgningsalgoritmer.
  • BST bruges også i applikationer, der kræver en sorteret liste som input som onlinebutikkerne.
  • BST'er bruges også til at evaluere udtrykket ved hjælp af ekspressionstræer.

Konklusion

Binære søgetræer (BST) er en variation af det binære træ og bruges i vid udstrækning i softwarefeltet. De kaldes også ordnede binære træer, da hver node i BST placeres i henhold til en bestemt rækkefølge.

Inorder traversal of BST giver os den sorterede sekvens af varer i stigende rækkefølge. Når BST'er bruges til søgning, er det meget effektivt og gøres på ingen tid. BST'er bruges også til en række applikationer som Huffmans kodning, indeksering på flere niveauer i databaser osv.

=> Læs gennem den populære C ++ træningsserie her.

Anbefalet læsning

^