Algoritmos y Progamación II - 1C2023

TDA Abb: de Michelle Chen - 105506 - mchen@fi.uba.ar

• Para compilar:

gcc src/*.c pruebas_alumno.c -std=c99 -Wall -Wconversion -Wtype-limits -pedantic -Werror -02 -g -o pruebas_alumno

• Para ejecutar:

./pruebas_chanutron
./pruebas_alumno

• Para ejecutar con valgrind:

valgrind --leak-check=full --track-origins=yes --show-reachable=yes --error-exitcode=2 --show-leak-kinds=all --trace-children=yes ./p

---

Funcionamiento

abb_t *abb_crear(abb_comparador comparador)

Para la función crear usé malloc apra pedir memoria del tamaño de un abb_t. Evalué la posibilidad de que falle el malloc y si malloc no falla inicializo el comparador del árbol con el comparador dado de parámetro. Inicializo el resto de las variables a 0 y devuelve el árbol creado.

nodo_abb_t *nodo_abb_crear(void *elemento)

Implementé una fución que crea un nuevo nodo pidiendo memoria con calloc e inicializando el puntero a un elemento con el elemento dado. La función devuelve el nuevo nodo creado con los datos inicializados. Agregué esta función para faciliar después la insersión de nodos al árbol.

abb_t *abb_insertar(abb_t *arbol, void *elemento)

La función insertar la planteé de forma recursiva. Uso la función nodo_abb_t *nodo_abb_crear(void *elemento) para crear un nodo nuevo que después va a ser insertado en el árbol. Evaluó si la creación del nodo fue exitoso, en caso que no, devuelvo NULL.

Y creo la función nodo_abb_t *abb_insertar_elemento_recursivo(nodo_abb_t *nodo_padre, nodo_abb_t *nuevo_nodo, int (*comparardor) (void *, void *)), lo que me devuelve la función va a ser igualada a arbol->nodo_raiz. Esta función de insertar recursiva funciona:

• Si el árbol es vacío entonces nodo_padre pasado de parámetro que en principio es arbol->nodo_raiz va a ser NULL. Y en ese caso la función recursiva me devuelve el nuevo_nodo que ahora es el nodo_raiz del árbol.

• Si el árbol no es vacío, arbol->nodo_raiz es distinto de NULL y debería usar el comparador para evaluar si el elemento del nuevo nodo es mayor, menor o igual que el elemento del nodo_padre en que estoy parado. Como tomamos por convención que el árbol puede recibir elementos repetidos y que en caso de tener elementos iguales lo mando para la izquierda, el caso de menor e igual sería el mismo.

Si el árbol no es vacío entonces nodo_padre distnto de de NULL y debería evaluar para qué lado ir con el comparador, dependiendo del resultado del comparador voy para la izquierda o derecha. Para el lado que vaya voy a tener nodo_padre->izquierda o nodo_padre->derecha que reciben lo que va a devolver la función nodo_abb_t *abb_insertar_elemento_recursivo(nodo_abb_t *nodo_padre, nodo_abb_t *nuevo_nodo, int (*comparardor) cada vez que la llame.

Voy apilando en el stack cada vez que llamo de nuevo la función recursiva y los nodo_padre->izquierda o nodo_padre->derecha quedan esperando lo que devuelva la función en cada llamada. Cuando el nodo_padre es NULL, devuelvo el nuevo_nodo y quedaría nodo_padre->izquierda = nuevo_nodo o nodo_padre->derecha = nuevo_nodo y así voy desapilando en el stack y enganchando los nodos hasta llegar el primer nodo_padre y devuelvo el nodo_padre con el sub-árbol actualizado con el nuevo_nodo y lo cuelgo de vuelta en la raíz.

Por último, actualizo el tamaño del árbol.

Fue bastante difícil en un principio entender cómo funcionaba esto de estar apilando desapinlando instancias de una función en el stack y que es lo que devuelvo con el return y en dónde se almacenan los datos cada vez que devuelvo, pero después siguiendo el código haciendo paso a paso en papel, se logró entender.

void *abb_buscar(abb_t *arbol, void *elemento)

La función buscar también fue implementada de manera recursiva. Es parecida a la función de insertar, pero con algunos cambios.

Creé una función nodo_abb_t *abb_buscar_recursivo(nodo_abb_t *nodo_padre, void *elemento, int (*comparador) (void *, void *)) para la búsqueda recursiva que recibe un nodo_padre que comienza en el nodo raiz, el elemento a buscar y el comparador. Lo primero que evalúo es si el nodo_padre es NULL, en ese caso no encontré el elemento buscado.

Si el elemetno a buscar es mayor que el elemento del nodo_padre entonces la función llama recursivamente en el sub-árbol derecho del nodo_padre, y si es menor el izquierdo. En caso de que el elemento del nodo_padre sea igual al elemento buscado, entonces encontré el nodo y lo devulvo.

Evalúo si lo que devolvió la función recurisva es NULL, en caso de serlo, no encontré el elemento. Sino devuelvo el elemento del nodo encontrado.

void *abb_quitar(abb_t *arbol, void *elemento)

La función de quitar fue implementada de manera iterativa, aunque el código se ve mucho más engorroso y la complejidad algorítmica no es buena, fue más para mí de manejar y debuggear los diferentes de casos de eliminar el nodo cuando lo encuentro.

Primero, uso la función de abb_buscar_recursivo para buscar el nodo que necesitamos. Si no lo encuentra, termina la función. Si lo encuentra, busco el nodo padre del nodo a quitar con la función nodo_abb_t *abb_buscar_padre(abb_t *arbol, nodo_abb_t *nodo_a_quitar).

Guardo en una variable en una variable aparte el elemento almacenado en el nodo al quitar para después devolverlo y almaceno también el sub-árbol derecho e izquierdo del nodo a quitar.

• Si el sub-árbol izquierdo y derecho son NULL significa que el nodo a quitar es un nodo hoja. Como no tengo hijos, libero el nodo a quitar. Si el nodo anterior al nodo a quitar es NULL significa que el nodo borrado es la raíz del árbol, como la función free devuelve la memoria, pero no hace nada con el contenido dentro de la memoria, apunto el nodo_raiza NULL.

• Si ninguno de los dos sub-árboles son vacíos entonces estoy en el caso de nodo con dos hojas. Uso la función creada nodo_abb_t *buscar_predecesor_inorden(nodo_abb_t *nodo_a_quitar_izquierda) para buscar el predecesor inorden. Actualizo el elemento del nodo a quitar con el elemento del predecesor inorden encontrado.

• Si el predecesor inorden coincide con el nodo izquierdo del nodo a quitar significa que el predecesor no tiene nodo derecho, entonces el nodo izquierdo del nodo a quitar debería apuntar al nodo izquierdo del predecesor. En caso contrario busco el nodo anterior del predecesor inorden con la función nodo_abb_t *abb_buscar_padre(abb_t *arbol, nodo_abb_t *nodo_a_quitar), como el predecesor no puede tener nodo derecho, sino no sería el predecesor, entonces cuelgo lo que tiene el nodo izquierdo del predecesor al nodo derecho del nodo anterior al predecesor. Por último, libero el nodo predecesor con free.

• El último caso sería cuando el nodo a quitar tiene solamente nodo izquierdo o nodo derecho. Para ese caso, si el nodo anterior al nodo a quitar es NULL significa que el nodo a quitar es el nodo_raiz por lo que re apunto el nodo_raiz al nodo izquierdo o derecho distinto de NULL. Si el nodo derecho del nodo anterior es el nodo a quitar, su derecha, entonces, sería el nodo izquierdo o derecho (dependiendo de cuál no es NULL) del nodo a quitar. Si el nodo izquierdo del nodo anterior es el nodo a quitar, entonces, su izquierda sería el nodo izquierdo o derecho (dependiendo de cuál no es NULL) del nodo a quitar. Libero el nodo a quitar cuando termino de re apuntar los nodos con free.

Por último, resto uno al tamaño del árbol y devuelvo el elemento del nodo a quitar.

void abb_destruir(abb_t *arbol) y void abb_destruir_todo(abb_t *arbol, void (*destructor)(void *))

Destruyo el árbol de manera recursiva recorriendo el árbol en postorden. Agregué una función para la destrucción de un árbol de manera recursiva void abb_destruir_recursivo_postorden(nodo_abb_t *nodo_padre, void (*destructor)(void *)) que recibe un nodo_padre y un destructor. La función de destruir recursivo recorre primero los nodos izquierdos y después los derechos, siempre destruye un nodo hoja, si hay destructor aplica el destructor al elemento del nodo, si no hay solamente libera el nodo con free.

Por último, cuando se termina de destruir todos los nodos del árbol, libero el árbol con free.

size_t abb_con_cada_elemento(abb_t *arbol, abb_recorrido recorrido, bool (*funcion)(void *, void *), void *aux)

Creo una variable para almacenar la cantidad de invocaciones que después va a ser devuelta por la función. Evaluó si el recorrido pedido es PREORDEN, INORDEN o POSTORDEN:

• bool abb_recorrido_preorden(nodo_abb_t *nodo_padre, bool (*funcion) (void *, void *), void *aux, size_t *invocaciones): Para el recorrido preorden primero debería visitar el nodo actual, después el izquierdo y por último el derecho. Si el nodo_padre es NULL, entonces he terminado de recorrer el árbol y devuelvo true. Si al aplicar la función pasada por parámetro el resultado da false devuelvo false, cuando evalúo el resultado de la función, si es false la función abb_recorrido_preorden devuelve false, sino la función devuelve true. Para cada aplicación de la función sumo uno a la cantidad de invocaciones.

En vez de pasar el puntero a invocaciones, paso la dirección del puntero a invocaciones, con puntero doble logro modificar la variable invocaciones_funcion en abb_con_cada_elemento.

• bool abb_recorrido_inorden(nodo_abb_t *nodo_padre, bool (*funcion) (void *, void *), void *aux, size_t *invocaciones): Evalúo si el nodo_padre es NULL, si lo es he terminado de recorrer y devuelvo true. Después para el recorrido inorden, primero debería visitar el subárbol izquierdo, después el padre y por último el derecho. La funciónde abb_recorrido_inorden es parecida a la del abb_recorrido_preorden, pero en vez de visitar el nodo antes visitar el sub-árbol izquierdo, visito el nodo despues de visitar el sub_árbol izquierdo.

• bool abb_recorrido_postorden(nodo_abb_t *nodo_padre, bool (*funcion) (void *, void *), void *aux, size_t *invocaciones): Recorro primero los nodos del sub-árbol izquierdo, después los del sub_árbol derecho y por último el nodo actual. Si en cualquiera de los dos recorridos el resultado de la función es false entonces devuelvo false, la función abb_recorrido_postorden devuelve false. Necesito evauluar dos veces el resultado de la función una para el recorrido izquierdo y otra para el derecho.

Costó para el recorrido postorden ver en qué momentos debería evaluar si el resultado de la función es false.

size_t abb_recorrer(abb_t *arbol, abb_recorrido recorrido, void **array, size_t tamanio_array)

Como abb_recorrer tiene que llenar un vector a medida que va recorriendo el árbol. Creo una estructura struct vector para el vector que después será pasado como parámetro auxiliar a abb_con_cada_elemento. Creo una variable array_aux del tipo de dato vector_t que tiene almacena un vector, el tamaño del vector y la posición para el último elemento del vector. Inicializo array_aux con el array pasado a la función, y el tamaño del vector con tamanio_array.

Creo la función bool abb_rellenar_vector(void *elemento, void *aux) para pasar como función a abb_con_cada_elemento que recibe un void *elemento y un void *aux que este caso sería el vector a llenar. En abb_rellenar_vector evalúo si la posición en la que quiero almacenar el elemento es mayor que el tamaño del vector dado, si lo es, devuelvo true, y si no, agrego el elemento en esa posición del vector, sumo uno a posición y devuelvo true.

---

Respuestas a las preguntas teóricas

ÁRBOL N-ARIOS

Un árbol es TDA (Tipo Abstracto de Datos) basada en una colección de nodos enlazados. Los nodos son los vértices o elementos del árbol. Nacen de la necesidad de representar una jeararquía en la estructura de los datos, así como también de querer optimizar la búsqueda linea de una lista.

De esta colección de nodos existe un nodo raíz (elemento en el primer nivel del árbol) que se distingue del resto, y de esta raíz puede tener conectada 0 o muchos sub-árboles no vacíos.

El/los inmediato/s nodo/s sucesor/es conectado a un nodo es/son llamado/s nodo hijo. Y el inmediato predecesor conectado a un nodo es el nodo padre. Un árbol general o árbol n-arios puede haber hasta n nodo hijo para cada nodo padre. Un nodo hoja es un nodo sin hijos, es decir, sin ningún nodo sucesor.

Las operaciones básicas de un árbol n-arios:

**crear**

La operación crear tiene complejidad O(1). La operación "crear" crea y devuelve un árbol vacío.

**destruir**

La opearción destruir tiene complejidad O(N) para el caso de árboles desbalanceados ya que para destruir cada uno de los nodos sí o sí hay recorrer todo el árbol e ir destruyendo uno por uno.

**vacio**

La opearción vacío tiene complejidad O(1) ya que para saber si el árbol es vacío o no solamente debería acceder al nodo raíz. En caso de que exista, el árbol ya no es vacío.

**insertar**

Como un árbol general (n-arios) no es un arbol AVL, es decir, puede estar totalmente desbalanceado, en el peor de los casos, todos los elementos insertados quedan enlazados uno después del otro formando así una lista enlazada. En ese caso insertar un elemento en el árbol, al igual que en una lista simplemente enlazada, tiene complejidad de O(N).

En un caso promedio, insertar tiene complejidad O(LOG N) para un arbol general.

M * M * M * ... * M = N M ^ K = N Luego, LOG en base M de N = K Realizo cambio de base: LOG en base de M de N = (LOG en base x de N) / (LOG en base x de M) [x puede ser una base cualquiera] Como 1 / (LOG en base x de M) es una constante: LOG en base de M de N = C * LOG en base x de N

**eliminar**

Sucede lo mismo eliminar un nodo para el peor de los casos en el que todos los nodos están enlazados uno después de otro como si fuera una lista simplemente enlazada, la complejidad para la operación eliminar sería O(N).

En un caso promedio, eliminar un nodo de un árbol general sería O(LOG N) por las razones especificadas en la operación insertar.

**buscar**

También sucede en la operación de buscar. En caso de tener un árbol totalemtne desbalanceado, teniendo a todos los elementos uno detrás de otro formando una lista enlazada, buscar un elemento sería O(N).

En un caso promedio, buscar un nodo tiene complejidad O(LOG N).

**recorrer**

La operación recorrer en el peor de los casos sería O(N) ya que tendría que pasar por cada uno de los elementos del árbol.

ÁRBOL BINARIO

Los árboles binarios son los árboles que pueden tener como máximo 0 a 2 sub-árboles por nodo, es decir, cada nodo del árbol puede tener un hijo izquierdo y un hijo derecho. Los árboles binarios están íntimamente con las operaciones de búsqueda con el objetivo de aproximarse a la búsqueda binaria.

Las operaciones básicas de un árbol binario:

**crear**

La operación crear tiene complejidad O(1). La operación "crear" crea y devuelve un árbol vacío.

**destruir**

La opearción destruir tiene complejidad O(N) ya que para destruir cada uno de los nodos sí o sí hay recorrer todo el árbol e ir destruyendo uno por uno.

**vacio**

La opearción vacío tiene complejidad O(1) ya que para saber si el árbol es vacío o no solamente debería acceder al nodo raíz. En caso de que exista, el árbol ya no es vacío.

**insertar**

Para el peor de los casos en el que todos los elementos insertados quedan enlazados uno después del otro formando una lista enlazada. En ese caso insertar un elemento en el árbol, al igual que en una lista simplemente enlazada, tiene complejidad de O(N).

En un caso promedio, insertar tiene una complejidad de O(LOG N)

2 * 2 * 2 * ... * 2 = N 2 ^ K = N Luego, LOG en base 2 de N = K Realizo cambio de base: LOG en base de 2 de N = (LOG en base x de N) / (LOG en base x de 2) [x puede ser una base cualquiera] Como 1 / (LOG en base x de 2) es una constante: LOG en base de 2 de N = C * LOG en base x de N

**eliminar**

Sucede lo mismo eliminar un nodo para el peor de los casos en el que todos los nodos están enlazados uno después de otro como si fuera una lista simplemente enlazada, la complejidad para la operación eliminar sería O(N).

En un caso promedio, eliminar tiene una complejidad de O(LOG N) por dividir siempre el problema en dos partes especificada en la operación de insertar.

**buscar**

También sucede en la operación de buscar. En caso de tener un árbol totalemtne desbalanceado, teniendo a todos los elementos uno detrás de otro formando una lista enlazada, buscar un elemento sería O(N).

En un caso promedio, buscar un elemento sería de complejidad O(LOG N).

**recorrer**

La operación recorrer en el peor de los casos sería O(N) porque tendría pasar por todos los elementos.

ÁRBOL BINARIO DE BÚSQUEDA - ABB

Un ABB es un árbol binario que puede ser vacío o en cada nodo del mismo contener un valor clave que satisfaga las siguientes condiciones:

• La clave en el nodo izquierdo del hijo (si existe) es menor que la clave en el nodo padre.
• La clave en el nodo derecho del hijo (si existe) es mayor que la clave en el nodo padre.
• Los sub-árboles derecho e izquierdo son también árboles binarios de búsqueda.

Las operaciones básicas de un ABB son:

**crear**

La operación crear tiene complejidad O(1) ya que crea un árbol vacío y lo devuelve.

**destruir**

La operación destruir tiene complejidad O(N) ya que para destruir un árbol entero necesito recorrer todos los nodos e ir eliminando uno por uno.

**vacio**

La operación de vacio tiene complejidad O(1) ya que con chequear existe el nodo raiz ya puedo saber si el árbol es vacío o no.

**insertar**

La operación insertar en el peor de los casos sería de la complejidad O(N). El peor caso sería insertar siempre de un lado tal que se forme una lista enlazada.

En un caso promedio, donde el árbol es balanceado, la complejidad sería O(LOG N) por dividir el problema en dos partes. Los pasos para obtener O(LOG N) están especificadas en insertar del árbol binario.

**eliminar**

La operación eliminar tiene complejidad O(N) en el peor de los casos y O(LOG N) en un caso promedio.

**buscar**

La operación buscar tiene complejidad O(N) en el peor de los casos y O(LOG N) en un caso promedio.

**recorrer**

La operación recorrer tiene complejidad O(N) por tener que recorrer todos los elementos del árbol.

por qué es importante la distinción de cada uno de estos diferentes tipos de árboles.

El árbol en general es un tipo de dato abstructo (TDA) que mejora la complejidad algorítmica de una lista enlazada para una gran cantidad de datos, que en caso promedio, sería O(LOG N). Dentro del tipo de dato árbol existen diferentes variantes implementadas con diferentes propiedades y características que se adecuan a diferentes usos.

Uno de ellos es el árbol binario en que cada nodo, en vez de poder tener enlazados n otros nodos, solamente puede tener entre 0 y 2 nodos. Como para cada nodo tengo una máxima de 2 nodos, cuando realizo alguna operación necesito alguna forma de saber hacia qué lado seguir, por el sub-árbol izquierdo o derecho. Sin esa operación de búsqueda, el árbol binario en sí solo carece de mucha utilidad.

El árbol binario de búsqueda es un árbol binario implementada tal que el criterio de búsqueda coincide con la de la búsqueda binaria.