Meny

Binärt sökträd C ++: BST-implementering och operationer med exempel

  • Huvud
  • Övrig
  • Binärt sökträd C ++: BST-implementering och operationer med exempel

binary search tree c

Prova Vårt Instrument För Att Eliminera Problem

Detaljerad handledning om binärt sökträd (BST) i C ++ inklusive operationer, C ++ implementering, fördelar och exempelprogram:

Ett binärt sökträd eller BST som det populärt kallas är ett binärt träd som uppfyller följande villkor:

  1. De noder som är mindre än rotnoden som placeras som vänster till BST.
  2. Noderna som är större än rotnoden som placeras som BST: s rätt barn.
  3. Vänster och höger underträd är i sin tur binära sökträd.

Detta arrangemang för att beställa tangenterna i en viss sekvens underlättar programmeraren att utföra operationer som att söka, infoga, radera, etc. mer effektivt. Om noder inte ordnas kan vi behöva jämföra varje nod innan vi kan få operationsresultatet.

=> Kolla hela C ++ träningsserien här.

Binärt sökträd i C ++

Vad du kommer att lära dig:

Binärt sökträd C ++

Ett exempel på BST visas nedan.

Exempel på BST

Binära sökträd kallas också 'Beställda binära träd' på grund av denna specifika ordning av noder.

Från ovanstående BST kan vi se att det vänstra underträdet har noder som är mindre än roten dvs 45 medan det högra underträdet har noder som är större än 45.

Låt oss nu diskutera några grundläggande funktioner för BST.

Grundläggande funktioner

# 1) Infoga

Infoga åtgärd lägger till en ny nod i ett binärt sökträd.

Algoritmen för binär sökningsträdinsatsoperation ges nedan.

bästa dator snabba upp programvara gratis
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 visas i ovanstående algoritm måste vi se till att noden placeras i lämplig position så att vi inte bryter mot BST-beställningen.

Infoga operation i BST

Som vi ser i ovanstående diagramsekvens gör vi en serie insättningsoperationer. Efter att ha jämfört nyckeln som ska infogas med rotnoden väljs vänster eller höger underträd för att nyckeln ska infogas som en bladnod i lämplig position.

# 2) Ta bort

Radera åtgärd tar bort en nod som matchar den angivna nyckeln från BST. Även i den här åtgärden måste vi flytta de återstående noderna efter radering så att BST-beställningen inte bryts.

Beroende på vilken nod vi måste ta bort har vi därför följande fall för borttagning i BST:

# 1) När noden är en bladnod

När noden som ska raderas är en bladnod raderar vi noden direkt.

Noden är en bladnod

# 2) När noden bara har ett barn

När noden som ska raderas bara har ett barn kopierar vi barnet till noden och tar bort barnet.

Noden har bara ett barn

# 3) När noden har två barn

Om noden som ska raderas har två barn, hittar vi efterföljaren för noden och kopierar sedan efterföljaren till noden. Senare tar vi bort efterföljaren.

Noden har två barn

I ovanstående träd för att radera noden 6 med två barn, hittar vi först inordningsföljaren för den noden som ska raderas. Vi hittar inordnarens efterträdare genom att hitta minimivärdet i rätt underträd. I ovanstående fall är minimivärdet 7 i rätt underträd. Vi kopierar den till noden som ska raderas och tar sedan bort efterföljaren.

# 3) Sök

Sökningen av BST söker efter ett visst objekt som identifierats som 'nyckel' i BST. Fördelen med att söka efter ett objekt i BST är att vi inte behöver söka i hela trädet. Istället på grund av beställningen i BST jämför vi bara nyckeln med roten.

Om nyckeln är densamma som root returnerar vi root. Om nyckeln inte är rot jämför vi den med roten för att avgöra om vi behöver söka i vänster eller höger underträd. När vi väl har hittat underträdet måste vi söka på nyckeln, och vi söker rekursivt efter det i något av underträden.

Nedan följer algoritmen för en sökoperation 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ökoperation i BST

Om vi ​​vill söka efter en nyckel med värdet 6 i ovanstående träd, jämför vi först nyckeln med rotnoden, dvs. om (6 == 7) => Nej om (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Därefter går vi ner till vänster subträd. Om (6 == 5) => Nej

Om (6 Nej; detta betyder 6> 5 och vi måste flytta åt höger.

Om (6 == 6) => Ja; nyckeln finns.

# 4) Traversaler

Vi har redan diskuterat korsningarna för det binära trädet. Även när det gäller BST kan vi korsa trädet för att komma i ordning, förbeställning eller efterbeställningssekvens. Faktum är att när vi korsar BST i Inorder01-sekvensen, får vi den sorterade sekvensen.

Vi har visat detta i nedanstående illustration.

traversaler

Korsningarna för ovanstående träd är följande:

Inorder traversal (lnr): 3 5 6 7 8 9 10
Förbeställning (nlr): 7 5 3 6 9 8 10
Postorder-traversal (lrn): 3 6 5 8 10 9 7

Illustration

Låt oss konstruera ett binärt sökträd utifrån uppgifterna nedan.

hur man förklarar en kö i java

45 30 60 65 70

Låt oss ta det första elementet som rotnod.

# 1) 45

rotnod

I de efterföljande stegen kommer vi att placera data enligt definitionen av binärt sökträd, dvs. om data är mindre än föräldernoden kommer den att placeras vid det vänstra barnet och om data är större än föräldernoden, då blir rätt barn.

Dessa steg visas nedan.

# 2) 30

Binärt sökträd Steg 1 30

# 3) 60

Binärt sökträd Steg 2 60

# 4) 65

11 Binärt sökträd steg 3

# 5) 70

Binärt sökträd steg 4

När vi utför inorder traversal på ovanstående BST som vi just konstruerade är sekvensen som följer.

Beställa tvärsekvens

Vi kan se att traverssekvensen har element ordnade i stigande ordning.

Binär sökträdsimplementering C ++

Låt oss demonstrera BST och dess verksamhet med 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ökträd skapat (Inorder traversal):

30 40 60 65 70

Ta bort nod 40

Inorder traversal för det modifierade binära sökträdet:

30 60 65 70

I ovanstående program matar vi ut BST för traversal sekvens i ordning.

Fördelar med BST

# 1) Att söka är mycket effektivt

Vi har alla noder för BST i en specifik ordning, därför är det mycket effektivt och snabbare att söka efter ett visst objekt. Detta beror på att vi inte behöver söka i hela trädet och jämföra alla noder.

Vi måste bara jämföra rotnoden med det objekt som vi söker efter och sedan bestämmer vi om vi behöver söka i vänster eller höger underträd.

# 2) Effektivt arbete jämfört med arrays och länkade listor

När vi söker efter ett objekt i fall av BST, blir vi av med hälften av vänster eller höger underträd i varje steg och därigenom förbättras sökoperationens prestanda. Detta står i kontrast till matriser eller länkade listor där vi måste jämföra alla artiklar i följd för att söka efter ett visst objekt.

# 3) Infoga och ta bort är snabbare

Infoga och ta bort operationer är också snabbare jämfört med andra datastrukturer som länkade listor och matriser.

Tillämpningar av BST

Några av de viktigaste tillämpningarna av BST är som följer:

  • BST används för att implementera flernivåindexering i databasapplikationer.
  • BST används också för att implementera konstruktioner som en ordlista.
  • BST kan användas för att implementera olika effektiva sökalgoritmer.
  • BST används också i applikationer som kräver en sorterad lista som input som onlinebutikerna.
  • BST används också för att utvärdera uttrycket med hjälp av expressionsträd.

Slutsats

Binära sökträd (BST) är en variant av det binära trädet och används ofta i programvarufältet. De kallas också ordnade binära träd eftersom varje nod i BST placeras enligt en specifik ordning.

Inorder traversal of BST ger oss den sorterade sekvensen av objekt i stigande ordning. När BST används för sökning är det mycket effektivt och görs på nolltid. BST används också för en mängd olika applikationer som Huffmans kodning, flernivåindexering i databaser etc.

=> Läs igenom den populära C ++ träningsserien här.

Rekommenderad läsning

^