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:
- Čvorovi koji su manji od korijenskog čvora koji je smješten kao lijeva podređena jedinica BST-a.
- Čvorovi veći od korijenskog čvora koji je postavljen kao prava podređena osoba BST-a.
- 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.
Što ćete naučiti:
- Binarno stablo pretraživanja C ++
- Osnovne operacije
- Implementacija binarnog stabla pretraživanja C ++
- Prednosti BST-a
- Primjene BST-a
- Zaključak
- Preporučena literatura
Binarno stablo pretraživanja C ++
Uzorak BST prikazan je u nastavku.
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.
najbolji program za nadzor gpu temp
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.
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.
# 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.
# 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.
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
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.
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
Ilustracija
Izgradimo binarno stablo pretraživanja od podataka danih u nastavku.
45 30 60 65 70
Uzmimo prvi element kao korijenski čvor.
# 1) 45
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
# 3) 60
# 4) 65
# 5) 70
Kada izvodimo inverziju prijelaza na gore navedenom BST-u koji smo upravo konstruirali, slijed je sljedeći.
najbolji besplatni vatrozidi za Windows 10
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
- Struktura podataka binarnog stabla u C ++
- Struktura podataka AVL stabla i hrpe u C ++
- Struktura podataka stabla B i stabla B + u jeziku C ++
- Osnovne ulazno / izlazne operacije na C ++
- Osnovne I / O operacije u Javi (ulazni / izlazni tokovi)
- Stabla u C ++: Osnovna terminologija, tehnike prelaska i tipovi stabala C ++
- Izlazne operacije unosa datoteke u C ++
- Pokazivači i operacije pokazivača u C ++