Convertir árbol binario en árbol binario de búsqueda

  1. Algoritmo de conversión de árbol binario a BST
  2. Convertir árbol binario en ilustración BST
  3. Convertir árbol binario en BST Implementación
  4. Convierta el árbol binario en la complejidad del algoritmo BST

Un árbol binario es una estructura de datos no lineal. Se llama árbol binario porque cada nodo tiene un máximo de dos hijos. Estos niños se llaman niños izquierdos y niños derechos. También se puede interpretar como un gráfico no dirigido en el que el nodo superior se llama raíz. Un árbol binario de búsqueda (BST) es un árbol binario con propiedades especiales que ayuda a mantener los datos organizados de forma ordenada.

En este tutorial, discutiremos cómo convertir un árbol binario a BST manteniendo la estructura original del árbol binario.

Algoritmo de conversión de árbol binario a BST

  • Crea un array llamada arr para almacenar el recorrido en orden de los nodos del árbol binario.
  • Ordenar arr usando cualquier algoritmo de ordenación (MergeSort O(nlogn), QuickSort O(n ^ 2), Insertion Sort O(n^2), etc.).
  • Nuevamente, haz el recorrido en orden del árbol y almacena los elementos en el árbol binario del array ordenada arr para producir la BST.

Convertir árbol binario en ilustración BST

Árbol binario a la ilustración BST

  • Llamamos cruce de orden en el nodo raíz 4. Recorre recursivamente a la izquierda para llegar al nodo 1, que es el nodo más a la izquierda, e inclúyelo en nuestra salida; como es la raíz y no tiene un nodo izquierdo, rastreamos hasta el nodo 2 y lo incluimos en nuestro recorrido. De esta manera, recorremos todo el árbol y almacenamos el recorrido en orden en el array arr como [1, 2, 3, 5, 4, 6].
  • Ordena el array arr usando cualquier algoritmo de ordenación para obtener [1, 2, 3, 4, 5, 6].
  • Volvemos a llamar al inorder traversal para almacenar el array arr ordenado de nuevo en el árbol binario para obtener nuestro BST.

Convertir árbol binario en BST Implementación

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

Convierta el árbol binario en la complejidad del algoritmo BST

Complejidad del tiempo

  • Caso promedio

La complejidad de tiempo de hacer el recorrido en orden en el que almacenamos el array en sorted y almacenamos el array sorted en el árbol binario es O(n). Pero, la complejidad de ordenar el array es O(nlogn) y, por lo tanto, la complejidad total se da como O(nlogn) + 2*O(n). La complejidad del tiempo es del orden de O(nlogn).

  • Mejor caso

La complejidad del tiempo en el mejor de los casos es del orden de O(n). Cuando el árbol binario dado ya es una BST, hacemos el recorrido en orden para realizarlo y no se requieren operaciones de clasificación.

  • Peor caso

La complejidad de tiempo en el peor de los casos es del orden de O(nlogn).

Complejidad espacial

La complejidad espacial del algoritmo es O(n) debido al espacio extra requerido por las llamadas recursivas.

Artículo relacionado - Data Structure

  • Inserto iterativo de árbol binario de búsqueda
  • Recorrido de árbol binario
  • Verificación del árbol binario de búsqueda
  • Artículo relacionado - Binary Tree

  • Inserto iterativo de árbol binario de búsqueda
  • Recorrido de árbol binario
  • Verificación del árbol binario de búsqueda
  • Artículo relacionado - Binary Search Tree

  • Inserto iterativo de árbol binario de búsqueda
  • Recorrido de árbol binario
  • Verificación del árbol binario de búsqueda