Meni

Binarno drevo iskanja C ++: Implementacija BST in operacije s primeri

  • Glavni
  • Drugo
  • Binarno drevo iskanja C ++: Implementacija BST in operacije s primeri

binary search tree c

Preizkusite Naš Instrument Za Odpravo Težav

Podrobna vadnica o binarnem drevesu iskanja (BST) v jeziku C ++, vključno z operacijami, implementacijo C ++, prednostmi in primeri programov:

Binarno drevo iskanja ali BST, kot ga popularno imenujejo, je binarno drevo, ki izpolnjuje naslednje pogoje:

  1. Vozlišča, ki so manjša od korenskega vozlišča, ki je postavljeno kot levi podrejeni element BST.
  2. Vozlišča, ki so večja od korenskega vozlišča, ki je postavljeno kot pravi podrejeni BST.
  3. Levo in desno poddrevje sta nato binarni iskalni drevesi.

Ta ureditev razvrščanja tipk v določenem zaporedju omogoča programerju, da učinkoviteje izvaja operacije, kot so iskanje, vstavljanje, brisanje itd. Če vozlišča niso urejena, bomo morda morali primerjati vsako vozlišče, preden bomo lahko dobili rezultat operacije.

=> Tukaj preverite celotno serijo usposabljanj za C ++

Binarno drevo iskanja v jeziku C ++

Kaj se boste naučili:

Binarno drevo iskanja C ++

Vzorec BST je prikazan spodaj.

Vzorec BST

Binarna drevesa za iskanje se imenujejo tudi »urejena binarna drevesa« zaradi tega posebnega urejanja vozlišč.

Iz zgornjega BST lahko vidimo, da ima levo poddrevo vozlišča, ki so manjša od korena, tj.45, medtem ko ima desno poddrevo vozlišča, večja od 45.

Zdaj pa se pogovorimo o nekaterih osnovnih operacijah BST.

Osnovne operacije

# 1) Vstavi

Operacija vstavljanja doda novo vozlišče v binarno drevo iskanja.

Algoritem za operacijo vstavljanja binarnega drevesa iskanja je podan spodaj.

vprašanja za intervju s testiranjem penetracije spletnih aplikacij
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

Kot je prikazano v zgornjem algoritmu, moramo zagotoviti, da je vozlišče postavljeno na ustrezen položaj, da ne bomo kršili BST-jevega urejanja.

Vstavite operacijo v BST

Kot vidimo v zgornjem zaporedju diagramov, izvedemo vrsto operacij vstavljanja. Po primerjavi ključa, ki ga je treba vstaviti, s korenskim vozliščem se izbere levo ali desno poddrevo, da se ključ vstavi kot listno vozlišče na ustreznem položaju.

# 2) Izbriši

Operacija Delete iz BST izbriše vozlišče, ki se ujema z danim ključem. Tudi pri tej operaciji moramo po brisanju prestaviti preostala vozlišča, tako da vrstni red BST ne bo kršen.

Glede na to, katero vozlišče moramo izbrisati, imamo v BST naslednje primere za brisanje:

# 1) Ko je vozlišče Leaf Node

Če je vozlišče, ki ga je treba izbrisati, vozlišče listov, potem vozlišče neposredno izbrišemo.

Vozlišče je listno vozlišče

# 2) Če ima vozlišče samo enega otroka

Ko ima vozlišče, ki ga je treba izbrisati, samo enega otroka, ga kopiramo v vozlišče in otroka izbrišemo.

Vozlišče ima samo enega otroka

# 3) Ko ima vozlišče dva otroka

Če ima vozlišče, ki ga je treba izbrisati, dva podrejena elementa, potem najdemo naslednika inorderja za vozlišče in nato naslednika inorderja kopiramo v vozlišče. Kasneje izbrišemo naslednika inorder.

Vozlišče ima dva otroka

V zgornjem drevesu za brisanje vozlišča 6 z dvema otrokoma najprej najdemo naslednika zaporedja za to vozlišče, ki ga je treba izbrisati. Naslednika inorderja najdemo tako, da najdemo najmanjšo vrednost v pravem poddrevesu. V zgornjem primeru je v desnem poddrevju najmanjša vrednost 7. Kopiramo ga v vozlišče, ki ga želimo izbrisati, in nato izbrišemo naslednika po naročilu.

# 3) Iskanje

Iskalna operacija BST išče določeno postavko, ki je v BST označena kot 'ključna'. Prednost iskanja predmeta v BST je, da nam ni treba iskati celotnega drevesa. Namesto zaradi naročanja v BST ključ primerjamo samo s korenskim.

Če je ključ enak korenu, vrnemo root. Če ključ ni root, ga primerjamo s korenom, da ugotovimo, ali moramo iskati levo ali desno poddrevo. Ko najdemo poddrevo, moramo poiskati ključ in ga rekurzivno poiskati v katerem koli od dreves.

Sledi algoritem za iskalno operacijo v 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

Iskalna operacija v BST

Če želimo v zgornjem drevesu poiskati ključ z vrednostjo 6, najprej primerjamo ključ s korenskim vozliščem, če je (6 == 7) => Ne, če (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Nato sestopimo do levega drevesa. Če je (6 == 5) => Ne.

Če (6 Ne; to pomeni 6> 5 in se moramo pomakniti desno.

Če (6 == 6) => Da; ključ je najden.

# 4) Prehodi

O poteh za binarno drevo smo že razpravljali. Tudi v primeru BST lahko drevo prehodimo, da dobimo zaporedje inOrder, preorder ali postOrder. Ko prehodimo BST v zaporedju Inorder01, dobimo razvrščeno zaporedje.

To smo pokazali na spodnji sliki.

prečnice

Prehodi za zgornje drevo so naslednji:

Prehod znotraj (lnr): 3 5 6 7 8 9 10
Prehod pred naročilom (nlr): 7 5 3 6 9 8 10
Prehod PostOrder (lrn): 3 6 5 8 10 9 7

Ilustracija

Iz spodnjih podatkov sestavimo binarno drevo iskanja.

45 30 60 65 70

Vzemimo prvi element kot korensko vozlišče.

# 1) 45

korensko vozlišče

V nadaljnjih korakih bomo podatke postavili v skladu z definicijo binarnega drevesa iskanja, tj. Če so podatki manjši od nadrejenega vozlišča, bodo postavljeni v levi podrejeni element in če so podatki večji od nadrejenega vozlišča, potem bo pravi otrok.

Ti koraki so prikazani spodaj.

# 2) 30

Drevo binarnega iskanja 1. korak 30

# 3) 60

Drevo binarnega iskanja 2. korak 60

brezplačno orodje za testiranje snemanja in predvajanja

# 4) 65

11 Binarno drevo iskanja korak3

# 5) 70

Drevo binarnega iskanja 4. korak

Ko izvedemo prehod po vrstnem redu na zgornjem BST, ki smo ga pravkar zgradili, je zaporedje naslednje.

Zaporedje prečkanja vrstnega reda

Vidimo lahko, da ima prehodno zaporedje elemente razporejene v naraščajočem vrstnem redu.

Izvedba binarnega drevesa iskanja C ++

Predstavimo BST in njegovo delovanje z uporabo implementacije C ++.

#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):'<

Izhod:

Ustvarjeno binarno drevo iskanja (prehod po vrsti):

30 40 60 65 70

Izbriši vozlišče 40

Prehod po vrsti za spremenjeno binarno drevo iskanja:

30 60 65 70

V zgornjem programu izpišemo BST za zaporedno prečkanje zaporedja.

Prednosti BST

# 1) Iskanje je zelo učinkovito

Vsa vozlišča BST imamo v določenem vrstnem redu, zato je iskanje določenega predmeta zelo učinkovito in hitrejše. To je zato, ker nam ni treba iskati celotnega drevesa in primerjati vseh vozlišč.

Primerjati moramo le korensko vozlišče s postavko, ki jo iščemo, nato pa se odločimo, ali moramo iskati v levem ali desnem poddrevesu.

# 2) Učinkovito delovanje v primerjavi z nizi in povezanimi seznami

Ko iščemo element v primeru BST, se na vsakem koraku znebimo polovice levega ali desnega poddrevesa in s tem izboljšamo uspešnost iskalne operacije. To je v nasprotju z nizi ali povezanimi seznami, v katerih moramo zaporedoma primerjati vse elemente za iskanje določenega predmeta.

# 3) Vstavljanje in brisanje sta hitrejša

Operacije vstavljanja in brisanja so prav tako hitrejše v primerjavi z drugimi podatkovnimi strukturami, kot so povezani seznami in polja.

Aplikacije BST

Nekatere glavne aplikacije BST so naslednje:

  • BST se uporablja za izvajanje večstopenjskega indeksiranja v aplikacijah baz podatkov.
  • BST se uporablja tudi za izvajanje konstruktov, kot je slovar.
  • BST se lahko uporablja za izvajanje različnih učinkovitih algoritmov iskanja.
  • BST se uporablja tudi v aplikacijah, ki kot vhodne podatke zahtevajo razvrščen seznam, kot so spletne trgovine.
  • BST-ji se uporabljajo tudi za ovrednotenje izraza z uporabo dreves izrazov.

Zaključek

Binarna drevesa iskanja (BST) so različica binarnega drevesa in se pogosto uporabljajo na področju programske opreme. Imenujejo se tudi urejena binarna drevesa, saj je vsako vozlišče v BST postavljeno po določenem vrstnem redu.

Prehod po vrstnem redu BST nam da razvrščeno zaporedje elementov v naraščajočem vrstnem redu. Ko se BST uporabljajo za iskanje, je to zelo učinkovito in se opravi v kratkem času. BST se uporabljajo tudi za različne aplikacije, kot je Huffmanovo kodiranje, večstopenjsko indeksiranje v zbirkah podatkov itd.

=> Tukaj preberite priljubljeno serijo usposabljanj za C ++

Priporočeno branje

^