Arbre binaire de recherche

1. Opération de recherche sur l’arbre binaire de recherche
2. Algorithme de recherche BST
3. Illustration de la recherche BST
4. Insertion dans BST
5. Algorithme d’insertion BST
6. Illustration d’insertion BST
7. Implémentation de la recherche et de l’insertion dans les BST
8. Complexité de l’algorithme d’insertion et de recherche de la BST

L’arbre binaire de recherche (BST) est une structure de données à base de nœuds ordonnés et d’arborescence binaire. Les nœuds ont une valeur et deux nœuds enfants (un arbre binaire a un maximum de deux nœuds enfants) qui lui sont attachés à gauche et à droite. À l’exception du nœud racine, tous les nœuds ne peuvent être référencés que par leur parent. Une BST a les propriétés suivantes :

• Tous les nœuds du sous-arbre de gauche sont plus petits que le nœud racine.
• Tous les nœuds du sous-arbre de droite sont plus grands que le nœud racine.
• Les sous-arbres de gauche et de droite doivent également être des arbres de recherche binaires.

L’arbre de gauche satisfait à toutes les propriétés de la BST. En revanche, l’arbre de droite semble être une BST car tous les nœuds du sous-arbre de gauche sont plus petits et ceux du sous-arbre de droite sont plus grands. Mais le noeud 1 du sous-arbre de gauche ne satisfait pas les propriétés de la BST car il est plus petit que le noeud 4 mais pas plus grand que le noeud racine 3. Il ne s’agit donc pas d’une BST.

Comme il s’agit d’une structure de données ordonnée, les éléments saisis sont toujours organisés de manière ordonnée. Nous pouvons utiliser la traversée en ordre pour récupérer les données stockées dans la BST dans un ordre trié. Il porte son nom car, tout comme la recherche binaire, il peut être utilisé pour rechercher les données dans O(logn).

Opération de recherche sur l’arbre binaire de recherche

Nous savons que dans une BST, tous les éléments du côté droit de la racine sont plus grands, et donc si l’élément cible que nous recherchons est plus petit que la racine, tout le sous-arbre droit peut être négligé. De même, si l’élément est plus grand que la racine, alors le sous-arbre gauche peut être négligé. Nous nous déplaçons de la même manière jusqu’à ce que nous épuisions l’arbre ou que nous trouvions l’élément cible comme racine du sous-arbre. Si la BST est équilibrée (un arbre est dit équilibré si, pour tous les nœuds, la différence entre la hauteur du sous-arbre gauche et du sous-arbre droit est inférieure à 1), la recherche dans la BST s’effectue de manière similaire à une recherche binaire car les deux sous-arbres contiennent environ la moitié des éléments qui sont négligés à chaque itération, mais dans le cas d’un arbre déséquilibré, tous les nœuds peuvent être présents du même côté et la recherche peut s’effectuer de manière similaire à une recherche linéaire.

Algorithme de recherche BST

Soit root le noeud racine de BST et X l’élément cible recherché.

Illustration de la recherche BST

Supposons que nous ayons la BST ci-dessus, et que nous voulions trouver l’élément X = 25.

Insertion dans BST

L’algorithme d’insertion d’un élément dans la BST est assez similaire à la recherche d’un élément dans la BST car avant d’insérer un élément, nous devons trouver sa position correcte. La seule différence entre la fonction d’insertion et la fonction de recherche est qu’en cas de recherche, nous renvoyons le nœud contenant la valeur cible, alors qu’en cas d’insertion, nous créons un nouveau nœud à la position appropriée du nœud.

Algorithme d’insertion BST

Soit root le nœud racine de BST et X l’élément que nous voulons insérer.

Illustration d’insertion BST

C’est ainsi que nous insérons des éléments dans un BST.

Implémentation de la recherche et de l’insertion dans les BST

#include <iostream>
using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
};

Node *newNode(int item) {
  Node *temp = (Node *)malloc(sizeof(Node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

void inorder(Node *root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

Node *insert(Node *root, int key) {
  if (root == NULL) return newNode(key);
  if (key < root->key)
    root->left = insert(root->left, key);
  else
    root->right = insert(root->right, key);

  return root;
}

Node *search(Node *root, int key) {
  if (root == NULL || root->key == key) return root;

  if (root->key < key) return search(root->right, key);

  return search(root->left, key);
}
int main() {
  Node *root = NULL;
  root = insert(root, 5);
  root = insert(root, 3);
  root = insert(root, 8);
  root = insert(root, 6);
  root = insert(root, 4);
  root = insert(root, 2);
  root = insert(root, 1);
  root = insert(root, 7);
  cout << search(root, 5)->key << endl;
}

Complexité de l’algorithme d’insertion et de recherche de la BST

Complexité du temps

• Cas moyen

En moyenne, la complexité temporelle de l’insertion d’un nœud ou de la recherche d’un élément dans une BST est de l’ordre de la hauteur de l’arbre binaire de recherche. En moyenne, la hauteur d’une BST est de O(logn). Elle se produit lorsque la BST formée est une BST équilibrée. Par conséquent, la complexité temporelle est de l’ordre de [Big Theta] : O(logn).

• Meilleur cas

Le meilleur cas se produit lorsque l’arbre est une BST équilibrée. Dans le meilleur des cas, la complexité temporelle de l’insertion et de la recherche est de l’ordre de O(logn). C’est la même chose que la complexité temporelle dans le cas moyen.

• Pire cas

Dans le pire des cas, nous pourrions avoir à traverser de la racine au nœud feuille le plus profond, c’est-à-dire toute la hauteur h de l’arbre. Si l’arbre est déséquilibré, c’est-à-dire qu’il est biaisé, la hauteur de l’arbre peut devenir n, et par conséquent, la complexité temporelle dans le pire des cas des opérations d’insertion et de recherche est O(n).

Complexité spatiale

La complexité spatiale de l’opération d’insertion et de recherche est O(n) en raison de l’espace requis par les appels récursifs.