Convertir l'arbre binaire en arbre binaire de recherche

1. Algorithme de conversion d’un arbre binaire en BST
2. Convertir l’arbre binaire en illustration BST
3. Convertir l’arbre binaire en implémentation BST
4. Convertir l’arbre binaire en complexité d’algorithme BST

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. Il peut également être interprété comme un graphe non dirigé dans lequel le nœud supérieur est appelé racine. Un arbre binaire de recherche (BST) est un arbre binaire avec des propriétés spéciales qui permet de garder les données organisées de manière ordonnée.

Dans ce tutoriel, nous verrons comment convertir un arbre binaire en BST tout en conservant la structure originale de l’arbre binaire.

Algorithme de conversion d’un arbre binaire en BST

Convertir l’arbre binaire en illustration BST

Convertir l’arbre binaire en implémentation BST

#include <bits/stdc++.h>
using namespace std;

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

void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
  }
}

void storetree(Node* root, int i = 0) {
  if (!root) {
    return;
  }
  storetree(root->left);
  v.push_back(root->data);
  storetree(root->right);
}

void restoretree(Node* root, int& i) {
  if (!root) {
    return;
  }
  restoretree(root->left, i);
  root->data = v[i];
  i++;
  restoretree(root->right, i);
}

void converttoBST(Node* root) {
  if (!root) {
    return;
  }
  storetree(root);
  sort(v.begin(), v.end());
  int i = 0;
  restoretree(root, i);
}

int main() {
  Node* root = new Node(3);
  root->left = new Node(1);
  root->right = new Node(7);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->left->left->right = new Node(2);
  root->right->left = new Node(6);
  root->right->right = new Node(9);
  root->right->right->left = new Node(8);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
  converttoBST(root);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
}

Convertir l’arbre binaire en complexité d’algorithme BST

Complexité du temps

• Cas moyen

La complexité temporelle de la traversée dans l’ordre dans laquelle nous stockons le tableau dans sorted et stockons le tableau sorted dans l’arborescence binaire est O(n). Mais, la complexité du tri du tableau est O(nlogn) et donc la complexité totale est donnée par O(nlogn) + 2 * O(n). La complexité temporelle est de l’ordre de O(nlogn).

• Meilleur cas

La complexité temporelle dans le meilleur des cas est de l’ordre de O(n). Lorsque l’arbre binaire donné est déjà un BST, nous effectuons la traversée dans l’ordre pour le réaliser, et aucune opération de tri n’est requise.

• Pire cas

La complexité temporelle dans le pire des cas est de l’ordre de O(nlogn).

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.