Cuando trabajamos con árboles binarios de búsqueda en C, una de las operaciones más complejas pero fundamentales es la eliminación de nodos. Para abordar esta tarea con eficacia, es necesario considerar los distintos casos que pueden presentarse: eliminar una hoja, eliminar un nodo con un solo hijo o eliminar un nodo con dos hijos. Para facilitar estas operaciones, una mejora clave es modificar la estructura del nodo para que cada uno tenga una referencia a su padre. Esto nos permite manejar las conexiones entre nodos de forma más sencilla y clara.
Empezamos por añadir un campo padre en la estructura del nodo y adaptamos la función que crea nodos para que reciba también el nodo padre. Esto implica modificar la función de inserción para que, además del árbol y el valor a insertar, reciba el padre del nodo actual. Para no complicar la interfaz pública, creamos una función estática interna que maneja la inserción con el padre, y una función pública que inicia la inserción pasando NULL como padre para la raíz.
Para comprobar que la referencia al padre funciona correctamente, podemos modificar la función de recorrido inorden para que imprima, además del valor del nodo, el valor de su padre cuando exista. Así confirmamos que cada nodo conoce a su padre, lo que será fundamental para la eliminación.
Antes de implementar la eliminación, definimos algunas funciones de apoyo. La primera es obtener, que busca un nodo con un valor dado dentro del árbol. Esta función es recursiva y sigue la lógica del árbol binario de búsqueda: si el árbol está vacío, devuelve NULL; si el valor coincide con el nodo actual, devuelve ese nodo; si el valor es menor, busca en el subárbol izquierdo; si es mayor, en el derecho.
Otra función importante es reemplazar, que nos permite cambiar un nodo por otro en la estructura del árbol. Esta función recibe el nodo a reemplazar y el nuevo nodo que ocupará su lugar. Primero verifica que el nodo a reemplazar tenga padre; si es así, determina si es hijo izquierdo o derecho y actualiza el puntero correspondiente del padre para que apunte al nuevo nodo. Además, si el nuevo nodo no es NULL, actualiza su referencia al padre para mantener la conexión bidireccional.
Con estas herramientas, podemos abordar la función principal de eliminación. La función eliminar busca el nodo con el valor a eliminar usando la función obtener. Si el nodo no existe o el árbol está vacío, no hace nada. Cuando encuentra el nodo, llama a una función auxiliar eliminarNodo que maneja los distintos casos.
Si el nodo a eliminar es una hoja (sin hijos), simplemente usamos reemplazar para que el padre deje de apuntar a él, pasando NULL como nuevo nodo, y luego liberamos la memoria del nodo eliminado.
Si el nodo tiene un solo hijo, ya sea izquierdo o derecho, usamos reemplazar para que el padre del nodo eliminado apunte directamente a ese hijo, y luego liberamos el nodo eliminado. Esto mantiene la estructura del árbol sin perder nodos.
El caso más complejo es cuando el nodo a eliminar tiene dos hijos. Para resolverlo, buscamos el nodo mínimo del subárbol derecho, que será el sucesor en orden del nodo a eliminar. Implementamos una función minimo que, dado un árbol, devuelve el nodo con el valor mínimo recorriendo recursivamente el hijo izquierdo hasta que no haya más. Una vez obtenido este nodo mínimo, copiamos su valor al nodo que queremos eliminar y luego eliminamos el nodo mínimo del subárbol derecho, que ahora está duplicado. Esto mantiene la propiedad del árbol binario de búsqueda.
Para ilustrar, si eliminamos la raíz que tiene dos hijos, el valor de la raíz se reemplaza por el mínimo del subárbol derecho, y luego eliminamos ese nodo mínimo, que será un caso más sencillo (hoja o con un solo hijo).
Con estas funciones y modificaciones, tenemos una implementación completa y robusta para eliminar nodos en árboles binarios de búsqueda en C, manejando todos los casos posibles y manteniendo la integridad del árbol. Además, al encapsular las funciones auxiliares como estáticas, limitamos su visibilidad al archivo fuente, manteniendo el código limpio y modular.