Insertion itérative de l'arbre binaire de recherche

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

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.

Illustration de l’insertion itérative de BST

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.