binary search tree c
Detaljert veiledning om binært søketre (BST) i C ++ inkludert operasjoner, C ++ implementering, fordeler og eksempelprogrammer:
Et binært søketre eller BST som det populært kalles er et binært tre som oppfyller følgende betingelser:
- Nodene som er mindre enn rotnoden som er plassert som venstre barn av BST.
- Nodene som er større enn rotnoden som er plassert som de rette barna til BST.
- Venstre og høyre undertrær er i sin tur de binære søketrærne.
Dette arrangementet med å bestille tastene i en bestemt rekkefølge, gjør det mulig for programmereren å utføre operasjoner som å søke, sette inn, slette osv. Mer effektivt. Hvis nodene ikke er bestilt, må vi kanskje sammenligne hver node før vi kan få operasjonsresultatet.
=> Sjekk den komplette C ++ treningsserien her.
Hva du vil lære:
- Binært søketre C ++
- Grunnleggende operasjoner
- Binær søktreimplementering C ++
- Fordeler med BST
- Anvendelser av BST
- Konklusjon
- Anbefalt lesing
Binært søketre C ++
En prøve BST er vist nedenfor.
Binære søketrær blir også referert til som 'Bestilte binære trær' på grunn av denne spesifikke rekkefølgen av noder.
Fra ovennevnte BST kan vi se at venstre undertre har noder som er mindre enn roten, dvs. 45 mens det høyre undertreet har nodene som er større enn 45.
La oss nå diskutere noen grunnleggende operasjoner av BST.
Grunnleggende operasjoner
# 1) Sett inn
Sett inn operasjon legger til en ny node i et binært søketre.
Algoritmen for innsettingen av binært søketre er gitt nedenfor.
beste datamaskinen hastighet opp programvare 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 vist i algoritmen ovenfor, må vi sørge for at noden plasseres i riktig posisjon slik at vi ikke bryter BST-bestillingen.
Som vi ser i den ovennevnte rekkefølgen av diagrammer, lager vi en serie innsettingsoperasjoner. Etter å ha sammenlignet nøkkelen som skal settes inn med rotnoden, blir venstre eller høyre undertre valgt for nøkkelen som skal settes inn som en bladnode i riktig posisjon.
# 2) Slett
Slett operasjon sletter en node som samsvarer med den gitte nøkkelen fra BST. Også i denne operasjonen må vi omplassere de resterende nodene etter sletting, slik at BST-bestillingen ikke blir brutt.
Avhengig av hvilken node vi må slette, har vi følgende tilfeller for sletting i BST:
# 1) Når noden er en bladnode
Når noden som skal slettes er en bladnode, sletter vi noden direkte.
# 2) Når noden bare har ett barn
Når noden som skal slettes bare har ett barn, kopierer vi barnet til noden og sletter barnet.
# 3) Når noden har to barn
Hvis noden som skal slettes har to barn, finner vi etterfølgeren til noden og deretter kopierer etterfølgeren til noden. Senere sletter vi ordren etterfølgeren.
I treet ovenfor for å slette noden 6 med to barn, finner vi først ordren etterfølgeren for den noden som skal slettes. Vi finner ordren etterfølgeren ved å finne minimumsverdien i riktig undertre. I ovennevnte tilfelle er minimumsverdien 7 i riktig undertre. Vi kopierer den til noden som skal slettes, og sletter deretter etterfølgeren.
# 3) Søk
Søkeoperasjonen til BST søker etter et bestemt element identifisert som 'nøkkel' i BST. Fordelen med å søke etter et element i BST er at vi ikke trenger å søke i hele treet. I stedet for på grunn av bestillingen i BST, sammenligner vi bare nøkkelen med roten.
Hvis nøkkelen er den samme som root, returnerer vi root. Hvis nøkkelen ikke er rot, sammenligner vi den med roten for å avgjøre om vi trenger å søke i venstre eller høyre undertrær. Når vi har funnet undertræret, må vi søke i nøkkelen, og vi søker rekursivt etter den i et av undertrærne.
Følgende er algoritmen for en søkeoperasjon 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
Hvis vi vil søke etter en nøkkel med verdi 6 i treet ovenfor, sammenligner vi først nøkkelen med rotnoden, dvs. hvis (6 == 7) => Nei hvis (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.
Deretter går vi ned til venstre undertre. Hvis (6 == 5) => Nei.
Hvis (6 Nei; dette betyr 6> 5 og vi må bevege oss mot høyre.
Hvis (6 == 6) => Ja; nøkkelen er funnet.
# 4) Gjennomganger
Vi har allerede diskutert gjennomgangene for det binære treet. I tilfelle BST også, kan vi krysse treet for å komme i rekkefølge, forhåndsbestille eller etterbestille. Når vi krysser BST i Inorder01-sekvensen, får vi faktisk den sorterte sekvensen.
Vi har vist dette i illustrasjonen nedenfor.
Gjennomgangen for treet ovenfor er som følger:
salesforce-utvikler intervju spørsmål og svar for erfarne
Inorder traversal (lnr): 3 5 6 7 8 9 10
Forhåndsbestill traversal (nlr): 7 5 3 6 9 8 10
PostOrder traversal (lrn): 3 6 5 8 10 9 7
Illustrasjon
La oss konstruere et binært søketre fra dataene nedenfor.
45 30 60 65 70
La oss ta det første elementet som rotnode.
# 1) 45
I de påfølgende trinnene vil vi plassere dataene i henhold til definisjonen av Binary Search-treet, dvs. hvis data er mindre enn foreldrenoden, vil de plasseres til venstre barn, og hvis dataene er større enn foreldrenoden, så vil være det rette barnet.
Disse trinnene er vist nedenfor.
# 2) 30
# 3) 60
# 4) 65
# 5) 70
Når vi utfører ordrenovergangen på ovennevnte BST som vi nettopp konstruerte, er sekvensen som følger.
Vi kan se at traversalsekvensen har elementer arrangert i stigende rekkefølge.
Binær søktreimplementering C ++
La oss demonstrere BST og dens operasjoner ved bruk av 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):'< Produksjon:
Binært søketre opprettet (Inorder traversal):
30 40 60 65 70
Slett node 40
Bestill traversal for det modifiserte binære søketreet:
30 60 65 70
I det ovennevnte programmet sender vi BST inn for i rekkefølge traversal sekvens.
Fordeler med BST
# 1) Søking er veldig effektiv
Vi har alle nodene til BST i en bestemt rekkefølge, og derfor er det veldig effektivt og raskere å søke etter et bestemt element. Dette er fordi vi ikke trenger å søke i hele treet og sammenligne alle nodene.
Vi må bare sammenligne rotnoden med elementet vi søker etter, og så bestemmer vi oss for om vi trenger å søke i venstre eller høyre undertreet.
# 2) Effektivt arbeid i forhold til matriser og sammenkoblede lister
Når vi søker etter et element i tilfelle BST, blir vi kvitt halvparten av venstre eller høyre undertrinn i hvert trinn, og forbedrer dermed ytelsen til søkeoperasjonen. Dette er i motsetning til matriser eller koblede lister der vi må sammenligne alle elementene sekvensielt for å søke i et bestemt element.
# 3) Sett inn og slett er raskere
Sett inn og slett operasjoner er også raskere sammenlignet med andre datastrukturer som koblede lister og matriser.
Anvendelser av BST
Noen av de viktigste anvendelsene av BST er som følger:
- BST brukes til å implementere indeksering på flere nivåer i databaseapplikasjoner.
- BST brukes også til å implementere konstruksjoner som en ordbok.
- BST kan brukes til å implementere ulike effektive søkealgoritmer.
- BST brukes også i applikasjoner som krever en sortert liste som input som nettbutikkene.
- BST-er brukes også til å evaluere uttrykket ved hjelp av uttrykkstrær.
Konklusjon
Binære søketrær (BST) er en variant av det binære treet og brukes mye i programvarefeltet. De kalles også ordnede binære trær ettersom hver node i BST er plassert i henhold til en bestemt rekkefølge.
Inorder traversal of BST gir oss den sorterte sekvensen av elementer i stigende rekkefølge. Når BST-er brukes til å søke, er det veldig effektivt og gjøres på kort tid. BST-er brukes også til en rekke applikasjoner som Huffmans koding, indeksering på flere nivåer i databaser, etc.
=> Les gjennom den populære C ++ treningsserien her.
Anbefalt lesing
- Datastruktur for binært tre i C ++
- AVL Tree and Heap Datastruktur i C ++
- B Tree og B + Tree Datastruktur i C ++
- Grunnleggende inngangs- / utgangsoperasjoner i C ++
- Grunnleggende I / U-operasjoner i Java (Input / Output Streams)
- Trees In C ++: Basic Terminology, Traversal Techniques & C ++ Tree Typer
- Operasjon av filinndata i C ++
- Pekere og pekeroperasjoner i C ++