Vérification de l'arbre binaire de recherche

  2. Tutoriel
  3. Structure de données
  4. Vérification de l'arbre binaire de …
Harshit Jindal 12 octobre 2023
Data Structure Binary Tree Binary Search Tree
  1. L’algorithme de vérification de l’arbre binaire est l’arbre binaire de recherche
  2. Implémentation de l’algorithme de vérification de l’arbre binaire est l’arbre binaire de recherche
  3. Analyse de la complexité
Vérification de l'arbre binaire de recherche

Un arbre binaire est une structure de données non linéaire. Il est appelé arbre binaire parce que chaque nœud a un maximum de deux enfants. Ces enfants sont appelés enfants de gauche et enfants de droite. Pour qu’un arbre binaire devienne BST, il doit satisfaire les propriétés suivantes :

  • Tous les nœuds du sous-arbre 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’algorithme de vérification de l’arbre binaire est l’arbre binaire de recherche

Algorithme 1

Dans cette approche, nous vérifions si le sous-arbre de gauche contient un élément supérieur à la valeur de la racine et si le sous-arbre de droite contient un élément inférieur à la valeur de la racine en considérant chaque nœud comme la racine de son sous-arbre. Pour trouver l’élément max et min, nous devons utiliser deux fonctions distinctes, getMin() et getMax().

getMin()

  • Initialise temp en tant que root.
  • Tant que temp a une gauche, procédez comme suit:
    • Réglez temp sur temp->left, c’est-à-dire déplacez-vous vers la gauche pour trouver le plus petit élément.
  • Renvoie temp->val comme valeur minimale à l’intérieur de ce sous-arbre.

getMax()

  • Initialise temp en tant que root.
  • Tant que temp a un right, procédez comme suit:
    • Réglez temp sur temp->right, c’est-à-dire déplacez-vous vers la droite pour trouver le plus grand élément.
  • Renvoie temp->val comme valeur maximale à l’intérieur de ce sous-arbre.

isBST(root)

  • Si la root est NULL, renvoie true.
  • Trouvez l’élément maximum maxm dans le sous-arbre de gauche en appelant getMax(root->left);
  • Trouvez l’élément minimum minm dans le sous-arbre de droite en appelant getMin(root->right);
  • Si l’élément racine est plus petit que maxm ou supérieur à minm, renvoie false.
  • Vérifiez récursivement tous les nœuds en appelant isBST(root->left) et isBST(root->right). Si les deux appels récursifs retournent true alors l’arbre est BST, retournez true sinon retournez false.

L’algorithme ci-dessus nous dit si un arbre est BST ou non mais est extrêmement lent. Les fonctions getMin() et getMax() ont une complexité temporelle de O(n) dans le pire des cas et sont appelées pour des noeuds n rendant la complexité temporelle totale O(n2).

Algorithme 2 :

Cet algorithme améliore l’algorithme précédent en n’effectuant pas de calculs répétés. L’approche précédente appelait getMin() et getMax() pour chaque noeud. Cette approche améliore l’approche précédente en gardant une trace des valeurs minimales et maximales autorisées lorsque nous traversons les nœuds.

isBST(root)

  • Initialise deux variables min comme INT_MIN et max comme INT_MAX.
  • Appelez isBST(root,min,max).

isBST(root, min, max)

  • Si la root est NULL, renvoie true.
  • Si min> root->data alors la propriété BST est violée, renvoie false.
  • Si max < root->data alors la propriété BST est violée, renvoie false.
  • Vérifiez récursivement le sous-arbre de gauche en appelant isBST(root->left, min, root->data-1) (en passant min et root->data - 1 comme arguments, cela change la plage valide pour BST dans le sous-arbre de gauche) et le sous-arbre de droite en appelant isBST(root->right, root->data+1, max) (en passant root->data + 1 et max comme arguments, cela change la plage valide pour BST dans le sous-arbre de droite).
  • Si les deux appels récursifs renvoient true alors l’arbre est BST, retournez true.

La complexité temporelle de cet algorithme est de O(n), ce qui est une amélioration significative par rapport à la méthode précédente.

Algorithme 3 :

Cet algorithme évite d’utiliser INT_MIN et INT_MAX dans l’algorithme ci-dessus en les remplaçant par deux pointeurs, l et r.

isBST(root)

  • Initialise deux nœuds l et r comme NULL.
  • Appelez isBST(root, l, r). (Appel de fonction surchargé)

isBST(root, l, r)

  • Si la root est NULL, renvoie true.
  • Si l n’est pas NULL et l->data> = root->data alors la propriété BST est violée, renvoie false.
  • Si r n’est pas NULL et r->data <= root->data alors la propriété BST est violée, renvoie false.
  • Vérifiez récursivement le sous-arbre de gauche en appelant isBST(root->left, left, root) (en passant root comme 3e argument change la limite de valeur minimale pour le sous-arbre) et le sous-arbre de droite en appelant isBST(root->right, root, right)(passer root comme 2ème argument change la limite de valeur maximale pour le sous-arbre).
  • Si les deux appels récursifs renvoient true, alors l’arborescence est BST, renvoie true.

Algorithme 4 :

Le parcours dans l’ordre de l’arbre binaire de recherche renvoie les éléments dans un ordre trié. Nous pouvons utiliser cette propriété pour vérifier si un arbre binaire est BST. Si tous les éléments de la traversée dans l’ordre ne sont pas en ordre croissant, alors l’arbre donné n’est pas un arbre binaire de recherche.

isBST(root)

  • Initialisez la variable prev comme INT_MIN. prev est utilisé pour vérifier si le noeud courant est plus grand que prev et donc suit l’ordre de tri.
  • Appelez isBST(root, prev). (Appel de fonction surchargé).

isBST(root,prev)

  • Si la root est NULL, renvoie true.
  • Vérifier récursivement le sous-arbre gauche par isBST(root->left, prev). S’il renvoie false, alors renvoie false.
  • Si root->data <= prev. l’ordre croissant est violé, retourne false.
  • Mettre à jour prev->data en tant que root->data.
  • Vérifier récursivement le sous-arbre de droite par isBST(root->right, prev). S’il renvoie false, alors renvoie false.
  • Sinon, renvoie vrai.

Implémentation de l’algorithme de vérification de l’arbre binaire est l’arbre binaire de recherche

Algorithme 1

#include <iostream>
using namespace std;

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

  return root->data;
}
int getMax(Node* root) {
  while (root->right) {
    root = root->right;
  }

  return root->data;
}
bool isBST(Node* root) {
  if (root == NULL) return true;

  if (root->left != NULL && getMax(root->left) > root->data) return false;

  if (root->right != NULL && getMin(root->right) < root->data) return false;

  if (!isBST(root->left) || !isBST(root->right)) return false;

  return true;
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algorithme 2

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int min, int max) {
  if (root == NULL) return 1;
  if (root->data < min || root->data > max) return 0;

  return isBST(root->left, min, root->data - 1) &&
         isBST(root->right, root->data + 1, max);
}

bool isBST(Node* root) { return isBST(root, INT_MIN, INT_MAX); }
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algorithme 3

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, Node* l, Node* r) {
  if (root == NULL) return true;

  if (l != NULL and root->data <= l->data) return false;
  if (r != NULL and root->data >= r->data) return false;

  return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST(Node* root) {
  Node* l = NULL;
  Node* r = NULL;
  return isBST(root, l, r);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algorithme 4

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int& prev) {
  if (!root) return true;

  if (!isBST(root->left, prev)) return false;

  if (root->data <= prev) return false;
  prev = root->data;

  return isBST(root->right, prev);
}

bool isBST(Node* root) {
  int prev = INT_MIN;
  return isBST(root, prev);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Analyse de la complexité

Complexité du temps

  • Cas moyen

Pour vérifier si l’arbre binaire donné est BST ou non, nous devons traverser tous les noeuds n car un seul noeud défiant les propriétés conduira à ce que l’arbre ne soit pas BST. La complexité temporelle est donc de l’ordre de [Big Theta] : O(n).

  • Meilleur cas

Dans le meilleur des cas, la complexité temporelle est de l’ordre de O(n). C’est la même chose que la complexité temporelle moyenne.

  • Pire cas

La complexité temporelle dans le pire des cas est de l’ordre de O(n). Elle est identique à la complexité temporelle du meilleur cas.

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