Inserto iterativo de árbol binario de búsqueda

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

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.

Ilustración de inserto iterativo BST

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.