[C] Eliminando Nodo de Arbol Binario (Solucionado)

[AlbertoBSD]

Tengo un detalle al momento de eliminar un nodo del arbol binario.

Dada la estructura:

Código (c) [Seleccionar] Expandir

struct nodo {
struct nodo *padre;
struct nodo *izquierdo;
struct nodo *derecho;
char *valor;
};

Ya puedo agregar y buscar nodos sin problema y al momento de eliminar nodos hay varios casos ya aborde la mayoria de ellos solo tengo un detalle con el ultimo.

Casos:

• El Nodo a eliminar no tiene hijos (Listo)
• El Nodo a eliminar solo tiene un hijo derecho o izquierdo (Listo)
• El Nodo a eliminar tiene ambos hijos (Pendiente)

El detalles es el decidir como reconectar los nodos cuando el noda eliminar tiene 2 hijos... (Si es un problema de algoritmo pero lo pongo aqui por que esta en C)

Si esos 2 hijos no tienen hijos no hay problema simplemente selecciono uno y lo pongo en el lugar del nodo eliminado. Pero el peor de los casos es cuando ambos nodos tienes 2 hijos cada uno mas o menos asi:

Código [Seleccionar] Expandir

      p
      |
->     n
    /   \
   d     i
  / \   / \
 d   i d   i


La pregunta que tengo aqui seria la siguiente...

Tengo que hacer una funcion que reconecte y reorganize los nodos del arbol ¿Que recomendarian ustedes una funcion iterativa o una recursiva?

La otra solucion que tengo es manejar el nodo a eliminar como un arbol independiente desvincularlo del arbol principal y recorrer este nuevo subarbol de izquierda a derecha o viceversa y agregar cada nodo del subarbol al arbol principal, con excepcion de nodo a eliminar que seria la raiz del subarbol.

¿Que recomiendan ustedes?

La funcion que tengo es la siguiente:

Código (c) [Seleccionar] Expandir

void eliminar_nodo(struct nodo *arbol,char *valor) {
struct nodo *n;
struct nodo *padre;
struct nodo *derecho;
struct nodo *izquierdo;
if(debug_arbol)
debug_arbol = 0;
n = buscar_valor(arbol,valor);
if(n) {

if(n->derecho == NULL && n->izquierdo == NULL) {
//No tiene hijos, hay que determinar si es el hijo derecho o izquierdo de su padre y desvincularlo
padre = n->padre;
if(padre->derecho == n) {
padre->derecho = NULL;
free_nodo(n);
}
else {
padre->izquierdo = NULL;
free_nodo(n);
}
}
else {
if(n->derecho != NULL && n->izquierdo != NULL) {
// Tiene 2 Hijos
padre = n->padre;
// Detalle aqui.....

}
else {
if(n->derecho != NULL) { //Solo tiene al hijo derecho
derecho = n->derecho;
padre = n->padre;
if(padre->derecho == n) { //hay que determinar si es el hijo derecho o izquierdo de su padre y vincular dicho nodo, con el nodo derecho del n actual y liberar n despues de eso
padre->derecho = derecho;
free_nodo(n);
}
else {
padre->izquierdo = derecho;
free_nodo(n);
}
}
else { //Solo tiene al hijo izquierdo
izquierdo = n->izquierdo;
padre = n->padre;
if(padre->derecho == n) { //hay que determinar si es el hijo derecho o izquierdo de su padre y vincular dicho nodo, con el nodo izquierdo del n actual y liberar n despues de eso
padre->derecho = izquierdo;
free_nodo(n);
}
else {
padre->izquierdo = izquierdo;
free_nodo(n);
}
}
}
}
}
else {
printf("No existe un nodo con el valor \"%s\" en el arbol\n",valor);
}
}



Solucion en : http://foro.elhacker.net/programacion_cc/c_eliminando_nodo_de_arbol_binario-t453185.0.html;msg2072953#msg2072953

[class_OpenGL]

No soy un experto en árboles binarios (lo digo en serio), pero cuando eliminas un nodo de este, ¿no tienes que eliminar también a sus hijos, "nietos" y demás nodos conectados directamente o indirectamente al nodo a eliminar?

[AlbertoBSD]

No necesariamente depende del uso que le estes dando al arbol. En este caso simplemente lo estoy usando como un contenedor de datos.

Por ejemplo en este lo estoy usando para contener un lista de libros muy grande.

Ver http://foro.elhacker.net/foro_libre/lista_de_libros_para_usar_en_programa-t452891.0.html

Y por ejemplo para agregar un nodo "libro" solo le toma log n operaciones encontrar su lugar en el arbol.

Y para buscar un nodo igualmente le toma solo log n operaciones.

Entonces si por casualidad queremos quitar un nodo y este nodo tiene hijos hay que reorganizar el arbol.

Claro que como dices tambien tengo que tener alguna funcion que elimine un subarbol pero... para los fines de mi programa ahorita no necesito esa función.

Saludos.

[class_OpenGL]

Solo te tienes que plantear: ¿de qué forma está organizado mi árbol? Una vez sabido eso, puedes establecer una regla en pseudocódigo con la cual eliminas un árbol con dos hijos.

Por ejemplo, dependiendo de la estructura del árbol, solo eliminaría la rama de la derecha, o la de la izquierda.

Sinceramente, no sé que ejemplo poner con árboles binarios y libros XDD Pon la estructura que sigue el árbol y a ver si se nos ocurren ideas para establecer las reglas de eliminación de un nodo.

[MAFUS]

Pásate por aquí: http://www.c.conclase.net/edd/?cap=007#7_5
Trata de este tema, precisamente.

[AlbertoBSD]

 

Se trata de un nodo rama: en ese caso no podemos eliminarlo, puesto que perderíamos todos los elementos del árbol de que el nodo actual es padre. En su lugar buscamos el nodo más a la izquierda del subárbol derecho, o el más a la derecha del subárbol izquierdo e intercambiamos sus valores. A continuación eliminamos el nodo hoja.

El mas izquierdo del subarbol derecho o el mas derecho del subarbol izquierdo Tiene mucha logica no se por que no se me ocurrio antes.

Esta genial!!!


Solucion

Como comentan en la lectura  del vinculo que puso MAFUS,

Ellos abordan el problema de 2 maneras.

• Es un nodo hoja (No tiene hijos)
• Es un nodo rama (tiene almenos un hijo)

Buscan el nodo mas izquierdo del subarbol derecho o buscan el nodo mas derecho del subarbol izquierdo, intercambian los valores con el nodo a eliminar y eliminan el ultimo nodo que ahora contiene el valor que queriamos eliminar en un principio.

Decidi por abordando el problema como lo plantee en un principio

• Es un nodo hoja
• Es un nodo rama (Con un solo hijo)
• Es un nodo rama (Con los 2 hijos)

Ya que cuando el nodo a eliminar tiene solo un hijo es mas facil solo revincular a el padre del nodo a eliminar con ese unico hijo.

Ahora en el tercer caso cuando el nodo a eliminar tiene 2 hijos lo que decidi a hacer es intercambiar el valor del nodo a eliminar con el de alguno de lo hijos y ahora evaluar iterativamente si este nuevo nodo tiene hijos o no esperando que llegue al caso 1 o 2.

Código (c) [Seleccionar] Expandir

if(n->derecho != NULL && n->izquierdo != NULL) {
if((rand() % 2) == 1) {
printf("Elijiendo derecho\n");
derecho = n->derecho;
temp = n->valor;
n->valor = derecho->valor;
derecho->valor = temp;
temp = NULL;
n=derecho;
}
else {
printf("Elijiendo izquierdo\n");
izquierdo = n->izquierdo;
temp = n->valor;
n->valor = izquierdo->valor;
izquierdo->valor = temp;
temp = NULL;
n=izquierdo;
}
}


ventajas y desventajas de esta implementacion.

Dependiendo de la profundidad del arbol esta implementacion podria ser mas rapida.

En el peor de los casos todos los subarboles siguientes tienen 2 hijos cada uno hasta llegar al ultimo nivel del arbol... ahi si es mas rapido el metodo descrito en el link

Ya que es muy rapido llegar al subnodo mas derecho del hijo izquierdo o al subnodo mas izquierdo del hijo derecho e intercambiar valores con el nodo a eliminar y posteriormente eliminado el nodo deseado.

Saludos