Á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.
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.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
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.
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.
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 comparadoritem 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).
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);
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);
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.Recorrido inorden: izquierda, raíz, derecha.
if (!root)
return ;
btree_apply_infix(root->left, applyf);
applyf(root->item);
btree_apply_infix(root->right, applyf);
Recorrido postorden: izquierda, derecha, raíz.
if (!root)
return ;
btree_apply_suffix(root->left, applyf);
btree_apply_suffix(root->right, applyf);
applyf(root->item);
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);
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.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));
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);
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);
}
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.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.
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
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
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
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
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
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
btree_search_item no usa el orden del BST. ¿No es un desperdicio?Sí sería más rápido bajar solo por un lado, pero el enunciado pide recorrer en inorden y devolver el
primero que case en ese orden. Además, cmpf puede no ser el mismo criterio con el
que se construyó el árbol, y entonces ir por un solo lado podría no encontrarlo.
→ ex05, O(log n)
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
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
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
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