Distribución Tarea 2

[ClaudiaAD]

Hola Axel. Escribo pues tenemos que hacer la segunda tarea juntos, la 9.

Estaba mirando y son 6 problemas de 0.5 puntos. No sé que te parezca pero nos podemos dividir esos a la mitad. No sé, yo pensé hacer uno los tres primeros y el otro los tres últimos, o dividirlos por pares e impares para que sea más justo quizás. No sé, espero tu opinión sobre eso.

En la pregunta 7 que hay que programar pues yo mañana pienso empezarla y te mando lo que tenga y de ahí sigues o algo así, te parece? Intentaré hacer al menos la mitad.

Espero tus comentarios.

[ClaudiaAD]

Por cierto, volví a escribir en ese fork de fork que hice la primera vez, pero copié todo aquí.

[axel9719]

Hola me parece mejor dividirlo a la mitad porque parece que los últimos tres dependen un poco entre si y el 3 se puede abordar con lo que veas en el 2, igual estaba programando algo pero si no me espero a que subas lo que tengas y a partir de eso continuo.

[ClaudiaAD]

Hola. Si quieres manda lo que tienes. Yo tuve unos imprevistos y no avancé como pensaba. Y yo completo lo que hayas hecho. Y dime si prefieres hacer los tres primeros o los tres ultimos. A mi me da igual

[axel9719]

Acabo de subir una carpeta "Axel-arboles", es lo que estaba haciendo son para arboles binarios de búsqueda AVL, aun no implementaba los colores de arboles rojos-negros, pero pensaba partir de esa estructura, Tengo una función re-cursiva para insertar elementos al árbol y las otras tres son para recorrer el árbol, a partir de cualquiera de estas salen fácil las de get(), contains(),size(), la de isEmpy() es trivial , mi problema era la de delete(), pues abría que reacomodar el arbol.

[axel9719]

Hago los tres últimos

[axel9719]

Apenas estoy leyendo lo de arboles rojo-negros porque no me quedaba claro, así que no estoy seguro de si la función de insertar que tengo se pueda ocupar para estos pero las otras si salen, con cualquiera de las otras tres porque es básicamente recorrer el árbol y ver lo que te piden.

[axel9719]

Ya vi que ocupar las funciones de búsqueda que tenia para hacer las que nos piden es más complicado de lo que pensé, así que estoy haciendo otras cosas.

[ClaudiaAD]

OK. Me mandas lo que logres tener y mañana yo lo completo. También ando mirando lo de rojo negro

[ClaudiaAD]

Ya estuve mirando tu código. Lo de Delete lo puedo hacer yo si eso te daba problemas. Estoy revisando el resto y viendo lo de rojo-negro en el Cormen para entender bien como funciona y qué hay que arreglar. Yo hago los tres primeros entonces.

[ClaudiaAD]

De hecho, como no te quedaba claro, empezaré trabajando con insertar y cuando la tenga lista lo subo. Después haré la de delete.

[axel9719]

Ya subi el de insertar

[ClaudiaAD]

Ah, ok. Lo descargo entonces, lo reviso y me pongo con el de delete.

[axel9719]

Estuve viendo y lo hacen con un apuntador extra al padre, así que ocupe eso y te ayuda bastante , hice la función put() con la función arreglar y dos de rotar para solucionar las violaciones que ocurran al insertar un nuevo nodo, ya quedo la get() así que supongo de esta sale la de contains(), así que faltaria esa, la de delete() y size()

[ClaudiaAD]

Ok. Acabo esas y las subo.

[axel9719]

subí un archivo pdf con el reporte y el .tex

[ClaudiaAD]

ok

[ClaudiaAD]

Hola. Te subiré un archivo arbol2.c que pondré en la misma carpeta. Estoy tratando de que lo de Delete me funcione pero no he logrado que quite los nodos raíz- Los demás lo hace, al menos los que he probado, pero en las raíces da problemas. Me guié por el pseudocódigo del cormen tercera edición. Te lo comento por si quieres revisarlo. Sigo trabajando, intentaré buscar alguna otra idea. O seguir debuggeando a ver qué es lo que pasa. Si tienes tiempo de mirarlo y te das cuenta del problema, me escribes porfa.

[axel9719]

Okey voy a ver y si logro algo, lo subo

[ClaudiaAD]

Revisé y tenía un par de cosas de identación mal, pero aún así sigue dando problemas. En el Cormen, usan y dicen que es importante lo del nodo NIL que está al final y que siempre tiene color negro y al que apuntan todos. Creo que sé como solucionar los problemas que tengo, pero tendría que cambiar algo toda la implementación desde insert y agregar una estructura de arbol aparte dela de nodo para que funcione lo de poner una raiz y un NIL para cada árbol. En fin, intentaré hacer todo el cambio y te lo paso. Creo que funcionará mejor.

[ClaudiaAD]

Axel, al final ya sirve todo Le tengo que agregar comentarios, pero está todo ya listo. Está la función contains, la función size y la delete con sus subfunciones. Para todo eso, como te comenté antes, tuve que crear una estructura de árbol que guardara la raíz, el NIL y el tamaño para tener el size más fácil. En este caso, el árbol se inicializa en NIL que es 0. Además, si pruebas la impresión, verás que imprime los 0 cuando van los NIL. Eso se puede quitar si te parece que no debería. Me comentas y lo quito.

En las funciones que habías hecho, también cambié los doble apuntadores por apuntadores sencillos al nuevo struct que es RBTree que es el árbol y es como estaba indicado en los prototipos de la tarea y así es como lo manejan en Cormen, que como te comenté, es lo que seguí para hacer el delete y que funcionara porque con los doble apuntadores me perdía para que saliera, aunque creo que lo que realmente faltaba, como te comenté, era lo del nodo NIL.

Mañana subo el tex y pdf con los tres puntos que me tocan y también el programa más comentado para ya entregar.

El nuevo código está en el archivo arbol2.c también , que lo sobreescribí.

Sigo pendiente de que lo revises y de cualquier comentario.

[axel9719]

Okey estoy terminando otro trabajo, pero lo reviso en un rato o mas tardar mañana en la mañana, pero si todo esta funcionando yo diria que esta bien, igual voy a probar varios casos para ver que este bien.

[ClaudiaAD]

Perfecto. Gracias. Mañana paso lo del reporte y listo.

[axel9719]

Ya lo revise y vi como lo tienen en el Cormen, lo que estaba leyendo no tenían eso pero creo que es mejor de esta forma, hice varios casos y fui comprobando que los resultados fueran los mismos, esta funcionando bien así que yo creo que ya lo podemos subir así como esta.

[ClaudiaAD]

Perfecto, ya subí el reporte en ClaudiaAxelTarea9. tex y pdf. Voy a poner ahora los comentarios bien en árbol2.c para que quede mejor explicado y ese sea el que subamos. Te aviso en cuanto lo suba otra vez.

[ClaudiaAD]

No he subido el codigo porque revisando me di cuenta de que no liberamos la memoria que se usa para crear los nodos. Estoy viendo como lo pongo para ya subirlo y que entreguemos.

[ClaudiaAD]

Axel, listo. Ya quedó el programa entero, comprobé que tod funciona y que aloca y libera la memoria correctamente. Resumiendo. En el archivo arbol2.c está el programa y en ClaudiaAxelTarea9.pdf está el reporte completo. Espero que me confirmes que apruebas todo para ya subirla al moodle.

[axel9719]

Okey ya lo volví a checar y probé los casos que podrían dar problemas y todo bien, entonces lo subimos

[ClaudiaAD]

OK