Meniu

Arborele de căutare binară C ++: Implementarea și operațiile BST cu exemple

  • Principal
  • Alte
  • Arborele de căutare binară C ++: Implementarea și operațiile BST cu exemple

binary search tree c

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Tutorial detaliat despre arborele de căutare binar (BST) în C ++, inclusiv operațiuni, implementare C ++, avantaje și exemple de programe:

Un arbore de căutare binar sau BST așa cum este numit popular este un arbore binar care îndeplinește următoarele condiții:

  1. Nodurile care sunt mai mici decât nodul rădăcină care este plasat ca copii stângi ai BST.
  2. Nodurile care sunt mai mari decât nodul rădăcină care este plasat drept copiii buni ai BST.
  3. Subarborii din stânga și din dreapta sunt la rândul lor copacii binari de căutare.

Acest aranjament de comandare a tastelor într-o anumită secvență facilitează programatorului să efectueze mai eficient operațiuni precum căutarea, inserarea, ștergerea etc. Dacă nodurile nu sunt ordonate, atunci ar trebui să comparăm fiecare nod înainte să putem obține rezultatul operației.

=> Verificați aici seria completă de formare C ++.

Arborele de căutare binar în C ++

Ce veți învăța:

Arborele de căutare binară C ++

Un eșantion BST este prezentat mai jos.

Eșantion BST

Arborii binari de căutare sunt, de asemenea, denumiți „Arborii binari ordonați” datorită acestei ordonări specifice a nodurilor.

Din BST de mai sus, putem vedea că subarborele din stânga are noduri mai mici decât rădăcina, adică 45, în timp ce subarborele din dreapta are nodurile mai mari de 45.

Acum, să discutăm câteva operațiuni de bază ale BST.

Operațiuni de bază

# 1) Inserați

Operația de inserare adaugă un nou nod într-un arbore de căutare binară.

Algoritmul pentru operația de inserare a arborelui de căutare binară este dat mai jos.

returnarea unui tablou dintr-o metodă în java
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

După cum se arată în algoritmul de mai sus, trebuie să ne asigurăm că nodul este plasat în poziția corespunzătoare, astfel încât să nu încălcăm ordinea BST.

Introduceți operațiunea în BST

După cum vedem în secvența de mai sus a diagramelor, facem o serie de operații de inserare. După compararea cheii de inserat cu nodul rădăcină, se alege subarborele stânga sau dreapta pentru ca cheia să fie inserată ca nod frunză în poziția corespunzătoare.

# 2) Ștergeți

Operația de ștergere șterge un nod care se potrivește cu cheia dată din BST. Și în această operație, trebuie să repoziționăm nodurile rămase după ștergere, astfel încât ordinea BST să nu fie încălcată.

Prin urmare, în funcție de nodul pe care trebuie să îl ștergem, avem următoarele cazuri de ștergere în BST:

# 1) Când nodul este un nod frunză

Când nodul de șters este un nod frunză, atunci ștergem nodul direct.

Nodul este un nod frunză

# 2) Când nodul are un singur copil

Când nodul de șters are un singur copil, atunci îl copiem în nod și îl ștergem.

Nodul are un singur copil

# 3) Când nodul are doi copii

Dacă nodul care urmează să fie șters are doi copii, atunci găsim succesorul inorder pentru nod și apoi copiem succesorul inorder în nod. Ulterior, ștergem succesorul inorder.

Node are doi copii

În arborele de mai sus pentru a șterge nodul 6 cu doi copii, găsim mai întâi succesorul inorder pentru acel nod care trebuie șters. Găsim succesorul inorder găsind valoarea minimă în subarborele potrivit. În cazul de mai sus, valoarea minimă este 7 în subarborele din dreapta. Îl copiem în nodul de șters și apoi ștergem succesorul inorder.

# 3) Căutare

Operațiunea de căutare a BST caută un anumit element identificat ca „cheie” în BST. Avantajul căutării unui articol în BST este că nu trebuie să căutăm întregul arbore. În schimb, din cauza ordonării în BST, comparăm doar cheia cu rădăcina.

Dacă cheia este aceeași cu rădăcina, atunci vom reveni la rădăcină. Dacă cheia nu este rădăcină, atunci o comparăm cu rădăcina pentru a determina dacă trebuie să căutăm subarborele din stânga sau din dreapta. Odată ce găsim subarborele, trebuie să căutăm cheia și o căutăm recursiv în oricare dintre subarburi.

Urmează algoritmul pentru o operațiune de căutare în 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

Operațiunea de căutare în BST

Dacă dorim să căutăm o cheie cu valoarea 6 în arborele de mai sus, atunci mai întâi comparăm cheia cu nodul rădăcină, adică if (6 == 7) => Nu dacă (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Apoi coborâm spre sub arborele din stânga. Dacă (6 == 5) => Nu.

Dacă (6 Nu; aceasta înseamnă 6> 5 și trebuie să ne deplasăm spre dreapta.

Dacă (6 == 6) => Da; se găsește cheia.

# 4) Traversări

Am discutat deja traversările pentru arborele binar. Și în cazul BST, putem traversa arborele pentru a intra în ordine, preordonare sau secvență postordonată. De fapt, atunci când traversăm BST în secvența Inorder01, atunci obținem secvența sortată.

Am arătat acest lucru în ilustrația de mai jos.

traversări

Traversele pentru arborele de mai sus sunt după cum urmează:

Trecere în ordine (lnr): 3 5 6 7 8 9 10
Traversare precomandă (nlr): 7 5 3 6 9 8 10
Traversare PostOrder (lrn): 3 6 5 8 10 9 7

Ilustrare

Să construim un arbore de căutare binară din datele date mai jos.

45 30 60 65 70

Să luăm primul element ca nod rădăcină.

# 1) 45

nod rădăcină

În pașii următori, vom plasa datele în conformitate cu definiția arborelui de căutare binară, adică dacă datele sunt mai mici decât nodul părinte, atunci vor fi plasate la copilul din stânga și dacă datele sunt mai mari decât nodul părinte, atunci va fi copilul potrivit.

Acești pași sunt arătați mai jos.

# 2) 30

Arborele de căutare binară Pasul 1 30

# 3) 60

Arborele de căutare binară Pasul 2 60

# 4) 65

11 Arborele binar de căutare pasul 3

întrebări și răspunsuri la interviu cu analistul sistemului de afaceri

# 5) 70

Arborele de căutare binar pasul 4

Când efectuăm traversarea inorderului pe BST de mai sus pe care tocmai l-am construit, secvența este după cum urmează.

Secvența de traversare în ordine

Putem vedea că secvența de traversare are elemente dispuse în ordine crescătoare.

Implementarea arborelui de căutare binară C ++

Să demonstrăm BST și operațiunile sale folosind implementarea 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):'<

Ieșire:

Arborele de căutare binar creat (traversarea Inorder):

30 40 60 65 70

Ștergeți nodul 40

Trecere în ordine pentru arborele de căutare binară modificat:

30 60 65 70

În programul de mai sus, trimitem BST pentru secvența de traversare în ordine.

Avantajele BST

# 1) Căutarea este foarte eficientă

Avem toate nodurile BST într-o ordine specifică, prin urmare căutarea unui anumit articol este foarte eficientă și mai rapidă. Acest lucru se datorează faptului că nu trebuie să căutăm întregul copac și să comparăm toate nodurile.

Trebuie doar să comparăm nodul rădăcină cu elementul pe care îl căutăm și apoi decidem dacă trebuie să căutăm în subarborele din stânga sau din dreapta.

# 2) Funcționare eficientă în comparație cu tablourile și listele legate

Când căutăm un articol în cazul BST, scăpăm de jumătate din subarborele stâng sau drept la fiecare pas, îmbunătățind astfel performanța operațiunii de căutare. Acest lucru este în contrast cu tablourile sau listele legate în care trebuie să comparăm secvențial toate articolele pentru a căuta un anumit articol.

# 3) Inserarea și ștergerea sunt mai rapide

Operațiile de inserare și ștergere sunt, de asemenea, mai rapide în comparație cu alte structuri de date, cum ar fi listele și matricile legate.

Aplicații ale BST

Unele dintre aplicațiile majore ale BST sunt următoarele:

  • BST este utilizat pentru a implementa indexarea pe mai multe niveluri în aplicațiile de baze de date.
  • BST este, de asemenea, utilizat pentru a implementa construcții precum un dicționar.
  • BST poate fi utilizat pentru a implementa diverși algoritmi de căutare eficienți.
  • BST este, de asemenea, utilizat în aplicații care necesită o listă sortată ca intrare, cum ar fi magazinele online.
  • BST-urile sunt, de asemenea, utilizate pentru a evalua expresia folosind arbori de expresie.

Concluzie

Arborii de căutare binari (BST) sunt o variație a arborelui binar și sunt folosiți pe scară largă în domeniul software. Ele sunt, de asemenea, numite copaci binari ordonați, deoarece fiecare nod din BST este plasat în conformitate cu o ordine specifică.

Trecerea în ordine a BST ne oferă secvența sortată a articolelor în ordine crescătoare. Când BST-urile sunt utilizate pentru căutare, este foarte eficient și se face în cel mai scurt timp. BST-urile sunt, de asemenea, utilizate pentru o varietate de aplicații, cum ar fi codarea lui Huffman, indexarea pe mai multe niveluri în baze de date etc.

=> Citiți aici seria populară de formare C ++.

Lectură recomandată

^