Título: [C] Eliminando Nodo de Arbol Binario (Solucionado) Publicado por: AlbertoBSD en 30 Mayo 2016, 05:42 am Tengo un detalle al momento de eliminar un nodo del arbol binario.
Dada la estructura: Código
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 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 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
Solucion en : http://foro.elhacker.net/programacion_cc/c_eliminando_nodo_de_arbol_binario-t453185.0.html;msg2072953#msg2072953 Título: Re: [C] Eliminando Nodo de Arbol Binario Publicado por: class_OpenGL 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?
Título: Re: [C] Eliminando Nodo de Arbol Binario Publicado por: AlbertoBSD 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. Título: Re: [C] Eliminando Nodo de Arbol Binario Publicado por: class_OpenGL 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. Título: Re: [C] Eliminando Nodo de Arbol Binario Publicado por: MAFUS 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. Título: Re: [C] Eliminando Nodo de Arbol Binario Publicado por: AlbertoBSD 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.
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
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
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 |