Suppression de l'arbre binaire de recherche

  2. Tutoriel
  3. Structure de données
  4. Suppression de l'arbre binaire de …
Harshit Jindal 12 octobre 2023
Data Structure Binary Tree Binary Search Tree
  1. Opération de suppression sur l’arbre binaire de recherche
  2. Illustration de suppression d’arbre binaire de recherche
  3. Algorithme de suppression BST
  4. arbre binaire de recherche Supprimer l’implémentation
  5. arbre binaire de recherche Supprimer la complexité de l’algorithme
Suppression de l'arbre binaire de recherche

Dans l’article [arbre binaire de recherche : rechercher et insérer](/fr/tutorial/data-structure/binary-search-tree/, nous avons expliqué comment insérer un élément dans un BST et comment rechercher une valeur dans un BST. Dans cet article, nous allons examiner comment supprimer un nœud de l’arbre binaire de recherche.

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

L’insertion d’un nœud dans la BST est relativement simple. Mais, tout en supprimant un nœud, nous devons tenir compte de multiples possibilités. Les 3 cas suivants peuvent se présenter :

  • Le nœud à supprimer n’a pas d’enfant - c’est une feuille.

C’est le cas le plus simple ; comme le nœud d’une feuille n’a pas d’enfant, nous n’avons pas à nous occuper de quoi que ce soit. Nous pouvons remplacer le nœud feuille par NULL et libérer l’espace alloué à ce nœud.

  • Le nœud à supprimer n’a qu’un seul enfant (enfant gauche ou droit).

Dans ce cas, nous stockons l’enfant du nœud et nous retirons le nœud de sa position initiale. Le nœud enfant est alors inséré à la position d’origine du nœud supprimé.

  • Le nœud à supprimer a deux enfants, un enfant gauche et un enfant droit.

C’est le cas le plus délicat car ici, on ne peut pas simplement supprimer ou remplacer le nœud par son enfant. Dans ce cas, nous trouvons le plus petit nœud dans le sous-arbre droit du nœud minnode. Remplacez la valeur du nœud à supprimer par la valeur de minnode et appelez récursivement delete sur ce nœud.

Illustration de suppression d’arbre binaire de recherche

  • Le nœud à supprimer n’a pas d’enfant - c’est une feuille.

    Opération de suppression d’un arbre binaire de recherche
    Le nœud 7 n’a pas d’enfant; supprimez-le simplement de l’arborescence, aucune propriété BST n’est violée.

  • Le nœud à supprimer n’a qu’un seul enfant

    Opération de suppression de l’arbre binaire de recherche
    Le nœud 15 a un enfant 7; nous devons nous en occuper avant de supprimer 15. Donc, nous le copions d’abord, puis nous le remplaçons par 15.

  • Le nœud à supprimer a les deux enfants.

    Opération de suppression d’un arbre binaire de recherche
    Le nœud 21 a deux enfants - 15 et 27. Nous trouvons le plus petit élément dans le sous-arbre de droite 23 et le remplaçons par 21, puis nous appelons la récursion pour supprimer 23 du sous-arbre de droite.

Algorithme de suppression BST

  • Si root == NULL, alors renvoie NULL.
  • Si root->key < X, alors écartez le sous-arbre de gauche et trouvez l’élément à supprimer dans le sous-arbre de droite

    root->right = deleteNode(root->right,X)

  • Sinon, si root->key > X, il faut supprimer le sous-arbre de droite et trouver l’élément à supprimer dans le sous-arbre de gauche

    root->left = deleteNode(root->left, X)

  • Sinon si root->key == X, alors agissez selon les 3 cas:
    • Si (root->left == NULL && root->right == NULL) alors supprimez root et renvoyez NULL.
    • Sinon si (root->right == NULL) alors copiez le sous-arbre de gauche et remplacez-le par le nœud à supprimer.
    • Sinon si (root->left == NULL) alors copiez le sous-arbre de droite et remplacez-le par le nœud à supprimer.
    • Sinon si (root->left && root->right) alors trouvez le nœud minimum dans le sous-arbre droit minnode et remplacez-le par le nœud à supprimer. Supprimez récursivement minnode du sous-arbre de droite.
  • Retournez le pointeur vers la racine d’origine.

arbre binaire de recherche Supprimer l’implémentation

#include <iostream>
using namespace std;

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

Node* newNode(int item) {
  Node* temp = new 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);
  }
}

void insert(Node*& root, int key) {
  Node* toinsert = newNode(key);
  Node* curr = root;
  Node* prev = NULL;

  while (curr != NULL) {
    prev = curr;
    if (key < curr->key)
      curr = curr->left;
    else
      curr = curr->right;
  }
  if (prev == NULL) {
    prev = toinsert;
    root = prev;
  }

  else if (key < prev->key) {
    prev->left = toinsert;
  }

  else {
    prev->right = toinsert;
  }
}

Node* getmin(Node* root) {
  Node* curr = root;

  while (curr && curr->left) {
    curr = curr->left;
  }

  return curr;
}

Node* deleteNode(Node* root, int key) {
  if (root == NULL) return root;

  if (key < root->key)
    root->left = deleteNode(root->left, key);

  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    if (root->left == NULL) {
      Node* temp = root->right;
      delete (root);
      return temp;
    } else if (root->right == NULL) {
      Node* temp = root->left;
      delete (root);
      return temp;
    }

    Node* temp = getmin(root->right);

    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

int main() {
  Node* root = NULL;
  insert(root, 5);
  insert(root, 3);
  insert(root, 8);
  insert(root, 6);
  insert(root, 4);
  insert(root, 2);
  insert(root, 1);
  insert(root, 7);
  inorder(root);
  cout << "\n";
  deleteNode(root, 5);
  inorder(root);
}

arbre binaire de recherche Supprimer la complexité de l’algorithme

Complexité du temps

  • Cas moyen

En moyenne, la complexité temporelle de la suppression d’un nœud d’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 la suppression est de l’ordre de O(logn). C’est la même chose que la complexité temporelle du cas moyen.

  • Pire cas

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

Complexité spatiale

La complexité spatiale de l’algorithme est O(n) en raison de l’espace supplémentaire requis par les appels de récursion.

Auteur: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Article connexe - Data Structure

Article connexe - Binary Tree

Article connexe - Binary Search Tree