Successeur de l'arbre de recherche binaire

1. Successeur d’ordre dans l’algorithme BST
2. Successeur d’ordre dans l’illustration BST
3. Successeur Inorder dans l’implémentation BST
4. Complexité du successeur d’ordre dans l’algorithme BST

Le successeur inorder d’un arbre binaire est le nœud qui vient ensuite dans le parcours inorder de l’arbre binaire. Donc, c’est NULL pour le dernier nœud dans l’arborescence. Puisque la traversée en ordre de l’arbre de recherche binaire est un tableau trié. Le nœud avec la plus petite clé supérieure au nœud donné est défini comme son successeur inorder. Dans un BST, il existe deux possibilités pour le successeur inorder, le nœud avec la plus petite valeur dans le sous-arbre droit ou l’ancêtre du nœud. Sinon, le successeur en ordre pour le nœud n’existe pas.

Successeur d’ordre dans l’algorithme BST

Successeur d’ordre dans l’illustration BST

Le successeur dans l’ordre de 3 est 4 parce que 3 a un noeud droit et 4 est le plus petit noeud qui est plus grand que 3 dans le sous-arbre droit.

Le successeur dans l’ordre de 4 est 5 parce que 4 n’a pas de noeud droit, et nous devons regarder ses ancêtres et parmi eux, 5 est le plus petit noeud qui est plus grand que 4.

Successeur Inorder dans l’implémentation BST

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};

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

Node* getNextleft(Node* root) {
  while (root->left) {
    root = root->left;
  }

  return root;
}

void inorderSuccessor(Node* root, Node*& succ, int key) {
  if (root == NULL) {
    succ = NULL;
    return;
  }

  if (root->data == key) {
    if (root->right) {
      succ = getNextleft(root->right);
    }
  }

  else if (key < root->data) {
    succ = root;
    inorderSuccessor(root->left, succ, key);
  } else {
    inorderSuccessor(root->right, succ, key);
  }
}

int main() {
  int keys[] = {1, 5, 8, 2, 6, 3, 7, 4};
  Node* root = NULL;
  for (int key : keys) {
    root = insert(root, key);
  }
  for (int key : keys) {
    Node* prec = NULL;
    inorderSuccessor(root, prec, key);
    if (prec) {
      cout << "Inorder successor of node " << key << " is " << prec->data;
    } else {
      cout << "No inorder Successor of node " << key;
    }

    cout << '\n';
  }

  return 0;
}

Complexité du successeur d’ordre dans l’algorithme BST

Complexité du temps

• Cas moyen

En moyenne, la complexité temporelle de la recherche d’un successeur en ordre dans une BST est de l’ordre de la hauteur de l’arbre de recherche binaire. 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 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’algorithme est O(h) en raison de l’espace supplémentaire requis par les appels de récursion.