Eliminar nodos en un árbol binario de búsqueda es una de las operaciones más interesantes y, a la vez, más complejas que podemos encontrar. Para abordar esta tarea, primero debemos localizar el nodo que queremos eliminar, algo que ya conocemos gracias a la búsqueda en árboles binarios. Pero la verdadera dificultad aparece cuando analizamos cuántos hijos tiene ese nodo, porque la estrategia para eliminarlo varía según si es una hoja, tiene un solo hijo o tiene dos hijos.
Cuando el nodo a eliminar es una hoja, la operación es bastante sencilla. Simplemente eliminamos ese nodo y actualizamos la referencia de su padre para que apunte a null, asegurándonos de que no quede ninguna referencia colgando. Por ejemplo, si queremos eliminar un nodo con valor 16 que no tiene hijos, solo tenemos que destruir ese nodo y hacer que su padre deje de apuntar a él.
Si el nodo tiene un solo hijo, la cosa cambia un poco. No podemos simplemente eliminar el nodo porque perderíamos toda la información contenida en su hijo. En este caso, lo que hacemos es reemplazar el nodo que queremos eliminar por su hijo. Esto significa que la referencia del padre del nodo eliminado debe apuntar ahora al hijo de ese nodo. Por ejemplo, si eliminamos un nodo con valor 12 que tiene un hijo con valor 8, la referencia que apuntaba a 12 debe actualizarse para apuntar a 8. De esta forma, mantenemos intacta la estructura del árbol y no perdemos datos.
El caso más complicado es cuando el nodo a eliminar tiene dos hijos. Aquí no podemos simplemente promover uno de los hijos porque perderíamos la estructura ordenada del árbol. La solución pasa por encontrar un nodo que pueda reemplazar al nodo eliminado sin romper las propiedades del árbol binario de búsqueda. Para ello, buscamos el nodo máximo del subárbol izquierdo o el nodo mínimo del subárbol derecho.
Buscar el nodo máximo del subárbol izquierdo significa recorrer la rama derecha de ese subárbol hasta encontrar un nodo que no tenga hijo derecho. Ese nodo será el mayor valor en ese subárbol. Por otro lado, buscar el nodo mínimo del subárbol derecho implica recorrer la rama izquierda de ese subárbol hasta encontrar un nodo sin hijo izquierdo, que será el menor valor en ese subárbol.
Una vez localizado ese nodo, lo promovemos para que ocupe la posición del nodo que queremos eliminar. Esto implica copiar el valor de ese nodo en la raíz del subárbol que estamos modificando. Sin embargo, ahora tenemos dos nodos con el mismo valor, por lo que debemos eliminar recursivamente el nodo que acabamos de promover desde su posición original.
Para ilustrar esto, imaginemos que queremos eliminar la raíz de un árbol con valor 36 que tiene dos hijos. Si optamos por usar el mínimo del subárbol derecho, buscamos el nodo más a la izquierda en ese subárbol, que podría ser el 41. Colocamos el 41 en la raíz y luego eliminamos el nodo 41 original, que en este caso es sencillo porque es una hoja. Si en cambio elegimos el máximo del subárbol izquierdo, buscamos el nodo más a la derecha en ese subárbol, que podría ser el 16. Lo promovemos a la raíz y luego eliminamos el nodo 16 original, que puede tener un hijo, por lo que aplicamos la estrategia para nodos con un solo hijo.
En resumen, eliminar un nodo en un árbol binario de búsqueda requiere primero identificar el tipo de nodo. Si es una hoja, lo eliminamos directamente. Si tiene un hijo, promovemos ese hijo. Y si tiene dos hijos, buscamos el máximo del subárbol izquierdo o el mínimo del subárbol derecho para reemplazarlo, y luego eliminamos recursivamente el nodo promovido desde su posición original.
Para que quede más claro, podemos pensar en una función recursiva que elimine un nodo dado un valor, siguiendo estas reglas. Aquí un ejemplo en Java que refleja esta lógica:
class Nodo {
int valor;
Nodo izquierdo, derecho;
Nodo(int valor) {
this.valor = valor;
izquierdo = derecho = null;
}
}
public class ArbolBinarioBusqueda {
Nodo raiz;
public Nodo eliminar(Nodo nodo, int valor) {
if (nodo == null) return null;
if (valor < nodo.valor) {
nodo.izquierdo = eliminar(nodo.izquierdo, valor);
} else if (valor > nodo.valor) {
nodo.derecho = eliminar(nodo.derecho, valor);
} else {
// Nodo encontrado
if (nodo.izquierdo == null && nodo.derecho == null) {
// Caso hoja
return null;
} else if (nodo.izquierdo == null) {
// Un hijo (derecho)
return nodo.derecho;
} else if (nodo.derecho == null) {
// Un hijo (izquierdo)
return nodo.izquierdo;
} else {
// Dos hijos
// Buscar mínimo en subárbol derecho
Nodo minDerecho = encontrarMinimo(nodo.derecho);
nodo.valor = minDerecho.valor;
nodo.derecho = eliminar(nodo.derecho, minDerecho.valor);
}
}
return nodo;
}
private Nodo encontrarMinimo(Nodo nodo) {
while (nodo.izquierdo != null) {
nodo = nodo.izquierdo;
}
return nodo;
}
}
Este código refleja la estrategia que hemos comentado: primero buscamos el nodo a eliminar, luego aplicamos la eliminación según el número de hijos, y en el caso de dos hijos, promovemos el mínimo del subárbol derecho y eliminamos ese nodo duplicado.
Con esta base, podemos seguir construyendo las operaciones típicas de un árbol binario de búsqueda, como inserción, búsqueda y recorridos, para tener una estructura completa y funcional.