Árbol binario de búsqueda: Eliminar

Harshit Jindal 12 octubre 2023
  1. Eliminar operación en el árbol binario de búsqueda
  2. Ilustración de eliminación de árbol binario de búsqueda
  3. Algoritmo de eliminación de BST
  4. Implementación de eliminación de árbol binario de búsqueda
  5. Complejidad del algoritmo de eliminación de árbol binario de búsqueda
Árbol binario de búsqueda: Eliminar

En el artículo árbol binario de búsqueda: buscar e insertar, discutimos cómo insertar un elemento en una BST y cómo busque un valor en una BST. En este artículo, discutiremos cómo eliminar un nodo del árbol binario de búsqueda.

Eliminar operación en el árbol binario de búsqueda

Insertar un nodo en BST es relativamente simple. Pero, al eliminar un nodo, tenemos que ocuparnos de múltiples posibilidades. Pueden ocurrir los siguientes 3 casos:

Este es el caso más simple; dado que un nodo hoja no tiene hijos, no necesitamos preocuparnos por nada. Podemos reemplazar el nodo hoja con NULL y liberar el espacio asignado a este nodo.

En este caso, almacenamos el hijo del nodo y eliminamos el nodo de su posición original. Luego, el nodo hijo se inserta en la posición original del nodo eliminado.

Este es el caso más complicado porque aquí, no podemos simplemente eliminar o reemplazar el nodo con su hijo. En este caso, encontramos el nodo más pequeño en el subárbol derecho del nodo minnode. Reemplace el valor del nodo que se eliminará con el valor de minnode y llame de forma recursiva a delete en este nodo.

Ilustración de eliminación de árbol binario de búsqueda

Algoritmo de eliminación de BST

Implementación de eliminación de árbol binario de búsqueda

C
++ cCopy#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;
  }
}

Node* getmin(Node* root) {
  Node* curr = root;

  while (curr && curr->left) {
    curr = curr->left;
  }

  return curr;
}

Node* deleteNode(Node* root, int key) {
  if (root == NULL) return root;

  if (key < root->key)
    root->left = deleteNode(root->left, key);

  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    if (root->left == NULL) {
      Node* temp = root->right;
      delete (root);
      return temp;
    } else if (root->right == NULL) {
      Node* temp = root->left;
      delete (root);
      return temp;
    }

    Node* temp = getmin(root->right);

    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

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);
  cout << "\n";
  deleteNode(root, 5);
  inorder(root);
}

Complejidad del algoritmo de eliminación de árbol binario de búsqueda

Complejidad del tiempo

  • Caso promedio

En el caso promedio, la complejidad temporal de eliminar un nodo de una 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 eliminació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 de tiempo en el peor de los casos de las operaciones de inserción y búsqueda es O(n).

Complejidad espacial

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

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