Estructuras de datos

Panorama general: formas para guardar información

Una estructura de datos tiene dos partes: una manera de guardar los elementos y un pequeño conjunto de operaciones para usarlos: insertar, eliminar, buscar y, a veces, acceder por posición. Toda elección tiene un precio. Un estante te deja tomar el 5.º libro al instante, pero poner un libro en el medio obliga a empujar todos los demás. Una cadena de clips te deja poner un clip en cualquier lugar, pero para llegar al 5.º debes contar desde el principio.

Palabras que vas a encontrar

• Nodo: una pieza de una estructura que guarda un valor y, normalmente, las direcciones de otros nodos.
• [[Puntero|un número que dice dónde está algo en la memoria, como la dirección de una casa]]: la manera en que un nodo apunta a otro nodo. Un puntero que no apunta a nada se llama nulo (null).
• Clave: la parte de un elemento que usamos para encontrarlo, como el nombre en una lista de contactos.
• Organización secuencial: los vecinos en la memoria son vecinos en la estructura. Organización enlazada: el orden lo dan los punteros.
• Costo: cuántos pasos toma una operación cuando el número de elementos n crece. O(1) significa 'siempre más o menos igual', O(log n) significa 'crece muy despacio' y O(n) significa 'crece junto con n'.

Tipos abstractos de datos y encapsulamiento

Cuando aprietas el botón del control remoto de la tele, no necesitas saber la electrónica de adentro. Solo necesitas saber qué hace cada botón. Un tipo abstracto de datos (TAD) es la misma idea para programas: dice qué puedes hacer con los datos (un conjunto de valores y las operaciones sobre ellos), pero no cómo se guardan. La parte escondida es la representación.

Interfaz e implementación

La interfaz es la lista de operaciones (sus nombres, sus parámetros y lo que significan). La implementación es el código y la organización de la memoria detrás de ellas. La gran ventaja es la independencia de la representación: mientras la interfaz siga igual, puedes cambiar la representación libremente. Si una fecha se guardaba en un array de tres enteros y la cambias por una struct con tres campos, los programas que solo llaman a las funciones del TAD no necesitan cambiar. Solo se rompe el código que entraba por dentro desde afuera.

Esto también permite hacer más rápida una estructura sin molestar a nadie. Si una lista buscaba la primera posición libre en cada add y ahora guarda un contador privado de cuántos elementos tiene, quienes la usan llaman a los mismos métodos y solo notan que se volvió más rápida.

Encapsulamiento en C

En C, un TAD se convierte en un módulo de dos archivos. El encabezado (.h) publica un tipo opaco (un nombre sin campos visibles) y los prototipos de las funciones. El archivo .c guarda la struct real. Quien lo usa solo tiene punteros y no puede leer los campos, porque el compilador lo rechaza. Así el encapsulamiento lo garantiza el compilador, no la buena voluntad.

/* stack.h */
typedef struct Stack Stack;   /* opaco: ningún campo visible */
Stack *stack_new(void);
int    stack_push(Stack *s, int x);
int    stack_pop(Stack *s, int *out);

/* stack.c */
struct Stack { int data[100]; int top; };  /* escondido */

Errores e invariantes

• Errores: ¿qué debe hacer pop en una pila vacía? Un TAD reutilizable solo detecta el problema y devuelve un indicador de éxito o fallo. El programa que lo usa decide la reacción: mostrar un mensaje, preguntar de nuevo o fallar una prueba. Así el mismo módulo sirve para un programa de terminal, una ventana o una prueba automática. Imprimir y terminar dentro del TAD lo volvería inútil en los otros casos.
• Invariantes: una regla que siempre debe ser verdadera, por ejemplo 'un Conjunto no tiene elementos repetidos'. Sigue siendo verdadera porque todo cambio pasa por las operaciones del TAD.
• Exposición de la representación: si una función entrega un puntero al array interno 'para evitar copiar', quien lo usa puede escribir ahí y romper el invariante. La cura es devolver una copia, una vista de solo lectura o un iterador (un ayudante que entrega los elementos de uno en uno).

Arrays y listas: secuencial, enlazada, doblemente enlazada, circular

Una lista es una secuencia de elementos en la que el orden importa. Hay dos maneras principales de construirla. En una lista secuencial (un array) los elementos están uno al lado del otro en la memoria, como los asientos de una fila del cine. En una lista enlazada cada elemento vive en un nodo junto con la dirección del siguiente nodo, como en una búsqueda del tesoro donde cada pista dice dónde está la siguiente.

array:    [ 7 ][ 3 ][ 9 ][ 4 ]      índice 0 1 2 3

enlazada: inicio -> [7|*]-> [3|*]-> [9|*]-> [4|nulo]

Acceso e inserción

En un array, la dirección del elemento i es el inicio más i veces el tamaño de un elemento, así que leer la posición i cuesta O(1). En una lista enlazada cada nodo solo conoce al siguiente, así que para llegar a la posición i hay que dar i pasos: O(n). Por otro lado, insertar al inicio de un array obliga a todos los elementos a correrse un lugar para hacer espacio (O(n)), mientras que insertar justo después de un nodo que ya tienes en una lista enlazada solo cambia punteros (O(1)).

Tipos de listas enlazadas

• Simplemente enlazada: cada nodo tiene el dato y next. El next del último nodo es nulo, y un bucle avanza mientras el puntero actual no sea nulo.
• Doblemente enlazada: cada nodo también tiene prev. Cuesta un puntero más por nodo, pero desde cualquier nodo los dos vecinos son alcanzables en O(1), así que se puede eliminar un nodo conocido y recorrer hacia atrás.
• Circular: el último nodo apunta al primero, así que no hay nulo. Para recorrerla, recuerda el nodo inicial y detente cuando lo encuentres otra vez. Es buena para cosas atendidas por turnos, como los jugadores de un juego.
• Centinela: un nodo extra sin dato del usuario que elimina casos especiales. En una búsqueda, copias la clave buscada en el centinela al final, así el bucle siempre termina y necesita una sola comparación por paso en vez de dos. Sigue siendo lineal.
• Nodo cabecera (header): un primer nodo falso. Eliminar un nodo es hacer que su predecesor apunte a su sucesor. El primer nodo real no tiene predecesor, así que sin cabecera es un caso especial. Con cabecera, todo nodo de datos tiene predecesor.

El orden de las líneas de punteros

Para insertar node después de p, la dirección del antiguo siguiente nodo existe solo en p->next. Si la sobrescribes primero, pierdes el resto de la lista. Entonces hay que enlazar primero el nodo nuevo con el resto, y solo después hacer que p apunte al nodo nuevo.

node->next = p->next;  /* 1: el nodo nuevo guarda el resto de la lista */
p->next    = node;     /* 2: solo ahora p apunta al nodo nuevo */

Organización frente a asignación

Son dos preguntas distintas. La organización es cómo se representa el orden: por posiciones vecinas (secuencial) o por enlaces (enlazada). La asignación es cuándo se reserva la memoria: toda de una vez (estática) o bajo demanda (dinámica). Una lista guardada en un array de tamaño fijo en la que cada celda guarda el índice de su sucesor es, por lo tanto, enlazada (organización) y estática (asignación).

Un pool de nodos simula malloc y free dentro de un array: los nodos libres forman una lista enlazada de índices (la lista de libres). getnode toma el nodo del frente de la lista de libres y freenode(i) pone el nodo i al frente. Ambos cuestan O(1) y el pool se comporta como una pila: el nodo liberado último es el primero en reutilizarse.

Arrays dinámicos y costo amortizado

Un array dinámico crece cuando se llena: reserva un bloque del doble de tamaño y copia todo. Un agregado puede costar O(n), pero duplicar lo vuelve raro, así que el costo amortizado de agregar es O(1).

Las copias son 1 + 2 + 4 = 7. Cada reasignación copia el doble que la anterior, pero ocurre la mitad de las veces, así que el total es una suma de potencias de 2, siempre menor que el doble del número de elementos. Por eso el costo promedio por agregado se mantiene constante.

Listas ordenadas y dos trampas clásicas

• Una lista enlazada mantenida ordenada por clave hace que las búsquedas que fallan terminen antes (apenas pasas el lugar donde estaría la clave). Pero igual avanzas nodo por nodo, así que no se vuelve logarítmica. La búsqueda binaria necesita acceso directo por posición, que solo tiene el array.
• Eliminar mientras recorres una lista en array: después de remove(i), el siguiente elemento se corre al índice i. Si el bucle hace i++ a continuación, se salta ese elemento. Para la lista [1, 5, 5, 2] y la tarea 'eliminar todos los 5', el bucle eliminaría el primer 5 y se saltaría el segundo. Se arregla no incrementando después de una eliminación, o recorriendo del final al inicio.
• Un caché LRU ('eliminar el menos usado recientemente') necesita un mapa hash de clave a nodo y una lista ordenada por uso. Cada acceso saca un nodo del medio y lo pone al frente, y el desalojo quita el último nodo. Ambos cuestan O(1) solo si la lista es doblemente enlazada, porque el nodo debe conocer a sus dos vecinos para salir de su lugar.

Pilas

Una pila es una pila de platos. Pones un plato nuevo encima y también sacas uno de arriba. Nunca sacas un plato del medio. En computación: push pone un elemento arriba y pop saca el de arriba. El elemento que se quita es siempre el más reciente. Esta regla se llama LIFO: last in, first out (el último en entrar es el primero en salir).

   | 3 |  <- tope
   | 2 |
   | 1 |
   +---+

Implementando una pila

• En array (estática): guarda un entero top con el índice del último elemento apilado. Convención: top == -1 significa vacía y top == N - 1 significa llena, donde N es el tamaño del array. Comprueba 'llena' antes de apilar, para no escribir fuera del array (overflow), y comprueba 'vacía' antes de desapilar (underflow).
• En lista simplemente enlazada: el tope es el primer nodo. push crea un nodo que apunta al antiguo primero y mueve el puntero de inicio hacia él. pop solo avanza el puntero de inicio. No se recorre nada, así que ambos cuestan O(1). Solo está llena cuando se acaba la memoria.

Dónde aparecen las pilas

• Llamadas a funciones: cada llamada apila la dirección de retorno y las variables locales, y el retorno desapila. Esa es la pila de llamadas.
• Los botones de deshacer y el botón de retroceso de un navegador.
• Paréntesis emparejados: apila cada apertura, y cada cierre debe coincidir con el tope.
• Invertir una secuencia: convertir 13 a binario dividiendo entre 2 da los bits del último al primero (restos 1, 0, 1, 1 apilados en ese orden). Desapilar escribe el número 1101 en el orden correcto.
• Evaluar expresiones escritas en notación posfija.

Notación posfija (polaca inversa)

En la notación posfija el operador va después de sus operandos, así que no se necesitan paréntesis ni reglas de precedencia. Lee de izquierda a derecha: si ves un número, apílalo. Si ves un operador, desapila dos números, calcula y apila el resultado. El primer número desapilado es el operando de la derecha, lo que importa en la resta y la división.

lee 2  -> pila: 2
lee 3  -> pila: 2 3
lee +  -> desapila 3, desapila 2, apila 2+3 -> pila: 5
lee 4  -> pila: 5 4
lee *  -> desapila 4, desapila 5, apila 5*4 -> pila: 20

¿Qué órdenes de salida son posibles?

Supón que 1, 2, 3, 4 se apilan en ese orden, y que desapilar puede ocurrir en cualquier momento. Cuando un valor sale, todo lo que se apiló después de él y sigue adentro debe salir primero, en orden inverso. Entonces, después de imprimir un valor x, los valores menores que aún no se imprimieron deben salir en orden decreciente. Por ejemplo, 2, 1, 3, 4 es posible, pero 2, 4, 1, 3 no lo es: después de que sale el 4, el 3 está encima del 1 y tiene que salir primero.

Una pila que conoce su mínimo

Para obtener el mínimo en O(1), mantén una segunda pila de mínimos. Apila x en ella cuando esté vacía o cuando x sea menor o igual que su tope. Al desapilar, si el valor quitado es igual al tope de la segunda pila, desapila también esa. La comparación debe ser 'menor o igual': si el mínimo 3 se apila dos veces y solo se registra la primera copia, quitar un 3 borra el registro del otro y la respuesta queda mal.

Colas y deques

Una cola es la fila de la caja: las personas entran por atrás y salen por delante, así que el primero en llegar es el primero en ser atendido. Esto es FIFO: first in, first out (el primero en entrar es el primero en salir). Las operaciones son enqueue (insertar al final) y dequeue (quitar del frente). Nadie entra ni sale por el medio.

frente -> [ A ][ B ][ C ] <- final
dequeue devuelve A:  [ B ][ C ]
enqueue D:           [ B ][ C ][ D ]

Un deque (double-ended queue, cola de dos extremos, se lee 'dek') permite insertar y quitar por ambos extremos, pero tampoco por el medio. Generaliza la pila y la cola. En una lista doblemente enlazada o en un array circular, las cuatro operaciones cuestan O(1).

Cola en lista enlazada

Los elementos salen por el frente y entran por el final, así que guarda dos punteros, uno para cada extremo. De este modo ninguna operación recorre nodos. El caso especial clásico: cuando quitas el único elemento, los dos punteros deben volver a nulo, porque si no el puntero del final apuntaría a un nodo que ya no existe.

Cola en array: el truco circular

Con índices front y rear que solo avanzan, las celdas a la izquierda de front se desperdician con cada eliminación, y pronto la cola dice 'llena' con el array casi vacío. Una solución es correr todos los elementos hacia atrás, pero entonces quitar cuesta O(n). La mejor solución es la cola circular: trata el array como un anillo, en el que después del último índice viene el índice 0.

índice:   0     1     2     3     4     5
        [ C ] [ D ] [   ] [   ] [ A ] [ B ]
                                   ^front = 4
N = 6, front = 4, count = 4: A en 4, B en 5, C en 0, D en 1

La siguiente inserción va en el índice (front + count) mod N, donde mod es el resto de una división. El frente avanza del mismo modo, front = (front + 1) mod N, en cada eliminación. En el anillo de arriba, N = 6, front = 4 y hay 4 elementos guardados, así que la siguiente inserción es en (4 + 4) mod 6 = 2.

Colas y pilas juntas

• Invertir una cola: una cola mantiene el orden de llegada, una pila lo invierte. Si pasas los elementos de una cola por una pila y de vuelta, su orden queda invertido. Ejemplo: la cola 3, 6, 9 entra en la pila como 3, 6, 9 (9 arriba) y sale como 9, 6, 3.
• Una cola hecha con dos pilas, In y Out: enqueue apila en In. dequeue desapila de Out, y solo cuando Out está vacía antes mueve todos los elementos de In a Out, un pop y un push cada vez. Mover invierte el orden, y dos inversiones devuelven el orden de llegada. Cada elemento se apila y desapila como máximo dos veces, así que n operaciones cuestan O(n) en total, es decir, O(1) amortizado por operación, aunque un solo dequeue cueste O(n).

Recursión y listas generalizadas

¿Has visto dos espejos uno frente al otro, con una imagen dentro de la imagen dentro de la imagen? Recursión es cuando una función resuelve un problema llamándose a sí misma para una versión más pequeña del problema. Para funcionar, toda función recursiva necesita dos partes: un caso base, que se responde directo sin más llamadas, y un paso recursivo que acerca el problema al caso base. Si falta una de ellas, las llamadas se acumulan en la pila de llamadas hasta que se acaba la memoria (un desbordamiento de pila, stack overflow).

function sum(n: number): number {
	if (n === 0) return 0;      // caso base: nada más que sumar
	return n + sum(n - 1);      // paso: un problema más pequeño
}

Torres de Hanói

Hay 3 postes y n discos de distintos tamaños, y un disco grande nunca puede estar sobre uno más pequeño. Para mover n discos del poste A al poste C: mueve los n - 1 discos de arriba al poste B (de reserva), mueve el disco más grande a C y luego mueve los n - 1 discos de B encima de C. El número de movimientos sigue T(n) = 2 T(n - 1) + 1, cuya solución es 2ⁿ - 1.

Fibonacci: cuando la recursión repite trabajo

fib(n) = fib(n-1) + fib(n-2), con fib(0) = 0 y fib(1) = 1. La versión recursiva directa resuelve los mismos problemas pequeños una y otra vez: en la figura de abajo, fib(2) se calcula dos veces. Las llamadas en total son 9 para fib(4), y el número crece exponencialmente cuando n crece. Guardar los resultados ya calculados, o usar un bucle simple, hace que el costo sea O(n).

              fib(4)
             /      \
        fib(3)      fib(2)
        /    \      /    \
    fib(2) fib(1) fib(1) fib(0)
    /    \
fib(1) fib(0)

Listas generalizadas

Una lista normal guarda solo cosas simples. En una lista generalizada cada elemento es un átomo (un valor simple, como a) o otra lista generalizada. Los paréntesis muestran el anidamiento: (a, (b, c)) tiene un átomo a y una sublista (b, c). Como la definición se refiere a sí misma, los algoritmos que la recorren son naturalmente recursivos.

La profundidad también se define recursivamente: 1 más la mayor profundidad entre sus sublistas, y los átomos no suman nada. Una lista hecha solo de átomos tiene profundidad 1. Así, (a, (b, (c, d))) tiene profundidad 3: la lista más interna (c, d) tiene profundidad 1, (b, (c, d)) tiene 2 y la lista completa tiene 3. Es el mismo razonamiento que se usa para la altura de un árbol.

Árboles binarios y recorridos

Un árbol genealógico empieza con un abuelo, que tiene hijos, que tienen sus propios hijos. Un árbol en computación es así, dibujado al revés: una raíz arriba y ramas que bajan. Un árbol binario es un árbol en el que cada nodo tiene como máximo dos hijos, llamados izquierdo y derecho.

Palabras sobre árboles

• Raíz: el único nodo sin padre. Hoja: un nodo sin hijos. Los demás son nodos internos.
• Grado de un nodo: su número de hijos. Las hojas tienen grado 0. En un árbol con un solo nodo, la raíz también es una hoja.
• Nivel: la distancia a la raíz, en pasos. Altura del árbol: el número de aristas (enlaces) del camino más largo desde la raíz hasta una hoja. En este resumen, un árbol con un solo nodo tiene altura 0.
• Subárbol: cualquier nodo junto con todo lo que está debajo de él.

Cada nivel puede tener el doble de nodos que el de arriba: 1, 2, 4, 8... Así, un árbol de altura h tiene h + 1 niveles y como máximo 2^(h+1) - 1 nodos (altura 3 da 15). Leído al revés: n nodos caben en una altura cercana a log₂ n, y por eso un buen árbol es tan rápido.

Paseando por el árbol

Los tres recorridos en profundidad se diferencian solo en cuándo visitan la raíz de cada subárbol: antes de los dos subárboles (preorden), entre ellos (inorden) o después de ellos (postorden). En todos, el subárbol izquierdo se recorre antes que el derecho, y la regla se aplica recursivamente a cada subárbol.

        1
       / \
      2   3
     / \
    4   5

El postorden sirve cuando un nodo necesita primero las respuestas de sus hijos, como liberar la memoria de un árbol o calcular su altura. La raíz es siempre la última, y el primer nodo visitado es siempre una hoja. El recorrido por niveles usa una cola: visita un nodo y pon sus hijos al final de la cola. La cola guarda los nodos descubiertos pero aún no visitados. Si cambias la cola por una pila, el mismo algoritmo se vuelve un recorrido en profundidad.

Reconstruyendo un árbol

El preorden te dice cuál es la raíz: el primer elemento. El inorden te dice qué claves están a la izquierda y cuáles a la derecha de esa raíz. Repite la separación en cada parte, y aparece un único árbol (siempre que todas las claves sean distintas). Ejemplo: preorden D B A C E e inorden A B C D E. La raíz es D. En el inorden, A B C queda a la izquierda y E a la derecha. En la parte izquierda, el preorden B A C dice que la raíz es B, con A a la izquierda y C a la derecha. Entonces el postorden es A C B E D.

Árboles de expresión

La expresión a * (b + c) - d se puede guardar con operadores en los nodos internos y operandos en las hojas. La forma del árbol ya dice el orden de las operaciones, así que no hacen falta paréntesis. El postorden escribe cada operador después de sus operandos (a b c + * d -, la notación posfija, que una pila sabe evaluar). El preorden da la notación prefija.

Datos para contar

• Un árbol binario con n nodos tiene n - 1 enlaces (todo nodo salvo la raíz tiene un padre). Con 2 punteros de hijo por nodo hay 2n punteros, así que exactamente n + 1 de ellos son nulos, sea cual sea la forma.
• Todo árbol binario no vacío tiene una hoja más que nodos con dos hijos. Así, un árbol con 5 nodos de dos hijos tiene 6 hojas, sin importar cuántos nodos tengan un solo hijo.

Árboles en un array

Un árbol se puede guardar nivel por nivel en un array, sin punteros. Con la raíz en el índice 0, los hijos del nodo en el índice i están en 2i + 1 y 2i + 2, y su padre está en (i - 1) div 2 (división entera). Así, los hijos del índice 3 están en 7 y 8. No desperdicia espacio solo para árboles completos, porque cada nodo que falta deja un hueco.

Árboles binarios de búsqueda

Piensa en un juego de adivinanza: 'estoy pensando en un número del 1 al 100'. Tú dices 50 y yo respondo 'mayor'. Con una pregunta descartaste la mitad de los números. Un árbol binario de búsqueda (ABB) es un árbol binario construido para jugar ese juego. En cada nodo, todas las claves del subárbol izquierdo son menores y todas las claves del subárbol derecho son mayores (aquí las claves son todas distintas).

        8
       / \
      3   10
     / \
    1   6

Para buscar, compara con el nodo y sigue solo un lado, descartando el otro. Para insertar, busca la clave y colócala como una hoja nueva donde termina la búsqueda. El costo de buscar, insertar y eliminar es la longitud del camino, como máximo la altura del árbol.

Datos útiles

• El recorrido inorden visita las claves en orden ascendente, en O(n). Así es como un ABB lista datos ordenados.
• El mínimo se encuentra siguiendo los punteros de la izquierda desde la raíz hasta que no haya hijo izquierdo. El máximo es simétrico, por la derecha.
• La propiedad es sobre subárboles completos, no solo padre e hijo. Un validador que solo comprueba 'hijo izquierdo menor, hijo derecho mayor' acepta un árbol incorrecto, por ejemplo un nodo 5 con hijo izquierdo 3, donde el 3 tiene un hijo derecho 7: el 7 está en el subárbol izquierdo del 5, pero es mayor que 5. Un validador correcto lleva un intervalo de valores permitidos hacia abajo (ir a la izquierda baja el límite superior, ir a la derecha sube el límite inferior), o comprueba que el inorden sea ascendente.

La forma depende del orden de inserción

Un ABB simple no hace balanceo: una clave nueva solo se vuelve hoja donde termina su búsqueda. Así, las mismas claves dan árboles distintos según el orden en que lleguen. Si las claves llegan ya ordenadas (1, 2, 3, ..., 1000), cada clave nueva es mayor que todas las demás y va a la derecha de la última. El árbol se vuelve una lista enlazada de altura n - 1, y una búsqueda cuesta O(n).

1
 \
  2
   \
    3
     \
      4

Para obtener la menor altura con las claves del 1 al 7, inserta primero la mediana (4), luego las medianas de cada mitad (2 y 6), luego el resto. El árbol tiene altura 2. Cuando no puedes elegir el orden, solo el balanceo automático garantiza una buena altura. Eso es lo que hacen los árboles AVL y rojinegros.

Eliminación

• Una hoja: simplemente se corta.
• Un hijo: el hijo ocupa el lugar del nodo eliminado.
• Dos hijos: no se puede dejar un hueco. Reemplaza la clave por su vecina en el orden: el sucesor inorden (la menor clave del subárbol derecho) o el predecesor (la mayor clave del subárbol izquierdo). Esa vecina tiene como máximo un hijo, así que quitarla de su lugar antiguo cae en uno de los casos fáciles.

Ejemplo: un árbol con 40 en la raíz, 20 y 60 debajo, 10 y 30 bajo el 20, 50 y 70 bajo el 60, y 55 bajo el 50. Eliminando el 40 con la regla del sucesor: la menor clave del subárbol derecho es 50 (la más a la izquierda bajo el 60). El 50 ocupa el lugar de la raíz, y su lugar antiguo lo llena su único hijo, 55, que pasa a ser hijo izquierdo del 60.

Árboles AVL

Un árbol que se inclina demasiado es como una pila de libros a punto de caerse. El árbol AVL (por sus inventores Adelson-Velsky y Landis) es un árbol binario de búsqueda que se arregla solo. Su regla: en cada nodo, las alturas de los subárboles izquierdo y derecho difieren en como máximo 1. Esta regla local simple mantiene la altura de todo el árbol en O(log n).

Cada nodo guarda un número pequeño, el factor de balanceo: aquí, la altura del subárbol derecho menos la altura del subárbol izquierdo. En un AVL válido siempre es -1, 0 o +1. Después de una inserción o eliminación, los factores se actualizan en el camino de vuelta hacia la raíz. Si algún nodo llega a ±2, se repara con una rotación.

La rotación

Una rotación intercambia los papeles de un nodo y uno de sus hijos cambiando unos pocos punteros, en tiempo constante. Cambia las alturas, pero mantiene el orden de izquierda a derecha de todas las claves, así que el árbol sigue siendo de búsqueda.

    x                  y
   / \                / \
  A   y     ---->    x   C
     / \            / \
    B   C          A   B

Ambos leen:  A x B y C

Los cuatro casos

Encuentra el primer nodo desbalanceado subiendo desde la clave nueva. Mira el camino hasta la clave nueva, debajo de ese nodo:

En el caso interno una rotación simple solo reflejaría el problema. La rotación doble primero endereza el camino y luego gira el nodo desbalanceado. El nieto sube dos niveles y sus dos subárboles se reparten entre el antiguo padre y el antiguo abuelo.

  3          3           2
 /          /           / \
1    ->    2     ->    1   3
 \        /
  2      1

Para un caso externo, toma las claves 1, 2, 3 en ese orden: forman una cadena hacia la derecha, la raíz 1 llega a +2, y una rotación a la izquierda en el 1 hace del 2 la raíz, con 1 y 3 como hijos. El arreglo es local: los nodos por encima del punto reparado no cambian.

¿Qué altura puede tener?

El AVL más delgado de altura h tiene un subárbol de altura h - 1, otro de altura h - 2, ambos también delgados, más la raíz. La recurrencia es N(h) = N(h-1) + N(h-2) + 1, que crece como los números de Fibonacci. Por eso la altura de un AVL con n nodos es como máximo cerca de 1,44 log₂ n.

Inserción frente a eliminación

Después de una inserción, el árbol creció en algún lugar, y un paso de rotación (simple o doble) devuelve ese subárbol a su altura anterior, así que el arreglo termina ahí: como máximo un paso de rotación. Después de una eliminación, un subárbol se hizo más bajo, y la rotación que arregla un nodo puede acortar aún más el subárbol, lo que puede desbalancear a su padre. Entonces la eliminación puede necesitar revisar todos los ancestros hasta la raíz, con hasta O(log n) pasos de rotación. El costo total sigue siendo O(log n).

Árboles rojinegros

Un árbol rojinegro se balancea con colores en vez de alturas. Cada nodo se pinta de rojo o negro, y unas pocas reglas evitan que el árbol se incline demasiado. Es una regla más laxa que la del AVL: el árbol puede quedar un poco más alto, pero las actualizaciones necesitan menos reorganización.

Las reglas

1. Todo nodo es rojo o negro.
2. La raíz es negra (la convención de este resumen).
3. Las hojas vacías, llamadas NIL, son negras.
4. Un nodo rojo solo tiene hijos negros (nunca dos rojos seguidos).
5. Todos los caminos desde un nodo hasta las hojas NIL debajo de él tienen el mismo número de nodos negros.

¿Por qué esto da un árbol bajo? Todos los caminos desde la raíz hasta las hojas tienen el mismo número de negros, y entre dos negros cabe como máximo un rojo. Así, el camino más largo tiene como máximo el doble de nodos que el más corto. Esto limita la altura a 2 log₂(n + 1).

Ejemplo: si todo camino desde la raíz hasta un NIL tiene exactamente 2 nodos negros (sin contar el NIL), el camino más corto tiene 2 nodos (ambos negros) y el más largo alterna negro y rojo, terminando en un rojo: negro, rojo, negro, rojo, lo que da como máximo 4 nodos.

Inserción

La clave nueva entra como hoja y se pinta de rojo. Un nodo rojo nunca cambia la cuenta de negros de ningún camino, que es la regla más delicada. Como máximo una regla puede romperse: un nodo rojo con padre rojo. La reparación (el fix-up) mira al tío, el hermano del padre.

Con tío rojo ningún camino cambia su cuenta de negros, porque el negro del abuelo solo baja a sus dos hijos. Este es el único caso que se repite. Si llega a la raíz y la raíz queda roja, se pinta de negro otra vez, lo que sube en uno la cuenta de negros de todos los caminos a la vez, así que las reglas siguen cumpliéndose.

      8B
     /  \
   5B    9B
           \
           12R

Síguelo: 5 es la raíz (negra). El 8 va a la derecha, rojo. Insertar 9 pone un hijo rojo bajo un padre rojo con tío negro (NIL): una rotación a la izquierda en el 5 y un intercambio de colores hacen del 8 negro, con hijos rojos 5 y 9. Insertar 12 como hijo del 9 rojo encuentra un tío rojo (5): recolorea, así que 5 y 9 pasan a negro y 8 a rojo, y luego 8 es la raíz y se pinta de negro otra vez. El 12 sigue rojo.

¿AVL o rojinegro?

Ambos garantizan búsqueda, inserción y eliminación en O(log n). En las mediciones de este repositorio, con 100.000 claves aleatorias un árbol simple es solo unas dos veces más alto que los balanceados (41 contra 20), pero con claves ordenadas es una cadena. Balancear es un seguro contra un orden de llegada que tú no eliges.

Heaps y colas de prioridad

En la sala de urgencias de un hospital, quien llegó primero no siempre es atendido primero: el caso más urgente pasa adelante. Una cola de prioridad funciona así: insertas elementos con una prioridad, y siempre te entrega el de mayor prioridad (no el más antiguo). La manera habitual de construirla es un heap.

Un max-heap binario tiene dos propiedades independientes. Orden: cada nodo es mayor o igual que sus hijos, así que el mayor elemento está siempre en la raíz. Forma: el árbol es completo, es decir, todos los niveles están llenos salvo quizás el último, que se llena de izquierda a derecha. Los hermanos y primos no se comparan, así que mantener este orden parcial es mucho más barato que mantener todo ordenado.

Un árbol dentro de un array

Por la forma completa, no hay huecos, y el heap cabe en un array sin punteros. Con la raíz en el índice 0, los hijos del índice i están en 2i + 1 y 2i + 2, y el padre está en (i - 1) div 2.

árbol:        9            array: [9][5][6][1][2]
            /   \                  0  1  2  3  4
           5     6
          / \
         1   2

Insertar y quitar el máximo

• Insertar: pon el elemento en la primera posición libre del array (esto mantiene la forma completa) y luego sube (sift up): intercambia con el padre mientras sea mayor. Inserta 8 en el heap de arriba: va al índice 5, su padre es 6 (índice 2), 8 es mayor, se intercambian. El siguiente padre es 9, se detiene. Resultado: [9, 5, 8, 1, 2, 6]. Como máximo cerca de log₂ n intercambios.
• Quitar el máximo: toma la raíz. Para no dejar un hueco, mueve el último elemento del array a la raíz y luego baja (sift down): intercambia con el mayor de sus dos hijos mientras sea menor que ese hijo. Quita el máximo de [9, 5, 8, 1, 2, 6]: el 6 va a la raíz, el hijo mayor es 8, se intercambian. Resultado: [8, 5, 6, 1, 2]. Intercambiar con el hijo mayor es esencial: si no, el nuevo padre podría ser menor que su hermano.

Dos datos sorprendentes

• Construir un heap es lineal. Aplicar sift-down a cada nodo interno, desde el último hasta la raíz, cuesta a cada nodo su altura, no la altura del árbol. La mayoría de los nodos están cerca del fondo, donde la altura es pequeña, así que la suma es O(n), más barata que insertar n elementos uno por uno (O(n log n)). Es el primer paso de heapsort.
• La menor clave de un max-heap no está en un lugar fijo. Puede estar en cualquier hoja. En un heap con n nodos las hojas ocupan los índices desde n div 2 en adelante, cerca de la mitad del array. Buscar el mínimo es revisarlas todas: O(n).

Tablas hash: colisiones, factor de carga, rehashing

Imagina una escuela con un casillero para cada número de lista. Para encontrar el cuaderno del alumno 17 no revisas todos los casilleros: vas directo al casillero 17. Una tabla hash hace esto para cualquier tipo de clave, incluso nombres. Una función hash convierte la clave en un número, que se vuelve un índice en un array. Entonces la búsqueda va directo a un solo lugar, en promedio en O(1).

Una buena función hash es determinista (la misma clave siempre da el mismo código), rápida, y reparte bien las claves. Una función mala sigue siendo correcta, pero pone muchas claves en los mismos lugares y vuelve todo lento.

Colisiones

Hay muchísimas más claves posibles que posiciones, así que dos claves distintas a veces caen en el mismo índice. Esto es una colisión. Toda tabla necesita un plan para eso. Los dos clásicos:

7  -> índice 2: libre, guarda.
12 -> índice 2 ocupado, prueba 3: libre, guarda.
2  -> índices 2 y 3 ocupados, prueba 4: libre, guarda.

índice:  0    1    2    3    4
       [   ][   ][ 7 ][ 12][ 2 ]

Una búsqueda sigue el mismo camino de posiciones: pregunta el índice 2, luego el 3, luego el 4, y se detiene cuando encuentra la clave o una posición vacía.

Eliminar con direccionamiento abierto: lápidas

En el direccionamiento abierto, una búsqueda termina cuando encuentra una posición vacía. Si eliminas la clave A (que está antes de B en la misma secuencia de sondeo) simplemente vaciando su posición, una búsqueda posterior de B se detiene en la celda vacía y dice por error 'no encontrada'. La solución es una lápida (tombstone), una marca especial: la búsqueda pasa por encima de ella, y una inserción puede reutilizarla. Las lápidas igual alargan los sondeos, así que una reconstrucción (rehash) las descarta.

Factor de carga

El factor de carga α es el número de elementos guardados dividido entre el número de posiciones. Con 40 posiciones y 30 elementos, α = 0,75. Mide qué tan llena está la tabla, y por lo tanto qué tan probable es una colisión. Con encadenamiento, α es la longitud promedio de una lista: una búsqueda que falla examina cerca de α entradas y una que tiene éxito cerca de 1 + α/2. Con 300 elementos en 100 posiciones, α = 3, así que una búsqueda de una clave ausente mira cerca de 3 entradas.

Con sondeo lineal, las celdas ocupadas se juntan en largas secuencias (agrupamiento primario), y una clave que cae en una secuencia debe avanzar hasta el final de ella, haciéndola aún más larga. El número esperado de posiciones examinadas en una búsqueda que falla es cerca de (1 + 1/(1 - α)²) / 2, que se dispara cuando α se acerca a 1.

Con encadenamiento, las mismas cargas cuestan 0,25, 0,5, 0,75 y 0,9 entradas: una recta. Por eso las tablas de direccionamiento abierto se redimensionan con cargas menores (el mini-proyecto de este repositorio usa 0,5 para sondeo y 0,75 para encadenamiento).

Rehashing

Cuando α pasa de un límite, la tabla crece (normalmente duplicándose). Pero el índice es hash mod capacidad, así que depende del tamaño: toda entrada debe insertarse de nuevo. Esto es el rehashing. Cuesta O(n), pero duplicar lo vuelve raro, así que la inserción sigue siendo O(1) amortizado. También acorta las listas al separar claves que antes colisionaban: las claves 3, 11 y 27 caen todas en el índice 3 con 8 posiciones; con 16 posiciones, el 3 se queda en el 3 y el 11 y el 27 van los dos al 11.

equals y hashCode

Una tabla encuentra un objeto en dos pasos: el código hash elige la posición, y la igualdad decide dentro de ella. Por eso los objetos iguales deben tener el mismo código hash. En Java, si la clase Point sobrescribe equals pero no hashCode, set.contains(new Point(1, 2)) después de agregar otro new Point(1, 2) muy probablemente devuelve false: el código hash por defecto es distinto, la búsqueda mira en el lugar equivocado, y el objeto parece desaparecer aunque está guardado.

Grafos: representaciones, BFS y DFS

Un mapa de ciudades y carreteras, una red de amigos, los enlaces entre páginas web: todos son grafos. Un grafo tiene vértices (los puntos, como las ciudades) y aristas (las líneas entre ellos, como las carreteras). Si las aristas tienen sentido (calles de un solo sentido), el grafo es dirigido, y la arista también se llama arco. El grado de un vértice es su número de vecinos.

Dos maneras de guardar un grafo

Sea V el número de vértices y E el número de aristas.

Un grafo es disperso cuando E es mucho menor que V². Con 10.000 vértices y 30.000 aristas, una matriz necesitaría 100 millones de celdas, mientras que las listas necesitan solo decenas de miles de entradas. Usa listas.

En un grafo no dirigido, una arista v–w debe poder encontrarse desde cualquiera de sus extremos, así que se guarda dos veces, una en cada lista. El tamaño total de las listas, que es la suma de los grados, es siempre 2E. Un grafo con 5 aristas y sin lazos tiene 10 entradas.

Dos maneras de recorrer un grafo

    A
   / \
  B   C
   \ /
    D --- E

• La búsqueda en profundidad (DFS) sigue un camino hasta donde pueda, luego vuelve e intenta otro, como explorar un laberinto con un ovillo de lana. Usa recursión o una pila explícita, y los vértices en la pila son exactamente el camino actual. Desde A (vecinos en orden alfabético) el orden es A B D C E.
• La búsqueda en anchura (BFS) visita el origen, luego todos sus vecinos, luego los vecinos de ellos: capa por capa, como ondas en el agua. Usa una cola, y cada vértice se marca cuando entra en la cola, para no insertarlo dos veces. Desde A el orden es A B C D E.

En un grafo sin pesos, la BFS garantiza que la capa en la que se encuentra un vértice por primera vez es su distancia mínima en aristas desde el origen. Guardar el predecesor de cada vértice permite reconstruir el camino más corto hacia atrás.

El costo de un recorrido depende de la representación, porque el paso principal es listar los vecinos de cada vértice. Con listas, el total es Θ(V + E). Con matriz, listar cuesta V por cada vértice, así que Θ(V²) incluso para un grafo con pocas aristas.

Ciclos y orden topológico

Un ciclo es un camino que vuelve al punto de partida. En un grafo dirigido, encontrar un vértice ya visitado durante la DFS es un ciclo solo si ese vértice todavía está en el camino actual (un ancestro). Un vértice que ya terminó y al que se llega por otro camino no cierra ningún ciclo. Por eso la detección usa tres estados: no visitado, en curso y terminado. Un detector que dice 'ciclo' cada vez que ve un vértice visitado está equivocado: en A→B, A→C, B→D, C→D acusaría un ciclo al llegar a D por segunda vez, pero no existe ninguno.

Un orden topológico lista los vértices de modo que, para toda arista v→w, v va antes que w, como el orden para vestirse (calcetines antes que zapatos). Existe solo para grafos dirigidos sin ciclos (DAG) y normalmente no es único: los vértices sin camino entre ellos pueden aparecer en cualquier orden relativo. Para las aristas A→B, A→C, B→D y C→D, A debe ser el primero y D el último, pero B y C pueden intercambiarse: A B C D y A C B D son ambos válidos, así que hay 2 órdenes.

Juntando todo: cómo elegir una estructura

Ahora conoces muchas formas. La habilidad está en mirar lo que el programa hace más, y elegir la forma que es barata para eso. Aquí está el panorama completo lado a lado (promedios, salvo que se diga otra cosa; n es el número de elementos).

Preguntas para hacerse

• ¿Necesito los elementos en orden (ordenados, o la siguiente clave mayor)? Usa un árbol de búsqueda balanceado, no una tabla hash.
• ¿Solo necesito búsqueda exacta por clave? Usa una tabla hash.
• ¿Solo necesito el elemento mayor o menor una y otra vez? Usa un heap.
• ¿Importa el último o el primer elemento (LIFO o FIFO)? Usa una pila o una cola.
• ¿Los elementos están relacionados entre sí en una red? Usa un grafo, con listas si es disperso.
• ¿Es importante el acceso por posición? Usa un array.

Errores comunes

• Creer que una lista enlazada siempre es más rápida que un array porque 'insertar es O(1)'. Llegar al lugar cuesta O(n).
• Olvidar que un ABB simple alimentado con datos ordenados se vuelve una cadena.
• Olvidar los casos vacío y lleno (underflow de pila, cola con un solo elemento, lista vacía, primer nodo).
• Usar una tabla hash con una mala función hash o con un factor de carga alto, o cambiar los campos clave de un objeto después de insertarlo.
• Confundir el TAD (el qué) con su implementación (el cómo).

Para ver estas ideas en movimiento, prueba las visualizaciones de VisuAlgo, donde insertas y quitas claves y ves, paso a paso, listas, heaps, tablas hash, árboles AVL y rojinegros y recorridos de grafos. Para clases, el curso del MIT de abajo cubre secuencias, hashing, árboles binarios, AVL, heaps y búsqueda en grafos.