Tri arborescent

1. Algorithme de tri arborescent
2. Exemple de tri arborescent
3. Implémentation d’algorithme de tri arborescent
4. Complexité de l’algorithme de tri arborescent

Le tri arborescent est un algorithme de tri en ligne. Il utilise la structure de données de arborescent de recherche binaire pour stocker les éléments. Les éléments peuvent être récupérés dans un ordre trié en effectuant une recherche dans l’ordre de l’arborescent de recherche binaire. Comme il s’agit d’un algorithme de tri en ligne, les éléments insérés sont toujours gérés dans l’ordre trié.

Algorithme de tri arborescent

Supposons que nous ayons un tableau non trié A[] contenant n éléments.

TreeSort()

Insert()

Inorder()

Exemple de tri arborescent

Supposons que nous ayons le tableau : (5, 3, 4, 2, 1, 6). Nous allons le trier en utilisant l’algorithme de tri par insertion.

Tout d’abord, nous initialisons BST en créant le nœud racine 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’arborescent courant, il est donc inséré à la position la plus à gauche.

1 est le plus petit élément de l’arborescent courant, il est donc inséré à la position la plus à gauche.

6 le plus grand élément de l’arborescent courant, il est donc inséré à la position la plus à droite.

Après la construction du BST, nous effectuons un parcours dans l’ordre sur l’arborescent pour obtenir le tableau trié final (1, 2, 3 ,4, 5, 6).

Implémentation d’algorithme de tri arborescent

#include <bits/stdc++.h>

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, int arr[], int &i) {
  if (root != NULL) {
    inorder(root->left, arr, i);
    arr[i++] = root->key;
    inorder(root->right, arr, i);
  }
}

Node *insertintoBST(Node *node, int key) {
  if (node == NULL) return newNode(key);
  if (key < node->key)
    node->left = insertintoBST(node->left, key);
  else if (key > node->key)
    node->right = insertintoBST(node->right, key);
  return node;
}

void treeSort(int arr[], int n) {
  Node *root = NULL;
  root = insertintoBST(root, arr[0]);
  for (int i = 1; i < n; i++) root = insertintoBST(root, arr[i]);
  int i = 0;
  inorder(root, arr, i);
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  treeSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complexité de l’algorithme de tri arborescent

Complexité temporelle

• Cas moyen

Dans le cas moyen, la complexité temporelle de l’insertion de noeuds n dans une BST est de l’ordre de O(nlogn). Elle se produit lorsque la BST formée est une BST équilibrée. La complexité temporelle est donc de l’ordre de [Big Theta] : O(nlogn).

• Pire cas

Le pire cas se produit lorsque le tableau est trié, et qu’un arbre de recherche binaire déséquilibré ayant une hauteur maximale de O(n) est formé. Il nécessite un temps de parcours O(n) et un temps d’insertion O(n²) par rapport au temps de parcours O(logn) dans le cas d’un BST régulier de hauteur logn. Le pire cas de complexité temporelle est [Big O] : O(n²).

Elle peut être réduite à O(nlogn) en utilisant une structure de données auto-équilibrée comme l’arborescent AVL, l’arborescent Rouge-Noir, etc.

• Meilleur cas

Le meilleur cas se produit lorsque l’arborescent de recherche binaire formé est équilibré. Le meilleur cas de complexité temporelle est [Big Omega] : O(nlogn). C’est la même chose que la complexité temporelle dans le cas moyen.

Complexité spatiale

La complexité spatiale de cet algorithme est O(n) parce que des nœuds doivent être créés pour chaque élément à l’intérieur de l’arborescent de recherche binaire.