C Piscine — C 13

Árboles binarios: la estructura donde la recursión deja de ser un truco y pasa a ser la forma natural de pensar. Ocho ejercicios sobre creación, los tres recorridos clásicos, el árbol binario de búsqueda y un recorrido por niveles que ya pide una cola.

La estructura del módulo — El nodo, entregado en ft_btree.h, tiene dos hijos en vez del único next de las listas:
typedef struct s_btree
{
	struct s_btree	*left;
	struct s_btree	*right;
	void			*item;
}	t_btree;
Ese doble enlace lo cambia todo: la estructura ya no es una línea, es una ramificación. Y por eso casi todas las funciones se escriben solas de forma recursiva: «haz algo con la raíz, luego repite lo mismo con el subárbol izquierdo y con el derecho». Cada rama es, a su vez, un árbol completo — esa autosemejanza es lo que hace que la recursión encaje como un guante.

GGlosario de teoría

C 13 es el módulo de los árboles binarios, y casi todo su vocabulario viene de la teoría de árboles y de la recursión. Aquí está cada término explicado desde cero y con un ejemplo sacado del propio módulo. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.

Los ejemplos usan siempre el mismo árbol: el que sale al insertar con btree_insert_data las cadenas d b f a c e g, en ese orden, comparando con strcmp.

        d
      /   \
     b     f
    / \   / \
   a   c e   g

El árbol

Árbol binario

Una estructura hecha de nodos en la que cada nodo tiene como mucho dos hijos, uno a la izquierda y otro a la derecha. Es como una lista enlazada de C 12 en la que cada nodo, en vez de un next, tiene dos: left y right. Si no hay hijo, el puntero vale NULL.

Los árboles de informática se dibujan al revés que los de verdad: la raíz arriba y las ramas hacia abajo.

Raíz, hijo, padre, hoja y subárbol

La raíz es el nodo de arriba del todo, el único que no es hijo de nadie: en el ejemplo, d. Si un nodo apunta a otro, el primero es el padre y el segundo el hijo: b es hijo de d y padre de a y c. Una hoja es un nodo sin hijos: a, c, e y g.

Un subárbol es un nodo con todo lo que cuelga de él. El subárbol izquierdo de d es b a c, y es un árbol completo por sí mismo. Esa idea, que cada rama es otro árbol, es la que hace que las funciones del módulo sean recursivas.

Nivel, rama y altura

El nivel de un nodo es a cuántos saltos está de la raíz: la raíz es el nivel 0, sus hijos el 1, sus nietos el 2. Así lo numera el enunciado de ex07. Una rama es un camino de la raíz a una hoja.

La altura es cuántos nodos tiene la rama más larga, que es lo que devuelve btree_level_count: el árbol del ejemplo tiene altura 3, una hoja sola 1 y el árbol vacío 0. Ojo: hay libros que cuentan saltos en vez de nodos y darían 2; aquí se cuentan nodos.

Árbol binario de búsqueda (BST)

Un árbol binario con una regla de orden: en cada nodo, todo lo que hay en su subárbol izquierdo es menor que él y todo lo del derecho es mayor (en C 13, mayor o igual). Las siglas vienen del inglés binary search tree.

La regla se mantiene sola si cada elemento se inserta con btree_insert_data: se baja desde la raíz yendo a la izquierda si es menor y a la derecha si no, y se cuelga donde haya un hueco. c es menor que d (izquierda) y no menor que b (derecha): por eso queda como hijo derecho de b.

Árbol equilibrado y árbol degenerado

Un árbol está equilibrado cuando sus ramas miden más o menos lo mismo: con n nodos, su altura ronda log₂ n. El del ejemplo lo está: 7 nodos y altura 3. Uno degenerado es el opuesto: cada nodo tiene un solo hijo, y el árbol es en realidad una lista.

Un BST degenera si se le insertan los datos ya ordenados: con a b c d, cada uno va a la derecha del anterior, y btree_level_count devuelve 4 (comprobado compilando el código de la página). La forma depende del orden de inserción, no solo de los datos.

Coste O(log n)

log₂ n es cuántas veces se puede partir n por la mitad hasta llegar a 1: log₂ 8 = 3, log₂ 1024 = 10. Un coste O(log n) crece muy despacio: el doble de datos, un paso más.

Es el coste de buscar en un BST equilibrado aprovechando el orden: en cada nodo se decide izquierda o derecha y se descarta la otra mitad. En un árbol degenerado la misma búsqueda es O(n), como en una lista. btree_search_item no aprovecha el orden, porque el enunciado pide recorrer en inorden: mira todos los nodos hasta encontrarlo, O(n).

Recorridos

Recorrido en profundidad (DFS)

Visitar un árbol bajando por una rama hasta el fondo antes de pasar a la siguiente. En inglés, depth-first search. Es lo que sale solo con recursión: la función baja por la izquierda, y solo cuando esa llamada termina entera baja por la derecha.

Preorden, inorden y postorden son los tres recorridos en profundidad. Se diferencian únicamente en cuándo se llama a applyf con el nodo actual: antes de bajar, entre las dos bajadas o después.

Preorden (prefix)

Raíz, subárbol izquierdo, subárbol derecho. Cada nodo sale antes que sus descendientes. Es btree_apply_prefix; con el árbol del ejemplo imprime d b a c f e g.

Como la raíz va primero, insertar los nodos en ese orden en un BST vacío reconstruye exactamente el mismo árbol. Por eso es el orden para copiar o guardar un árbol.

Inorden (infix)

Subárbol izquierdo, raíz, subárbol derecho. Es btree_apply_infix; con el ejemplo imprime a b c d e f g.

Sobre un BST sale siempre ordenado, y no por casualidad: en cada nodo, todo lo de su izquierda es menor y todo lo de su derecha es mayor o igual, y el inorden escribe justo eso, la izquierda, el nodo y la derecha.

Postorden (suffix)

Subárbol izquierdo, subárbol derecho, raíz. Cada nodo sale después de todos sus descendientes. Es btree_apply_suffix; con el ejemplo imprime a c b e g f d, y la raíz d sale la última.

Es el orden para liberar un árbol: si se libera un padre antes que sus hijos, ya no se puede leer left ni right para llegar a ellos.

Recorrido en anchura (BFS, por niveles)

Visitar el árbol nivel a nivel, de izquierda a derecha: primero la raíz, luego todos sus hijos, luego todos los nietos. En inglés, breadth-first search. Con el ejemplo: d, después b f, después a c e g.

No se puede hacer con una recursión simple sobre los hijos, porque esa recursión siempre termina un subárbol entero antes de empezar el otro: haría falta visitar f antes que a, y la recursión lleva primero a a. Hace falta una cola.

Cola (FIFO)

Una estructura en la que el primero en entrar es el primero en salir (First In, First Out), como la cola de un supermercado: se añade por el final y se saca por el principio. Es lo contrario de una pila (LIFO).

En btree_apply_by_level la cola es una lista enlazada con un puntero a cada extremo (head y tail). Se saca el de delante, se procesa y se meten sus hijos detrás. Como los hijos entran detrás de todo lo que ya esperaba, un nivel entero sale antes que el siguiente. Cada nodo de la cola se reserva con malloc y se libera al sacarlo.

Recursión

Recursión

Una función es recursiva cuando se llama a sí misma con un problema más pequeño. En un árbol el problema pequeño sale solo: para recorrer el árbol, recorre el subárbol izquierdo y el derecho, que son árboles más pequeños.

Toda función recursiva necesita dos partes: un caso base que termine sin llamarse, y un paso que se acerque a él. En C 13 bajar por left o right siempre acerca al caso base, porque acaba llegando a un NULL.

Caso base

El caso que se responde sin volver a llamarse. En casi todas las funciones del módulo es el árbol vacío: if (!root) return ; en los recorridos, return (NULL) en btree_search_item y return (0) en btree_level_count. En btree_insert_data es el hueco: *root == NULL, y ahí se crea el nodo.

Al poner el caso base en el NULL y no en la hoja, la función funciona también con el árbol vacío y no hace falta mirar si existen left y right antes de bajar.

Pila de llamadas y profundidad de la recursión

Cada llamada a una función que aún no ha terminado ocupa un hueco (un marco) en la pila de llamadas, con sus parámetros y variables locales. En una recursión sobre un árbol hay a la vez tantas llamadas pendientes como nodos tiene la rama por la que se va bajando: como mucho, la altura del árbol más la llamada con NULL.

Con árboles equilibrados son muy pocas (unas 20 para un millón de nodos). En uno degenerado son tantas como nodos, y con cientos de miles la pila se acaba y el programa muere por desbordamiento de pila (stack overflow).

Divide y vencerás

Resolver un problema partiéndolo en subproblemas del mismo tipo, resolviéndolos por separado y combinando sus resultados. En inglés, divide and conquer.

btree_level_count es el ejemplo del módulo: la altura de un árbol es 1 más la mayor de las alturas de sus dos subárboles. Para d: el subárbol de b mide 2, el de f también, y 1 + 2 = 3.

C

Doble puntero (t_btree **)

La dirección de una variable que es a su vez un puntero. Se usa cuando una función tiene que cambiar un puntero del llamante, igual que el t_list ** de C 12.

En btree_insert_data hace falta porque el nodo nuevo se cuelga en un puntero que vale NULL: la raíz del llamante la primera vez, y después el left o right de algún nodo. Con &(*root)->left se pasa la dirección de ese campo, y cuando la recursión llega al hueco escribe allí con *root = ….

void *item y el comparador

item es un void *: un puntero a cualquier cosa. El árbol no sabe si guarda cadenas o números, así que no puede compararlos ni mostrarlos él solo: las funciones reciben applyf para hacer algo con un item y cmpf para comparar dos, con el convenio de strcmp (negativo, 0 o positivo).

Ojo al orden de los argumentos: en btree_insert_data el nuevo va primero, cmpf(item, (*root)->item), y en btree_search_item el del árbol va primero y la referencia después, cmpf(root->item, data_ref).

ex00btree_create_node

Entregable: btree_create_node.c, ft_btree.hAutorizadas: malloc

Crear un nodo con su item y el resto a 0.

node = malloc(sizeof(t_btree));
if (!node)
	return (NULL);
node->left = NULL;
node->right = NULL;
node->item = item;
return (node);
Qué te obliga a aprender — El caso base de todo lo que viene. Un nodo recién creado es una hoja: sin hijos (left y right a NULL). Ese NULL es lo que luego detiene la recursión en cada recorrido; si dejaras los punteros sin inicializar, cada recorrido se lanzaría contra memoria basura.

ex01btree_apply_prefix

Entregable: btree_apply_prefix.c, ft_btree.hAutorizadas: ninguna

Recorrido preorden: raíz, luego izquierda, luego derecha.

if (!root)
	return ;
applyf(root->item);
btree_apply_prefix(root->left, applyf);
btree_apply_prefix(root->right, applyf);
Qué te obliga a aprender — La plantilla de la recursión sobre árboles: comprobar NULL (caso base) y bajar por los dos lados. En preorden se visita antes de bajar. Sirve para copiar o serializar un árbol: como la raíz sale primero, quien lee la secuencia puede reconstruir la estructura de arriba abajo.

ex02btree_apply_infix

Entregable: btree_apply_infix.c, ft_btree.hAutorizadas: ninguna

Recorrido inorden: izquierda, raíz, derecha.

if (!root)
	return ;
btree_apply_infix(root->left, applyf);
applyf(root->item);
btree_apply_infix(root->right, applyf);
Qué te obliga a aprender — El mismo esqueleto, movida una sola línea: la visita va entre las dos bajadas. Y ahí está la magia — sobre un árbol binario de búsqueda, el inorden saca los elementos ordenados de menor a mayor. Cambiar el momento de la visita cambia por completo el resultado, con el mismo recorrido.

ex03btree_apply_suffix

Entregable: btree_apply_suffix.c, ft_btree.hAutorizadas: ninguna

Recorrido postorden: izquierda, derecha, raíz.

if (!root)
	return ;
btree_apply_suffix(root->left, applyf);
btree_apply_suffix(root->right, applyf);
applyf(root->item);
Qué te obliga a aprender — La tercera posición de la visita: después de bajar por ambos lados. Es el orden que necesitas para liberar un árbol (borras los hijos antes que el padre, o dejarías nodos huérfanos) y para evaluar expresiones: un nodo se calcula cuando sus dos operandos ya están resueltos. Preorden, inorden y postorden son la misma recursión con la visita en un sitio distinto.

ex04btree_insert_data

Entregable: btree_insert_data.c, ft_btree.hAutorizadas: btree_create_node

Insertar respetando el orden: los menores a la izquierda, los iguales o mayores a la derecha, usando un comparador tipo strcmp.

if (!*root)
{
	*root = btree_create_node(item);
	return ;
}
if (cmpf(item, (*root)->item) < 0)
	btree_insert_data(&(*root)->left, item, cmpf);
else
	btree_insert_data(&(*root)->right, item, cmpf);
Qué te obliga a aprender — Aquí se construye el árbol binario de búsqueda (BST): la propiedad de «menores a la izquierda, mayores a la derecha» es la que convierte un árbol en un buscador. Se combina la recursión con el t_btree ** de C 12: al llegar a un hueco (*root == NULL) hay que escribir ahí el nodo nuevo, y para eso necesitas la dirección del puntero, no su valor.

ex05btree_search_item

Entregable: btree_search_item.c, ft_btree.hAutorizadas: ninguna

Buscar el primer item que casa con data_ref, recorriendo en inorden. Devuelve NULL si no está.

if (!root)
	return (NULL);
found = btree_search_item(root->left, data_ref, cmpf);
if (found)
	return (found);
if (cmpf(root->item, data_ref) == 0)
	return (root->item);
return (btree_search_item(root->right, data_ref, cmpf));
Qué te obliga a aprender — Recursión que devuelve valor y corta en cuanto encuentra: si el subárbol izquierdo ya trae un resultado, no se mira el resto. El enunciado pide orden inorden, así que se busca izquierda → raíz → derecha. Ojo al matiz: aquí se recorre sin aprovechar la propiedad del BST; si se aprovechara (ir solo a un lado según el comparador), la búsqueda sería O(log n) en un árbol equilibrado — la razón de ser de los árboles de búsqueda.

ex06btree_level_count

Entregable: btree_level_count.c, ft_btree.hAutorizadas: ninguna

Devolver la longitud de la rama más larga (la altura del árbol).

if (!root)
	return (0);
left = btree_level_count(root->left);
right = btree_level_count(root->right);
if (left > right)
	return (left + 1);
return (right + 1);
Qué te obliga a aprender — La recursión que calcula en vez de solo recorrer: la altura de un nodo es 1 más la altura de su hijo más alto. El vacío mide 0, una hoja mide 1. Es el patrón «resuelve los dos subproblemas y combínalos» (divide y vencerás), y esa altura es la que determina si un BST está equilibrado o degenerado en una lista.

ex07btree_apply_by_level

Entregable: btree_apply_by_level.c, ft_btree.hAutorizadas: malloc, free

Recorrer el árbol nivel por nivel (anchura). A cada nodo se le pasa su nivel y si es el primero de su nivel.

head = new_qnode(root, 0);
while (head)
{
	applyf(head->node->item, head->level, head->level != prev);
	prev = head->level;
	tail = enqueue_kids(tail, head->node, head->level);  /* encola hijos */
	tmp = head;
	head = head->next;
	free(tmp);
}
Qué te obliga a aprender — El recorrido en anchura (BFS) no sale gratis con recursión: necesita una cola (FIFO). Se saca un nodo, se procesa y se encolan sus hijos al final; la cola garantiza que un nivel entero se visita antes que el siguiente. Por eso el ejercicio autoriza malloc y free: hay que construir esa cola con nodos auxiliares y liberarlos al vaciarla. Es la estructura opuesta a la pila que usa la recursión (que hace, implícitamente, un recorrido en profundidad). El flag «primero del nivel» se deduce de comparar el nivel actual con el del nodo anterior.

?Preguntas probables de la evaluación

Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado. Están agrupadas en: recorridos, el árbol de búsqueda, memoria y entrega. Antes de mirar la respuesta, intenta contestar tú, y ten papel a mano: te pedirán que dibujes un árbol y digas en qué orden sale.

Recorridos

Inserto d b f a c e g. ¿Qué imprime cada recorrido?

Preorden d b a c f e g, inorden a b c d e f g, postorden a c b e g f d y por niveles d b f a c e g. Comprobado compilando el código de la página (para el de niveles, con una cola hecha a mano). → recorridos en profundidad, en anchura

¿Qué cambia entre apply_prefix, apply_infix y apply_suffix?

Solo la posición de la línea applyf(root->item): antes de las dos llamadas recursivas, entre ellas o después. El resto del código es idéntico. → ex01, ex02, ex03

¿Por qué apply_by_level necesita malloc y los demás no?

Porque un recorrido por niveles necesita una cola donde esperen los nodos del siguiente nivel, y esa cola hay que construirla. Los otros recorridos usan la pila de llamadas, que ya está ahí. Cada nodo de la cola se libera al sacarlo, así que al terminar no queda nada reservado. → cola, ex07

¿Cómo sabes si un nodo es el primero de su nivel?

Comparando su nivel con el del nodo anterior que salió de la cola: como la cola saca los niveles en orden, si el nivel cambia, este es el primero. Para que la raíz cuente como primera, la variable prev tiene que empezar en un valor que no sea un nivel válido, como −1; el fragmento de la página no muestra esa inicialización, y es lo primero que hay que poder enseñar. → ex07

El árbol de búsqueda

¿Por qué el inorden de un BST sale ordenado?

Porque en cada nodo todo lo de la izquierda es menor y todo lo de la derecha es mayor o igual, y el inorden escribe izquierda, nodo, derecha. Aplicado en cada nivel, sale todo en orden. → inorden, BST

¿Dónde va un elemento igual a uno que ya está?

A la derecha: el enunciado dice que los de valor igual o superior van a la derecha, y el código solo va a la izquierda si cmpf da negativo. → ex04

¿Cuánto devuelve btree_level_count con un árbol vacío, una hoja y a b c d insertados en orden?

0, 1 y 4. El último es un árbol degenerado: cada nodo cuelga a la derecha del anterior y la rama más larga tiene los cuatro (comprobado). → árbol degenerado, ex06

Memoria, punteros y entrega

¿Por qué btree_insert_data recibe t_btree **root?

Porque cuando llega a un hueco tiene que escribir en él el nodo nuevo: en la raíz del llamante la primera vez (el enunciado dice que entonces apunta a NULL) y luego en el left o right de un nodo. Para escribir en un puntero ajeno hace falta su dirección. → doble puntero

¿Cómo liberarías el árbol entero?

En postorden: primero los dos subárboles y después el nodo. Si se libera el padre primero, ya no se pueden leer sus left y right. Ningún ejercicio lo pide, pero en tu main de pruebas hace falta para que valgrind no marque fugas. → postorden

¿Qué entregas en cada ejercicio y qué funciones puedes usar?

El .c y ft_btree.h con el struct tal cual. Desde ex01 la Moulinette pone su btree_create_node, así que tu header debe tener el prototipo y tu .c no necesita la función (si la copias dentro, puede chocar con la suya al enlazar). Solo hay malloc en ex00 y malloc y free en ex07; en ex04, solo btree_create_node. → ex00, ex04