Menu

Arborescence de recherche binaire C ++: implémentation et opérations BST avec exemples

  • Principal
  • Autre
  • Arborescence de recherche binaire C ++: implémentation et opérations BST avec exemples

binary search tree c

Essayez Notre Instrument Pour Éliminer Les Problèmes

Tutoriel détaillé sur l'arbre de recherche binaire (BST) en C ++, y compris les opérations, l'implémentation C ++, les avantages et les exemples de programmes:

Un arbre de recherche binaire ou BST comme on l'appelle couramment est un arbre binaire qui remplit les conditions suivantes:

  1. Les nœuds qui sont inférieurs au nœud racine qui est placé comme enfants à gauche du BST.
  2. Les nœuds qui sont supérieurs au nœud racine qui est placé comme les bons enfants du BST.
  3. Les sous-arbres gauche et droit sont à leur tour les arbres de recherche binaire.

Cette disposition consistant à ordonner les touches dans une séquence particulière permet au programmeur d'effectuer des opérations telles que la recherche, l'insertion, la suppression, etc. plus efficacement. Si les nœuds ne sont pas classés, nous devrons peut-être comparer chaque nœud avant de pouvoir obtenir le résultat de l'opération.

=> Consultez la série complète de formations C ++ ici.

Arborescence de recherche binaire en C ++

Ce que vous apprendrez:

Arbre de recherche binaire C ++

Un exemple de BST est présenté ci-dessous.

Échantillon BST

Les arbres de recherche binaires sont également appelés «arbres binaires ordonnés» en raison de cet ordre spécifique des nœuds.

À partir du BST ci-dessus, nous pouvons voir que le sous-arbre gauche a des nœuds inférieurs à la racine, c'est-à-dire 45, tandis que le sous-arbre droit a les nœuds supérieurs à 45.

Parlons maintenant de quelques opérations de base de BST.

Opérations de base

# 1) Insérer

L'opération d'insertion ajoute un nouveau nœud dans une arborescence de recherche binaire.

L'algorithme pour l'opération d'insertion d'arbre de recherche binaire est donné ci-dessous.

meilleure suppression gratuite de virus et de logiciels malveillants
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

Comme le montre l'algorithme ci-dessus, nous devons nous assurer que le nœud est placé à la position appropriée afin de ne pas violer l'ordre BST.

Insérer une opération dans BST

Comme nous le voyons dans la séquence de diagrammes ci-dessus, nous effectuons une série d'opérations d'insertion. Après avoir comparé la clé à insérer avec le nœud racine, le sous-arbre gauche ou droit est choisi pour la clé à insérer en tant que nœud feuille à la position appropriée.

# 2) Supprimer

L'opération de suppression supprime un nœud qui correspond à la clé donnée de BST. Dans cette opération également, nous devons repositionner les nœuds restants après la suppression afin que l'ordre BST ne soit pas violé.

Par conséquent, en fonction du nœud que nous devons supprimer, nous avons les cas suivants pour la suppression dans BST:

# 1) Lorsque le nœud est un nœud feuille

Lorsque le nœud à supprimer est un nœud feuille, nous supprimons directement le nœud.

Le nœud est un nœud feuille

# 2) Lorsque le nœud n'a qu'un seul enfant

Lorsque le nœud à supprimer n'a qu'un seul enfant, nous copions l'enfant dans le nœud et supprimons l'enfant.

Le nœud n

# 3) Lorsque le nœud a deux enfants

Si le nœud à supprimer a deux enfants, nous trouvons le successeur inorder du nœud, puis nous copions le successeur inorder sur le nœud. Plus tard, nous supprimons le successeur inorder.

Node a deux enfants

Dans l'arborescence ci-dessus pour supprimer le nœud 6 avec deux enfants, nous trouvons d'abord le successeur inorder pour ce nœud à supprimer. Nous trouvons le successeur dans l'ordre en trouvant la valeur minimale dans le bon sous-arbre. Dans le cas ci-dessus, la valeur minimale est 7 dans le sous-arbre de droite. Nous le copions sur le nœud à supprimer, puis supprimons le successeur en ordre.

# 3) Recherche

L'opération de recherche de BST recherche un élément particulier identifié comme «clé» dans le BST. L'avantage de rechercher un élément dans BST est que nous n'avons pas besoin de rechercher l'ensemble de l'arborescence. Au lieu de cela, à cause de l'ordre dans BST, nous comparons simplement la clé à la racine.

Si la clé est la même que root, nous retournons root. Si la clé n'est pas root, nous la comparons avec la racine pour déterminer si nous devons rechercher le sous-arbre gauche ou droit. Une fois que nous avons trouvé le sous-arbre, nous devons rechercher la clé dans, et nous la recherchons de manière récursive dans l'un ou l'autre des sous-arbres.

Voici l'algorithme pour une opération de recherche dans 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

Opération de recherche dans BST

Si nous voulons rechercher une clé avec la valeur 6 dans l'arborescence ci-dessus, nous comparons d'abord la clé avec le nœud racine, c'est-à-dire si (6 == 7) => Non si (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Ensuite, nous descendons vers le sous-arbre de gauche. Si (6 == 5) => Non.

Si (6 Non; cela signifie 6> 5 et nous devons avancer vers la droite.

Si (6 == 6) => Oui; la clé est trouvée.

# 4) Traversées

Nous avons déjà discuté des traversées pour l'arbre binaire. Dans le cas de BST également, nous pouvons parcourir l'arborescence pour obtenir une séquence inOrder, preorder ou postOrder. En fait, lorsque nous traversons le BST dans la séquence Inorder01, nous obtenons la séquence triée.

Nous l'avons montré dans l'illustration ci-dessous.

traversées

Les traversées de l'arbre ci-dessus sont les suivantes:

Traversée en ordre (lnr): 3 5 6 7 8 9 10
Parcours de précommande (nlr): 7 5 3 6 9 8 10
Traversée PostOrder (lrn): 3 6 5 8 10 9 7

Illustration

Construisons un arbre de recherche binaire à partir des données ci-dessous.

45 30 60 65 70

Prenons le premier élément comme nœud racine.

# 1) 45

Noeud principal

Dans les étapes suivantes, nous placerons les données selon la définition de l'arborescence de recherche binaire, c'est-à-dire si les données sont inférieures au nœud parent, elles seront placées à l'enfant de gauche et si les données sont supérieures au nœud parent, alors elles sera le bon enfant.

Ces étapes sont illustrées ci-dessous.

# 2) 30

Arbre de recherche binaire Étape 1 30

# 3) 60

Arborescence de recherche binaire Étape 2 60

# 4) 65

11 Arbre de recherche binaire step3

# 5) 70

Arbre de recherche binaire étape 4

Lorsque nous effectuons la traversée dans l'ordre sur le BST ci-dessus que nous venons de construire, la séquence est la suivante.

Séquence de traversée en ordre

Nous pouvons voir que la séquence de parcours comporte des éléments disposés par ordre croissant.

Implémentation d'arbre de recherche binaire C ++

Laissez-nous démontrer BST et ses opérations en utilisant l'implémentation 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):'<

Production:

Arborescence de recherche binaire créée (parcours Inorder):

30 40 60 65 70

Supprimer le nœud 40

Traversée en ordre pour l'arborescence de recherche binaire modifiée:

30 60 65 70

Dans le programme ci-dessus, nous sortons le BST pour une séquence de parcours dans l'ordre.

Avantages de BST

# 1) La recherche est très efficace

Nous avons tous les nœuds de BST dans un ordre spécifique, donc la recherche d'un élément particulier est très efficace et plus rapide. En effet, nous n'avons pas besoin de rechercher l'ensemble de l'arbre et de comparer tous les nœuds.

Nous devons simplement comparer le nœud racine à l'élément que nous recherchons, puis nous décidons si nous devons rechercher dans le sous-arbre gauche ou droit.

# 2) Travail efficace par rapport aux tableaux et aux listes liées

applications qui espionnent d'autres téléphones

Lorsque nous recherchons un élément en cas de BST, nous nous débarrassons de la moitié du sous-arbre gauche ou droit à chaque étape, améliorant ainsi les performances de l'opération de recherche. Cela contraste avec les tableaux ou les listes chaînées dans lesquels nous devons comparer tous les éléments de manière séquentielle pour rechercher un élément particulier.

# 3) L'insertion et la suppression sont plus rapides

Les opérations d'insertion et de suppression sont également plus rapides par rapport à d'autres structures de données telles que les listes liées et les tableaux.

Applications de BST

Certaines des principales applications de la BST sont les suivantes:

  • BST est utilisé pour implémenter l'indexation à plusieurs niveaux dans les applications de base de données.
  • BST est également utilisé pour implémenter des constructions comme un dictionnaire.
  • BST peut être utilisé pour implémenter divers algorithmes de recherche efficaces.
  • BST est également utilisé dans les applications qui nécessitent une liste triée comme entrée, comme les magasins en ligne.
  • Les BST sont également utilisés pour évaluer l'expression à l'aide d'arbres d'expression.

Conclusion

Les arbres de recherche binaire (BST) sont une variante de l'arbre binaire et sont largement utilisés dans le domaine des logiciels. Ils sont également appelés arbres binaires ordonnés car chaque nœud de BST est placé selon un ordre spécifique.

La traversée en ordre de BST nous donne la séquence triée des éléments dans l'ordre croissant. Lorsque les BST sont utilisés pour la recherche, cela est très efficace et se fait en un rien de temps. Les BST sont également utilisés pour diverses applications telles que le codage de Huffman, l'indexation à plusieurs niveaux dans les bases de données, etc.

=> Lisez la série de formations populaires C ++ ici.

lecture recommandée

^