Implémenter une structure de données d'arborescence de recherche binaire en C++

1. Implémenter un arbre de recherche binaire à l’aide du mot-clé struct en C++
2. Implémenter l’algorithme de recherche binaire pour un arbre de recherche binaire en C++

Ce guide montrera comment implémenter une structure de données d’arbre de recherche binaire en C++.

Implémenter un arbre de recherche binaire à l’aide du mot-clé struct en C++

Un arbre de recherche binaire (BST) est un cas particulier d’une structure de données d’arbre binaire. La structure de données est généralement utilisée pour stocker une liste triée d’éléments pour une recherche rapide à l’aide de l’algorithme de recherche binaire. Contrairement à l’arbre binaire régulier, BST a un membre de données spécial dans chaque nœud appelé key, qui doit avoir des valeurs uniques.

Chaque nœud d’un BST doit satisfaire à l’exigence suivante : la valeur key doit être supérieure à toutes les clés du sous-arbre de son enfant de gauche et inférieure à toutes les clés du sous-arbre de son enfant de droite. L’instruction précédente implique que les éléments avec des valeurs de clé inférieures seront positionnés sur le côté gauche de la hiérarchie de l’arborescence ; cela se traduit par une structure optimale sur laquelle utiliser la recherche binaire.

Dans l’exemple de code suivant, nous définissons une struct nommée BSTreeNode, composée de deux pointeurs vers les nœuds gauche/droite et d’un membre string pour désigner la clé. Notez que nous implémentons simplement la version la plus simple de BST, où la valeur de la clé est la même que les données stockées dans le nœud.

Généralement, le programmeur est libre de définir un nœud BST pour stocker d’autres membres de données selon les besoins du problème spécifique. Cette définition est la mieux adaptée pour émuler le tableau trié de chaînes, qui doit être recherché pour une chaîne (clé) donnée. Avant d’implémenter la fonction de recherche binaire, l’objet BST doit être construit à partir de zéro. Ainsi, nous utilisons un vector de chaînes prédéfini pour initialiser un nouvel arbre de recherche binaire.

La fonction insertNode est l’implémentation récursive pour créer un nouveau fils BSTreeNode lorsque la racine de l’arbre est passée en argument. Si nous devons créer un nœud racine lui-même, vous pouvez déclarer un pointeur sur le type BSTreeNode, lui affecter nullptr et le passer au insertNode avec la valeur string correspondante qui doit y être stockée. Une fois que nous avons initialisé la liste avec le contenu v1, la fonction printTree peut être invoquée pour imprimer toutes les valeurs clés dans l’ordre trié appelé le parcours inorder de BST.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

void printTree(BSTreeNode *n) {
  if (n != nullptr) {
    printTree(n->left);
    cout << n->key << "; ";
    printTree(n->right);
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printTree(root);

  return EXIT_SUCCESS;
}

Production:

aim;
born;
camel;
maya;
wind;
xen;
zero;

Implémenter l’algorithme de recherche binaire pour un arbre de recherche binaire en C++

L’algorithme de recherche binaire est efficace sur la structure BST en raison de l’ordre, où les clés sont stockées dans la hiérarchie. Il existe trois opérations principales implémentées pour les BST : insertion, suppression et recherche.

Dans l’exemple suivant, nous nous concentrons davantage sur la recherche. La fonction findNode est responsable de la recherche de la clé donnée dans le BST, qui est transmise à une fonction à l’aide de son nœud racine. Cette commande est de nature récursive et renvoie le pointeur vers le BSTreeNode où est stockée la clé. Si la valeur de la clé n’est trouvée dans aucun nœud, nullptr est renvoyé. Pour une meilleure démonstration, nous avons également implémenté une fonction printNode qui prend le pointeur du nœud et renvoie la valeur de la clé au flux cout pour enchaîner la valeur de retour de la fonction findNode directement dans la fonction pour l’imprimer.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

BSTreeNode *findNode(BSTreeNode *root, const string &k) {
  if (root == nullptr) return nullptr;

  if (k == root->key) return root;

  if (k < root->key)
    return findNode(root->left, k);
  else
    return findNode(root->right, k);
}

void printNode(BSTreeNode *n) {
  if (n != nullptr) {
    cout << n->key << endl;
  } else {
    cout << "Not a valid node!" << endl;
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printNode(findNode(root, "zero"));
  printNode(findNode(root, "zeroo"));

  return EXIT_SUCCESS;
}

Production:

zero Not a valid node !