Menú

Arbre de cerca binària C ++: implementació i operacions de BST amb exemples

  • Principal
  • Altres
  • Arbre de cerca binària C ++: implementació i operacions de BST amb exemples

binary search tree c

Proveu El Nostre Instrument Per Eliminar Problemes

Tutorial detallat sobre l'arbre de cerca binària (BST) a C ++ que inclou operacions, implementació de C ++, avantatges i programes d'exemple:

Un arbre de cerca binari o BST, com es coneix popularment, és un arbre binari que compleix les condicions següents:

  1. Els nodes que són menors que el node arrel que es col·loca com a fills secundaris del BST.
  2. Els nodes que són més grans que el node arrel que es col·loca com a fills adequats del BST.
  3. Els subarbres esquerre i dret són al seu torn els arbres de cerca binaris.

Aquesta disposició d’ordenar les tecles en una seqüència concreta facilita al programador realitzar operacions com ara cercar, inserir, suprimir, etc. de manera més eficient. Si els nodes no estan ordenats, hauríem de comparar tots i cadascun dels nodes abans de poder obtenir el resultat de l'operació.

=> Consulteu aquí la sèrie completa de formació C ++.

Arbre de cerca binària en C ++

Què aprendreu:

Arbre de cerca binària C ++

A continuació es mostra un exemple de BST.

BST de mostra

Els arbres binaris de cerca també es coneixen com a 'arbres binaris ordenats' a causa d'aquesta ordenació específica de nodes.

Des del BST anterior, podem veure que el subarbre esquerre té nodes inferiors a l’arrel, és a dir, 45, mentre que el subarbre dret té els nodes superiors a 45.

Ara anem a discutir algunes operacions bàsiques de BST.

Operacions bàsiques

# 1) Insereix

L'operació d'inserció afegeix un nou node en un arbre de cerca binari.

A continuació es mostra l'algorisme per a l'operació d'inserció d'arbre de cerca binària.

enrutador d'equilibri de càrrega dues connexions a Internet
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

Com es mostra a l'algorisme anterior, hem d'assegurar-nos que el node es col·loqui a la posició adequada de manera que no infringim l'ordre BST.

Inseriu l

Com veiem a la seqüència de diagrames anterior, fem una sèrie d'operacions d'inserció. Després de comparar la clau que cal inserir amb el node arrel, es tria el subarbre esquerre o dret perquè la clau s'insereixi com a node fulla a la posició adequada.

# 2) Suprimeix

L'operació d'eliminació elimina un node que coincideix amb la clau donada de BST. També en aquesta operació, hem de canviar la posició dels nodes restants després de suprimir-los de manera que no es infringeixi l'ordre BST.

Per tant, segons el node que hem de suprimir, tenim els casos següents per suprimir-los a BST:

# 1) Quan el node és un node de fulla

Quan el node que voleu suprimir és un node fulla, suprimim directament el node.

Node és un node de fulla

# 2) Quan el node només té un fill

Quan el node a suprimir només té un fill, el copiem al node i el suprimim.

Node només té un fill

# 3) Quan el node té dos fills

Si el node a suprimir té dos fills, trobem el successor de l'ordenació del node i després copiem el successor de l'ordenació al node. Més tard, suprimim el successor inorder.

Node té dos fills

A l’arbre anterior per esborrar el node 6 amb dos fills, primer trobem el successor inorder perquè aquest node se suprimeixi. Trobem el successor inorder en trobar el valor mínim al subarbre dret. En el cas anterior, el valor mínim és 7 al subarbre dret. El copiem al node que voleu suprimir i, a continuació, suprimim el successor de l'ordre.

# 3) Cerca

L'operació de cerca de BST busca un element concret identificat com a 'clau' al BST. L’avantatge de cercar un element a BST és que no hem de fer cerques a tot l’arbre. En lloc d’això, per l’ordenació a BST, només comparem la clau amb l’arrel.

Si la clau és la mateixa que l'arrel, retornem l'arrel. Si la clau no és arrel, la comparem amb l'arrel per determinar si hem de buscar al subarbre esquerre o dret. Un cop trobem el subarbre, hem de cercar la clau i la cerquem recursivament a qualsevol dels subarbres.

A continuació es mostra l’algorisme per a una operació de cerca a 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

Operació de cerca a BST

Si volem cercar una clau amb el valor 6 a l’arbre anterior, primer comparem la clau amb el node arrel, és a dir, if (6 == 7) => No si (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

A continuació baixem cap al subarbre esquerre. Si (6 == 5) => No.

Si (6 No; això significa 6> 5 i ens hem de desplaçar cap a la dreta.

Si (6 == 6) => Sí; es troba la clau.

# 4) Traversals

Ja hem comentat els recorreguts de l'arbre binari. També en el cas de BST, podem travessar l’arbre per obtenir una seqüència d’ordre, preordre o postordre. De fet, quan travessem el BST en la seqüència Inorder01, obtenim la seqüència ordenada.

Ho hem demostrat a la següent il·lustració.

travessies

Les travessies de l’arbre anterior són les següents:

Recorregut per ordre (lnr): 3 5 6 7 8 9 10
Recorregut per ordre previ (nlr): 7 5 3 6 9 8 10
Recorregut PostOrder (lrn): 3 6 5 8 10 9 7

Il·lustració

Construïm un arbre de cerca binària a partir de les dades que es donen a continuació.

45 30 60 65 70

Prenguem el primer element com a node arrel.

# 1) 45

node arrel

En els passos posteriors, col·locarem les dades segons la definició de l’arbre de cerca binària, és a dir, si les dades són inferiors al node pare, es col·locaran al fill esquerre i si les dades són més grans que el node pare, serà el nen adequat.

tipus de bombolla c ++ codi

Aquests passos es mostren a continuació.

# 2) 30

Arbre de cerca binària Pas 1 30

# 3) 60

Arbre de cerca binària Pas 2 60

# 4) 65

11 Pas 3 de l

# 5) 70

Pas 4 de l

Quan realitzem el recorregut desordenat al BST anterior que acabem de construir, la seqüència és la següent.

Seqüència de recorregut inorder

Podem veure que la seqüència de recorregut té elements disposats en ordre ascendent.

Implementació de l'arbre de cerca binària C ++

Demostrem BST i les seves operacions mitjançant la implementació de 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):'<

Sortida:

S'ha creat l'arbre de cerca binària (recorregut de l'ordre):

30 40 60 65 70

Suprimiu el node 40

Recorregut per ordre de l'arbre de cerca binari modificat:

30 60 65 70

Al programa anterior, publiquem el BST per a una seqüència de recorregut ordenada.

Avantatges de BST

# 1) La cerca és molt eficient

Tenim tots els nodes de BST en un ordre específic, per tant, la cerca d’un article concret és molt eficient i més ràpida. Això es deu al fet que no hem de buscar a tot l'arbre i comparar tots els nodes.

Només hem de comparar el node arrel amb l’element que cerquem i després decidim si hem de cercar al subarbre esquerre o dret.

# 2) Funcionament eficient en comparació amb matrius i llistes enllaçades

Quan cerquem un element en cas de BST, ens eliminem de la meitat del subarbre esquerre o dret a cada pas, millorant així el rendiment de l'operació de cerca. Això contrasta amb matrius o llistes enllaçades en què hem de comparar tots els elements seqüencialment per cercar un element concret.

# 3) La inserció i la supressió són més ràpides

Les operacions d'inserció i supressió també són més ràpides en comparació amb altres estructures de dades, com ara llistes i matrius enllaçats.

Aplicacions de BST

Algunes de les principals aplicacions de BST són les següents:

  • BST s’utilitza per implementar la indexació multinivell en aplicacions de bases de dades.
  • BST també s'utilitza per implementar construccions com un diccionari.
  • BST es pot utilitzar per implementar diversos algoritmes de cerca eficients.
  • BST també s’utilitza en aplicacions que requereixen una llista ordenada com a entrada, com ara les botigues en línia.
  • Els BST també s’utilitzen per avaluar l’expressió mitjançant arbres d’expressió.

Conclusió

Els arbres de cerca binària (BST) són una variació de l’arbre binari i s’utilitzen àmpliament en el camp del programari. També s’anomenen arbres binaris ordenats, ja que cada node de BST es col·loca segons un ordre específic.

El recorregut desordenat de BST ens proporciona la seqüència ordenada d’elements en ordre ascendent. Quan s’utilitzen BST per fer cerques, és molt eficient i es fa en poc temps. Els BST també s’utilitzen per a diverses aplicacions com la codificació de Huffman, la indexació multinivell en bases de dades, etc.

=> Llegiu aquí la popular sèrie de formació C ++.

Lectura recomanada

^