Las estructuras de datos explicadas
Todo programa guarda datos en algún sitio, y la forma de guardarlos decide qué es rápido y qué es lento. Una lista de un millón de nombres se puede recorrer nombre a nombre, u ordenar de modo que veinte comparaciones encuentren cualquier nombre. Las estructuras de datos son esas formas de organizar: un puñado de ideas, la mayoría más antiguas que el ordenador personal, que están dentro de cada base de datos, sistema operativo, navegador y videojuego.
Para qué sirve una estructura de datos
Una estructura de datos se elige por las preguntas que tiene que responder. El registro de llamadas de un teléfono necesita primero la última llamada, la cola de una impresora primero el trabajo más antiguo, un diccionario el significado de una palabra entre cien mil, un planificador de rutas el cruce no visitado más cercano. Cada estructura hace rápidas algunas operaciones renunciando a otras, y la notación O grande describe ese intercambio: O(1) significa que el tiempo no crece con el número n de elementos, O(log n) que duplicar n añade un paso, y O(n) que el tiempo crece en proporción a n.
Pilas, colas y deques
Una pila añade y quita por el mismo extremo: último en entrar, primero en salir. Los historiales de deshacer, el botón Atrás y las llamadas de un programa en marcha son pilas. Una cola añade al final y quita por el frente: primero en entrar, primero en salir, como las pulsaciones del teclado o una cola de impresión. Una deque permite ambas cosas en ambos extremos. Las tres tardan un tiempo constante por operación. Una cola suele guardarse en un búfer circular, un arreglo fijo en el que el frente y el final dan la vuelta tras el último hueco; cuando se llena, los elementos se copian a un arreglo del doble de tamaño. Copiar cuesta O(n), pero ocurre tan pocas veces que cada operación sigue costando O(1) en promedio, lo que se llama una cota amortizada.
Listas enlazadas
Una lista enlazada guarda cada valor en un nodo con un puntero al siguiente nodo. Insertar o borrar solo cambia uno o dos punteros, sin desplazar nada, pero no se puede saltar al décimo nodo: hay que seguir los enlaces desde la cabeza. Una lista que solo guarda su cabeza llega a la cola en O(n) pasos; las listas reales suelen guardar también un puntero a la cola, y las doblemente enlazadas un puntero hacia atrás, y así se construyen un historial del navegador o una caché LRU.
Árboles binarios de búsqueda
Un árbol binario de búsqueda guarda, en cada nodo, los valores menores en el subárbol izquierdo y los mayores en el derecho. Una búsqueda compara y va a la izquierda o a la derecha, y un recorrido en orden lee los valores ordenados. Borrar una hoja consiste en quitarla, un nodo con un hijo se sustituye por ese hijo, y un nodo con dos hijos por su sucesor en orden, el valor más pequeño de su subárbol derecho. Todo ello tarda un tiempo proporcional a la altura del árbol: unos log n cuando el árbol es frondoso, pero n cuando los valores llegan ordenados y el árbol degenera en una lista.
Árboles AVL y rojo-negros
Los árboles autoequilibrados reparan su forma después de cada cambio. Un árbol AVL, inventado por Adelson-Velsky y Landis en 1962, mantiene las alturas de los dos subárboles de cada nodo a una de distancia como mucho; cuando el factor de equilibrio de un nodo llega a ±2, una rotación (los casos LL y RR) o dos (LR y RL) lo restablecen. Un árbol rojo-negro colorea sus nodos de modo que la raíz es negra, ningún nodo rojo tiene un hijo rojo y todo camino hacia abajo pasa por el mismo número de nodos negros, lo que limita el camino más largo al doble del más corto. Se repara recoloreando y con pocas rotaciones como mucho, y es el árbol que hay dentro de TreeMap de Java, std::map de C++ y el planificador de Linux.
Montículos y colas de prioridad
Un montículo binario es un árbol binario completo guardado en un arreglo sin punteros: los hijos de la posición i están en 2i + 1 y 2i + 2. En un montículo mínimo cada padre es como mucho igual de grande que sus hijos, así que el valor más pequeño siempre está en la raíz. Un valor nuevo va al final y flota por encima de los padres mayores; extraer la raíz lleva el último valor arriba y lo hunde. Ambas operaciones cuestan O(log n), y un arreglo entero se puede convertir en montículo en O(n). Los montículos mueven las colas de prioridad del algoritmo de caminos mínimos de Dijkstra, de las simulaciones de eventos y de los planificadores de los sistemas operativos, y dan lugar al heapsort.
Tablas hash
Una tabla hash convierte una clave en un índice del arreglo con una función hash y va allí directamente. Claves distintas pueden caer en el mismo índice: es una colisión. El encadenamiento guarda una pequeña lista en cada cubeta; el direccionamiento abierto, como el sondeo lineal, prueba las casillas siguientes hasta encontrar una libre y, al borrar una clave, debe dejar una lápida para que las búsquedas posteriores sigan sondeando. Con una buena función hash y un factor de carga (claves por cubeta) bajo, que se consigue haciendo crecer la tabla, insertar, buscar y borrar cuestan O(1) en promedio. Una función pobre, como sumar los códigos de los caracteres de una palabra, manda los anagramas a la misma cubeta. Las tablas hash están detrás del dict de Python, los objetos de JavaScript y los índices de las bases de datos.
Tries y union-find
Un trie, o árbol de prefijos, guarda cadenas con un carácter por nivel, de modo que las palabras que empiezan igual comparten camino y un nodo marca dónde termina una palabra. Encontrar una palabra de longitud L cuesta L pasos, haya las palabras que haya, y todas las palabras con un prefijo dado están en un mismo subárbol: así funcionan el autocompletado y los correctores ortográficos. Union-find guarda los elementos en conjuntos disjuntos, cada uno un árbol cuya raíz da nombre al conjunto. Find sigue los enlaces al padre hasta la raíz; union cuelga una raíz debajo de otra. Con unión por rango y compresión de caminos, una larga serie de operaciones cuesta un tiempo casi constante cada una, la función inversa de Ackermann α(n), que no pasa de 4 para ningún n realista. El algoritmo de Kruskal del árbol de expansión mínima se apoya en ella.
Preguntas frecuentes
¿Qué diferencia hay entre un arreglo y una lista enlazada?
Un arreglo guarda sus elementos uno junto a otro en memoria, así que cualquier posición se alcanza al instante, pero insertar en medio obliga a desplazar todo lo que viene detrás. Una lista enlazada puede insertar en cualquier sitio cambiando punteros, pero llegar a una posición obliga a recorrerla desde la cabeza. Además, los arreglos aprovechan mucho mejor la caché del procesador, por eso en la práctica suelen ser más rápidos.
¿Qué significa tiempo amortizado?
El coste medio por operación en una larga serie, aunque alguna operación aislada sea cara. Un búfer circular que se duplica al llenarse copia de vez en cuando sus n elementos, pero como las copias son cada vez más raras a medida que el búfer crece, n inserciones cuestan O(n) en total, es decir, O(1) cada una en promedio.
¿Un montículo es lo mismo que un árbol binario de búsqueda?
No. Un árbol binario de búsqueda coloca cada subárbol izquierdo antes de su nodo y cada subárbol derecho después, así que puede listar todos los valores en orden y encontrar cualquier valor rápido. Un montículo solo promete que cada padre va antes que sus hijos, lo que basta para encontrar al instante el mínimo o el máximo, pero no para buscar un valor cualquiera.
¿Cómo sabe union-find si dos elementos están conectados?
Sigue los enlaces al padre desde cada elemento hasta la raíz de su árbol. Si ambos llegan a la misma raíz, están en el mismo conjunto. Después, la compresión de caminos hace que cada nodo del camino apunte directamente a la raíz, así que la siguiente pregunta sobre ellos solo cuesta un paso.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Abrir el visualizador de estructuras de datos