Ordenamiento con árbol binario

1. Algoritmo de ordenamiento con árbol binario
2. Ejemplo de ordenamiento con árbol binario
3. Implementación del algoritmo de ordenamiento con árbol binario
4. Complejidad del algoritmo de ordenamiento con árbol binario

La ordenamiento con árbol binario es un algoritmo de ordenación en línea. Utiliza la estructura de datos del árbol de búsqueda binaria para almacenar los elementos. Los elementos pueden ser recuperados en orden de clasificación haciendo un recorrido en orden del árbol de búsqueda binario. Como es un algoritmo de ordenación en línea, los elementos insertados se mantienen siempre en orden.

Algoritmo de ordenamiento con árbol binario

Supongamos que tenemos un array sin ordenar A[] que contiene n elementos.

TreeSort()

Insert()

Inorder()

Ejemplo de ordenamiento con árbol binario

Supongamos que tenemos el array (5, 3, 4, 2, 1, 6). Lo ordenaremos utilizando el algoritmo de ordenación por inserción.

Primero inicializamos el BST creando el nodo raíz 5.

El nodo 3 es más pequeño que 5, por lo que se inserta a la izquierda de 5.

4 es menor que 5 pero mayor que 3, por lo que se inserta a la derecha de 3 pero a la izquierda de 4.

2 es el elemento más pequeño del árbol actual, por lo que se inserta en la posición más a la izquierda.

1 es el elemento más pequeño del árbol actual, por lo que se inserta en la posición más a la izquierda.

6 es el elemento más grande del árbol actual, por lo que se inserta en la posición más a la derecha.

Una vez construido el BST, realizamos un recorrido en orden sobre el árbol para obtener el array final ordenada (1, 2, 3 ,4, 5, 6).

Implementación del algoritmo de ordenamiento con árbol binario

#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";
}

Complejidad del algoritmo de ordenamiento con árbol binario

Complejidad temporal

• Caso medio

En el caso medio, la complejidad temporal de insertar n nodos en un BST es del orden de O(nlogn). Esto ocurre cuando el BST formado es un BST equilibrado. Por tanto, la complejidad temporal es del orden de [Big Theta]: O(nlogn).

• El peor caso

El peor caso se produce cuando el array está ordenado y se forma un árbol de búsqueda binario no equilibrado con una altura máxima de O(n). Requiere un tiempo O(n) para recorrerlo y O(n²) para insertarlo, comparado con el tiempo O(logn) para recorrerlo en el caso de un BST regular de altura logn. La complejidad temporal en el peor de los casos es [Big O] O(n²).

Puede reducirse a O(nlogn) utilizando una estructura de datos autoequilibrada como el árbol AVL, el árbol rojo-negro, etc.

• El mejor caso

El mejor caso se produce cuando el árbol de búsqueda binario formado está equilibrado. La complejidad temporal del mejor caso es [Big Omega]: O(nlogn). Es la misma que la complejidad temporal del caso medio.

Complejidad espacial

La complejidad espacial de este algoritmo es O(n) porque hay que crear n nodos para cada elemento dentro del árbol de búsqueda binario.