Eliminar nodos en un árbol binario de búsqueda es una de las operaciones más complejas que podemos realizar, y para abordarla correctamente debemos considerar varios casos según la cantidad de hijos que tenga el nodo a eliminar. Lo primero que hacemos es verificar que el árbol no esté vacío; si lo está, no hay nada que eliminar. Luego, comprobamos si el nodo actual es el que queremos eliminar o si debemos buscar en alguno de sus subárboles, izquierdo o derecho, dependiendo de si el valor a eliminar es menor o mayor que el nodo actual.
Para manejar la eliminación de manera ordenada y sin sobrecargar el método principal, creamos un método privado que se encargue de eliminar el nodo una vez que sabemos que es el correcto. Este método debe contemplar tres situaciones: eliminar un nodo sin hijos, con un solo hijo o con dos hijos.
En el caso más sencillo, cuando el nodo no tiene hijos, simplemente informamos a su padre para que elimine la referencia a este nodo. Para facilitar esta operación, añadimos un campo padre en cada nodo, que nos permite conocer el nodo padre de cualquier instancia. Esto implica modificar la inserción para que, al añadir un nuevo nodo, se le asigne correctamente su padre. Cuando eliminamos un nodo sin hijos, si tiene padre, comprobamos si somos su hijo izquierdo o derecho y eliminamos esa referencia. Además, para evitar referencias colgantes, ponemos a null tanto el campo padre como el valor del nodo eliminado, ayudando así al recolector de basura.
Cuando el nodo a eliminar tiene un solo hijo, la estrategia es reemplazar el contenido del nodo con el de su único hijo. Primero identificamos si el hijo está a la izquierda o a la derecha, y luego copiamos el valor y las referencias de ese hijo en el nodo actual. De esta forma, el nodo actual se convierte en su hijo, manteniendo la estructura del árbol sin perder nodos.
El caso más complicado es cuando el nodo tiene dos hijos. Aquí, la técnica consiste en buscar el mínimo del subárbol derecho, que es el sucesor en orden del nodo a eliminar. Para ello, implementamos un método mínimo que recorre el subárbol izquierdo hasta encontrar el nodo más pequeño. Una vez localizado este mínimo, reemplazamos el valor del nodo a eliminar por el valor de este mínimo. Sin embargo, para evitar duplicados, debemos eliminar el nodo mínimo del subárbol derecho, ya que su valor ahora está en la posición del nodo eliminado originalmente.
Este enfoque garantiza que el árbol mantenga sus propiedades de búsqueda después de la eliminación. Por ejemplo, si eliminamos la raíz y el mínimo del subárbol derecho es 33, entonces 33 ocupará la posición de la raíz y desaparecerá de su posición original.
Con estas operaciones implementadas, tenemos un árbol binario de búsqueda funcional en Java que permite insertar, eliminar y buscar elementos, además de poder extenderlo con otras funcionalidades como calcular la profundidad máxima o la distancia hasta un nodo. Este ejemplo cubre los fundamentos esenciales para trabajar con árboles binarios de búsqueda y nos abre la puerta a exploraciones más avanzadas en estructuras de datos.
A continuación, mostramos cómo podría quedar el método para encontrar el mínimo en un subárbol:
public PST mínimo() {
if (izquierdo != null) {
return izquierdo.mínimo();
} else {
return this;
}
}
Y un esquema simplificado de la eliminación cuando el nodo tiene un solo hijo:
private void eliminarImpl() {
if (izquierdo != null && derecho == null) {
valor = izquierdo.valor;
derecho = izquierdo.derecho;
izquierdo = izquierdo.izquierdo;
} else if (derecho != null && izquierdo == null) {
valor = derecho.valor;
izquierdo = derecho.izquierdo;
derecho = derecho.derecho;
}
// Otros casos omitidos para brevedad
}
Con estas bases, podemos manejar la eliminación en árboles binarios de búsqueda de forma segura y eficiente.