Inserto iterativo de árbol binario de búsqueda

Harshit Jindal 15 febrero 2024
  1. Algoritmo de inserción iterativa BST
  2. Ilustración de inserto iterativo BST
  3. Implementación de inserto iterativo BST
  4. Complejidad del algoritmo de inserción iterativa BST
Inserto iterativo de árbol binario de búsqueda

En el artículo anterior Árbol binario de búsqueda, discutimos el enfoque recursivo para insertar un nodo en BST. En esta publicación, discutiremos el enfoque iterativo para insertar un nodo en BST. Es mejor que el método recursivo, ya que el algoritmo de inserción iterativo no requiere espacio adicional.

Algoritmo de inserción iterativa BST

Sea root el nodo raíz de BST y key el elemento que queremos insertar.

  • Crea el nodo a insertar - toinsert.
  • Inicializa dos punteros, curr apunta a root y prev apunta a nulo. (curr atraviesa el árbol y prev mantiene su rastro).
  • Mientras curr != NULL, haz lo siguiente:
    • Actualice prev para que sea curr para mantener su estela.
    • si curr->data > key, establezca curr en curr->left, descarte el subárbol derecho.
    • si curr->data < key, establezca curr en curr->right, descarte el subárbol izquierdo.
  • Si prev == NULL, significa que el árbol está vacío. Cree el nodo root.
  • De lo contrario, si prev->data > key, inserte toinsert a la izquierda de prev, prev->left = toinsert.
  • De lo contrario, si prev->data < key, inserte toinsert a la derecha de prev, prev->right = toinsert.

Ilustración de inserto iterativo BST

Ilustración de inserto iterativo BST

  • Primero, inicializamos BST creando un nodo root e insertamos 5 en él.
  • 3 es menor 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 en el árbol actual, por lo que se inserta en la posición más a la izquierda.
  • 1 es el elemento más pequeño en el árbol actual, por lo que se inserta en la posición más a la izquierda.
  • 6 es el elemento más grande en el árbol actual, por lo que se inserta en la posición más a la derecha.

Así es como insertamos elementos dentro de una BST.

Implementación de inserto iterativo BST

#include <iostream>
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) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

void insert(Node *&root, int key) {
  Node *toinsert = newNode(key);
  Node *curr = root;
  Node *prev = NULL;

  while (curr != NULL) {
    prev = curr;
    if (key < curr->key)
      curr = curr->left;
    else
      curr = curr->right;
  }
  if (prev == NULL) {
    prev = toinsert;
    root = prev;
  }

  else if (key < prev->key)
    prev->left = toinsert;

  else
    prev->right = toinsert;
}

int main() {
  Node *root = NULL;
  insert(root, 5);
  insert(root, 3);
  insert(root, 8);
  insert(root, 6);
  insert(root, 4);
  insert(root, 2);
  insert(root, 1);
  insert(root, 7);
  inorder(root);
}

Complejidad del algoritmo de inserción iterativa BST

Complejidad del tiempo

  • Caso promedio

En el caso promedio, la complejidad de tiempo de insertar un nodo en un BST es del orden de la altura del árbol binario de búsqueda. En promedio, la altura de un BST es O(logn). Ocurre cuando la BST formada es una BST equilibrada. Por tanto, la complejidad del tiempo es del orden de [Big Theta]: O(logn).

  • Mejor caso

El mejor de los casos ocurre cuando el árbol es una BST equilibrada. La complejidad de tiempo de inserción en el mejor de los casos es del orden de O(logn). Es lo mismo que la complejidad del tiempo promedio de los casos.

  • Peor caso

En el peor de los casos, podríamos tener que atravesar desde la raíz hasta el nodo de la hoja más profundo, es decir, toda la altura h del árbol. Si el árbol está desequilibrado, es decir, está sesgado, la altura del árbol puede convertirse en n y, por lo tanto, la complejidad temporal en el peor de los casos de la operación de inserción y de búsqueda es O(n).

Complejidad espacial

La complejidad espacial de la operación de inserción iterativa es O(1) porque no se requiere espacio adicional.

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

Artículo relacionado - Data Structure

Artículo relacionado - Binary Tree

Artículo relacionado - Binary Search Tree