Insertion itérative de l'arbre binaire de recherche

Harshit Jindal 15 février 2024
  1. Algorithme d’insertion itérative dans la BST
  2. Illustration de l’insertion itérative de BST
  3. Implémentation de l’insertion itérative dans une BST
  4. Complexité de l’algorithme d’insertion itérative de la BST
Insertion itérative de l'arbre binaire de recherche

Dans l’article précédent [arbre binaire de recherche](/fr/tutorial/data-structure/binary-search-tree/, nous avons discuté de l’approche récursive pour insérer un nœud dans BST. Dans cet article, nous discuterons de l’approche itérative pour insérer un noeud dans BST. Elle est meilleure que la méthode récursive car l’algorithme d’insertion itérative ne nécessite pas d’espace supplémentaire.

Algorithme d’insertion itérative dans la BST

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

  • Créez le nœud à insérer - toinsert.
  • Initialisez deux pointeurs, curr pointant sur root et prev pointant sur null. (curr traverse l’arbre et prev maintient sa trace).
  • Si curr != NULL, faites ce qui suit :
    • Mettez à jour prev pour qu’il soit curr pour maintenir sa trace.
    • si curr->data > key, mettez curr à curr->left, supprimez le sous-arbre de droite.
    • si curr->data < key, mettre curr à curr->right, supprimer le sous-arbre de gauche.
  • Si prev == NULL, cela signifie que l’arbre est vide. Créez le noeud root.
  • Sinon, si prev->data > key alors insérez toinsert à gauche de prev, prev->left = toinsert.
  • Sinon, si prev->data < key alors insérez toinsert à droite de prev, prev->right = toinsert.

Illustration de l’insertion itérative de BST

Illustration de l&rsquo;insert itératif de la BST

  • Tout d’abord, nous initialisons la BST en créant un nœud root et en y insérant 5.
  • 3 est plus petit que 5, donc il est inséré à gauche de 5.
  • 4 est plus petit que 5 mais plus grand que 3, donc il est inséré à droite de 3 mais à gauche de 4.
  • 2 est le plus petit élément de l’arbre courant, il est donc inséré à la position la plus à gauche.
  • 1 est le plus petit élément dans l’arbre courant, il est donc inséré à la position la plus à gauche.
  • 6 est le plus grand élément de l’arbre courant, il est donc inséré à la position la plus à droite.

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

Implémentation de l’insertion itérative dans une BST

#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;
}

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);
}

Complexité de l’algorithme d’insertion itérative de la BST

Complexité du temps

  • Cas moyen

En moyenne, la complexité temporelle de l’insertion d’un nœud 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 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 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 donc la complexité temporelle dans le pire des cas, tant pour l’insertion que pour la recherche, est O(n).

Complexité spatiale

La complexité spatiale de l’opération itérative d’insertion est de O(1) car aucun espace supplémentaire n’est nécessaire.

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