Árbol binario de búsqueda: Eliminar

  2. Tutorial
  3. Estructura de datos
  4. Árbol binario de búsqueda: Eliminar
Harshit Jindal 12 octubre 2023
Data Structure Binary Tree Binary Search Tree
  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:

  • El nodo que se va a eliminar no tiene hijo, es una hoja.

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.

  • El nodo que se va a eliminar tiene un solo hijo (hijo izquierdo o derecho).

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.

  • El nodo que se va a eliminar tiene hijos, hijo izquierdo y derecho.

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

  • El nodo que se va a eliminar no tiene hijo, es una hoja.

    Operación de eliminación del árbol binario de búsqueda
    El nodo 7 no tiene hijos; simplemente elimínelo del árbol, no se viola ninguna propiedad BST.

  • El nodo que se va a eliminar tiene un solo hijo

    Operación de eliminación del árbol binario de búsqueda
    El nodo 15 tiene un hijo 7; tenemos que encargarnos de ello antes de borrar 15. Entonces, lo copiamos primero y luego lo reemplazamos con 15.

  • El nodo que se va a eliminar tiene ambos hijos.

    Operación de eliminación del árbol binario de búsqueda
    El nodo 21 tiene dos hijos: 15 y 27. Encontramos el elemento más pequeño en el subárbol derecho 23 y lo reemplazamos con 21, y luego llamamos a la recursividad para eliminar 23 del subárbol derecho.

Algoritmo de eliminación de BST

  • Si root == NULL, devuelve NULL.
  • Si root->key < X, descarta el subárbol izquierdo y busca el elemento que se eliminará en el subárbol derecho

    root->right = deleteNode(root->right, X)

  • De lo contrario, si root->key > X, descarta el subárbol derecho y busca el elemento que se eliminará en el subárbol izquierdo

    root->left = deleteNode(root->left, X)

  • De lo contrario, si root->key == X, actúe de acuerdo con los 3 casos:
    • Si (root->left == NULL && root->right == NULL) entonces borre root y devuelva NULL.
    • De lo contrario, si (root->right == NULL), entonces copie el subárbol izquierdo y reemplácelo con el nodo a eliminar.
    • De lo contrario, si (root->left == NULL) entonces copie el subárbol derecho y reemplácelo con el nodo a eliminar.
    • De lo contrario, si (root->left && root->right), busque el nodo mínimo en el subárbol derecho minnode y sustitúyalo por el nodo a eliminar. Elimina de forma recursiva minnode del subárbol derecho.
  • Devuelve el puntero a la raíz original.

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

#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.

Autor: Harshit Jindal
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