Meni

Binarno stablo pretraživanja C ++: Implementacija BST-a i operacije s primjerima

  • Glavni
  • Ostalo
  • Binarno stablo pretraživanja C ++: Implementacija BST-a i operacije s primjerima

binary search tree c

Detaljan vodič o binarnom stablu pretraživanja (BST) u C ++-u, uključujući operacije, implementaciju C ++-a, prednosti i primjere programa:

Binarno stablo pretraživanja ili BST, kako ga popularno nazivaju, je binarno stablo koje ispunjava sljedeće uvjete:

  1. Čvorovi koji su manji od korijenskog čvora koji je smješten kao lijeva podređena jedinica BST-a.
  2. Čvorovi veći od korijenskog čvora koji je postavljen kao prava podređena osoba BST-a.
  3. Lijevo i desno podstablo su pak binarna stabla pretraživanja.

Ovakav raspored redoslijeda ključeva u određenom slijedu olakšava programeru da učinkovitije izvršava operacije poput pretraživanja, umetanja, brisanja itd. Ako čvorovi nisu poredani, možda ćemo morati usporediti svaki čvor prije nego što dobijemo rezultat operacije.

=> Ovdje pogledajte cjelovitu seriju C ++ treninga.

Binarno stablo pretraživanja na C ++

Što ćete naučiti:

Binarno stablo pretraživanja C ++

Uzorak BST prikazan je u nastavku.

Uzorak BST

najbolji program za nadzor gpu temp

Binarno drveće pretraživanja naziva se i 'uređenim binarnim drvećem' zbog ovog specifičnog uređenja čvorova.

Iz gornjeg BST-a možemo vidjeti da lijevo podstablo ima čvorove manje od korijena, tj. 45, dok desno podstablo ima čvorove veće od 45.

Sada ćemo razgovarati o nekim osnovnim operacijama BST-a.

Osnovne operacije

# 1) Umetak

Operacija umetanja dodaje novi čvor u binarnom stablu pretraživanja.

Algoritam za operaciju umetanja binarnog stabla pretraživanja dan je u nastavku.

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

Kao što je prikazano u gornjem algoritmu, moramo osigurati da je čvor postavljen na odgovarajući položaj kako ne bismo kršili BST redoslijed.

Umetni operaciju u BST

Kao što vidimo u gornjem slijedu dijagrama, radimo niz operacija umetanja. Nakon usporedbe ključa koji treba umetnuti s korijenskim čvorom, odabire se lijevo ili desno podstablo za ključ koji će se umetnuti kao čvor lista na odgovarajućem položaju.

# 2) Izbriši

Operacija brisanja briše čvor koji odgovara zadanom ključu iz BST-a. I u ovoj operaciji moramo preusmjeriti preostale čvorove nakon brisanja kako BST redoslijed ne bi bio prekršen.

Stoga, ovisno o tome koji čvor moramo izbrisati, u BST imamo sljedeće slučajeve za brisanje:

# 1) Kada je čvor Leaf Node

Kada je čvor koji se treba izbrisati lisni čvor, tada čvor izravno brišemo.

Čvor je lisni čvor

# 2) Kada čvor ima samo Jedno dijete

Kada čvor koji treba izbrisati ima samo jedno dijete, tada kopiramo dijete u čvor i brišemo dijete.

Čvor ima samo jedno dijete

# 3) Kada čvor ima dvoje djece

Ako čvor koji se treba izbrisati ima dvoje djece, tada pronalazimo nasljednika inorder za čvor, a zatim kopiramo inorder nasljednika na čvor. Kasnije ćemo izbrisati nasljednika inorder.

Node ima dvoje djece

U gornjem stablu za brisanje čvora 6 s dvoje djece prvo pronalazimo nasljednika inorder za taj čvor koji će se izbrisati. Nasljednika inordera pronalazimo pronalaženjem minimalne vrijednosti u pravom podstablu. U gornjem slučaju, minimalna vrijednost je 7 u desnom podstablu. Kopiramo ga u čvor koji ćemo izbrisati, a zatim brišemo nasljednika inordera.

# 3) Pretraživanje

Operacija pretraživanja BST-a traži određenu stavku koja je identificirana kao „ključ“ u BST-u. Prednost pretraživanja stavke u BST-u je ta što ne moramo pretraživati ​​cijelo stablo. Umjesto toga, zbog narudžbe u BST-u, samo uspoređujemo ključ s root-om.

Ako je ključ isti kao root, tada vraćamo root. Ako ključ nije root, uspoređujemo ga s rootom kako bismo utvrdili trebamo li pretražiti lijevo ili desno podstablo. Jednom kad pronađemo podstablo, trebamo pretražiti ključ i rekurzivno ga tražimo u bilo kojem od podstabala.

Slijedi algoritam za operaciju pretraživanja u BST-u.

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

Operacija pretraživanja u BST-u

Ako želimo pretražiti ključ s vrijednošću 6 u gornjem stablu, tada prvo uspoređujemo ključ s korijenskim čvorom, tj. If (6 == 7) => Ne if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Dalje se spuštamo do lijevog podstabla. Ako je (6 == 5) => Ne.

Ako (6 Ne; to znači 6> 5 i moramo se pomicati udesno.

Ako je (6 == 6) => Da; ključ je pronađen.

# 4) Promjene

Već smo razgovarali o prijelazima za binarno stablo. U slučaju BST-a, možemo preći stablo da bismo dobili redoslijed inOrder, preorder ili postOrder. Zapravo, kada prelazimo BST u sekvenci Inorder01, tada dobivamo sortirani niz.

To smo pokazali na donjoj ilustraciji.

obilaznice

Prelasci za gornje stablo su sljedeći:

Promjena unutar (lnr): 3 5 6 7 8 9 10
Prijelaz predbilježbe (nlr): 7 5 3 6 9 8 10
PostOrder prijelaz (lrn): 3 6 5 8 10 9 7

najbolji besplatni vatrozidi za Windows 10

Ilustracija

Izgradimo binarno stablo pretraživanja od podataka danih u nastavku.

45 30 60 65 70

Uzmimo prvi element kao korijenski čvor.

# 1) 45

korijenski čvor

U sljedećim koracima podatke ćemo smjestiti prema definiciji stabla binarnog pretraživanja, tj. Ako su podaci manji od nadređenog čvora, tada će biti postavljeni na lijevo podređeno tijelo, a ako su podaci veći od nadređenog čvora, tada će bit će pravo dijete.

Ovi koraci su prikazani u nastavku.

# 2) 30

Stablo binarnog pretraživanja 1. korak 30

# 3) 60

Stablo binarnog pretraživanja Korak 2 60

# 4) 65

11 Binarno stablo pretraživanja korak3

# 5) 70

Binarno stablo pretraživanja korak 4

Kada izvodimo inverziju prijelaza na gore navedenom BST-u koji smo upravo konstruirali, slijed je sljedeći.

Slijed prijelaza u redoslijedu

Vidimo da redoslijed prelaska ima elemente poredane uzlaznim redoslijedom.

Implementacija binarnog stabla pretraživanja C ++

Pokažimo BST i njegove operacije pomoću 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):'<

Izlaz:

Stvoreno binarno stablo pretraživanja (zaobilaženje stranice):

30 40 60 65 70

Izbriši čvor 40

Neobični prijelaz za modificirano stablo binarnog pretraživanja:

30 60 65 70

U gore navedenom programu, BST prikazujemo za redoslijed prelaska.

Prednosti BST-a

# 1) Pretraživanje je vrlo učinkovito

Imamo sve čvorove BST-a u određenom redoslijedu, stoga je traženje određene stavke vrlo učinkovito i brže. To je zato što ne trebamo pretraživati ​​cijelo stablo i uspoređivati ​​sve čvorove.

Moramo samo usporediti korijenski čvor s stavkom koju pretražujemo, a zatim odlučujemo trebamo li tražiti u lijevom ili desnom podstablu.

# 2) Učinkovit rad u usporedbi s nizovima i povezanim popisima

Kada pretražujemo stavku u slučaju BST, rješavamo se polovice lijevog ili desnog podstabla na svakom koraku, poboljšavajući tako izvedbu operacije pretraživanja. To je za razliku od nizova ili povezanih popisa u kojima moramo sekvencijalno usporediti sve stavke da bismo pretražili određenu stavku.

# 3) Umetanje i brisanje brže su

Operacije umetanja i brisanja također su brže u usporedbi s drugim strukturama podataka poput povezanih popisa i nizova.

Primjene BST-a

Neke od glavnih primjena BST-a su sljedeće:

  • BST se koristi za implementaciju višerazinskog indeksiranja u aplikacijama baza podataka.
  • BST se također koristi za implementaciju konstrukcija poput rječnika.
  • BST se može koristiti za implementaciju različitih učinkovitih algoritama pretraživanja.
  • BST se također koristi u aplikacijama kojima je potreban sortirani popis kao ulaz, poput mrežnih trgovina.
  • BST se također koriste za procjenu izraza pomoću stabala izraza.

Zaključak

Binarna stabla pretraživanja (BST) varijacija su binarnog stabla i široko se koriste u softverskom polju. Nazivaju se i uređenim binarnim stablima jer se svaki čvor u BST postavlja prema određenom redoslijedu.

Zaobilaženje BST-a daje razvrstani redoslijed predmeta u rastućem redoslijedu. Kada se BST koriste za pretragu, to je vrlo učinkovito i obavlja se u kratkom roku. BST se također koriste za razne programe poput Huffmanovog kodiranja, višerazinskog indeksiranja u bazama podataka itd.

=> Ovdje pročitajte popularne serije obuke za C ++.

Preporučena literatura

^