elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [C] Eliminando Nodo de Arbol Binario (Solucionado)		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [C] Eliminando Nodo de Arbol Binario (Solucionado)  (Leído 16,262 veces)
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
[C] Eliminando Nodo de Arbol Binario (Solucionado)
« en: 30 Mayo 2016, 05:42 am »
Tengo un detalle al momento de eliminar un nodo del arbol binario.

Dada la estructura:

Código
  1. struct nodo	{
  2. 	struct nodo *padre;
  3. 	struct nodo *izquierdo;
  4. 	struct nodo *derecho;
  5. 	char *valor;
  6. };

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:
       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
  1. void eliminar_nodo(struct nodo *arbol,char *valor)	{
  2. 	struct nodo *n;
  3. 	struct nodo *padre;
  4. 	struct nodo *derecho;
  5. 	struct nodo *izquierdo;
  6. 	if(debug_arbol)
  7. 		debug_arbol = 0;
  8. 	n = buscar_valor(arbol,valor);
  9. 	if(n)	{
  10.  
  11. 		if(n->derecho == NULL && n->izquierdo == NULL)	{
  12. 			//No tiene hijos, hay que determinar si es el hijo derecho o izquierdo de su padre y desvincularlo
  13. 			padre = n->padre;
  14. 			if(padre->derecho == n)	{
  15. 				padre->derecho = NULL;
  16. 				free_nodo(n);
  17. 			}
  18. 			else	{
  19. 				padre->izquierdo = NULL;
  20. 				free_nodo(n);			
  21. 			}
  22. 		}
  23. 		else	{
  24. 			if(n->derecho != NULL && n->izquierdo != NULL)	{
  25. 				// Tiene 2 Hijos
  26. 				padre = n->padre;
  27. 				// Detalle aqui.....
  28.  
  29. 			}
  30. 			else	{
  31. 				if(n->derecho != NULL)	{	//Solo tiene al hijo derecho
  32. 					derecho = n->derecho;
  33. 					padre = n->padre;
  34. 					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
  35. 						padre->derecho = derecho;
  36. 						free_nodo(n);
  37. 					}
  38. 					else	{
  39. 						padre->izquierdo = derecho;
  40. 						free_nodo(n);			
  41. 					}
  42. 				}
  43. 				else	{	//Solo tiene al hijo izquierdo
  44. 					izquierdo = n->izquierdo;
  45. 					padre = n->padre;
  46. 					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
  47. 						padre->derecho = izquierdo;
  48. 						free_nodo(n);
  49. 					}
  50. 					else	{
  51. 						padre->izquierdo = izquierdo;
  52. 						free_nodo(n);			
  53. 					}
  54. 				}
  55. 			}
  56. 		}
  57. 	}
  58. 	else	{
  59. 		printf("No existe un nodo con el valor \"%s\" en el arbol\n",valor);
  60. 	}	
  61. }


Solucion en : http://foro.elhacker.net/programacion_cc/c_eliminando_nodo_de_arbol_binario-t453185.0.html;msg2072953#msg2072953
« Última modificación: 31 Mayo 2016, 05:02 am por AlbertoBSD » En línea
class_OpenGL


Desconectado Desconectado

Mensajes: 437

Si usas Direct3D, no eres mi amigo :P


Ver Perfil
Re: [C] Eliminando Nodo de Arbol Binario
« Respuesta #1 en: 30 Mayo 2016, 14:12 pm »
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?


En línea
Programador aficionado. Me quiero centrar en programar videojuegos. La API que uso para crearlos es OpenGL
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: [C] Eliminando Nodo de Arbol Binario
« Respuesta #2 en: 30 Mayo 2016, 14:36 pm »
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.
En línea
class_OpenGL


Desconectado Desconectado

Mensajes: 437

Si usas Direct3D, no eres mi amigo :P


Ver Perfil
Re: [C] Eliminando Nodo de Arbol Binario
« Respuesta #3 en: 30 Mayo 2016, 15:56 pm »
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.
En línea
Programador aficionado. Me quiero centrar en programar videojuegos. La API que uso para crearlos es OpenGL
MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: [C] Eliminando Nodo de Arbol Binario
« Respuesta #4 en: 30 Mayo 2016, 20:11 pm »
Pásate por aquí: http://www.c.conclase.net/edd/?cap=007#7_5
Trata de este tema, precisamente.
En línea
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: [C] Eliminando Nodo de Arbol Binario
« Respuesta #5 en: 31 Mayo 2016, 05:01 am »
 ;-) ;-) ;-)

Citar
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
  1. 				if(n->derecho != NULL && n->izquierdo != NULL)	{
  2. 					if((rand() % 2) == 1)	{
  3. 						printf("Elijiendo derecho\n");
  4. 						derecho = n->derecho;
  5. 						temp = n->valor;
  6. 						n->valor = derecho->valor;
  7. 						derecho->valor = temp;
  8. 						temp = NULL;
  9. 						n=derecho;
  10. 					}
  11. 					else	{
  12. 						printf("Elijiendo izquierdo\n");
  13. 						izquierdo = n->izquierdo;
  14. 						temp = n->valor;
  15. 						n->valor = izquierdo->valor;
  16. 						izquierdo->valor = temp;
  17. 						temp = NULL;
  18. 						n=izquierdo;
  19. 					}
  20. 				}
  21.  

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
En línea
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[SOLUCIONADO] como saber cuando un nodo de un treeview es nodo hoja
.NET (C#, VB.NET, ASP) 		matiasGuacharaca 5 14,412 Último mensaje 19 Junio 2009, 01:32 am
por matiasGuacharaca
Eliminar nodo en un arbol binario
.NET (C#, VB.NET, ASP) 		DaNuK 4 29,324 Último mensaje 6 Diciembre 2010, 20:19 pm
por DaNuK
Borrar nodo de un arbol
Programación C/C++ 		karmi 2 7,521 Último mensaje 10 Diciembre 2010, 18:02 pm
por do-while
Ayuda, no puedo borrar nodos de un Arbol Binario de Busqueda (Solucionado) [C++]
Programación C/C++ 		DarkSorcerer 7 13,242 Último mensaje 8 Marzo 2014, 02:47 am
por DarkSorcerer
leer un documento HTML,cada etiqueta debe guardarse en un nodo de un árbol
Programación C/C++ 		mcMario 0 1,979 Último mensaje 12 Diciembre 2016, 02:40 am
por mcMario
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines