Tamaño
Comparaciones

Operación Promedio Peor caso

Más información sobre las estructuras de datos

Visualizador de estructuras de datos

Una estructura de datos es una forma de guardar datos para que las preguntas más frecuentes se respondan rápido. Elige una de las once estructuras clásicas, desde la pila hasta el árbol rojo-negro, escribe un valor y pulsa una operación. Cada paso se ve en pantalla: qué nodo se compara, qué enlace cambia, por qué un árbol rota o un valor sube, con una frase que dice lo que ocurre. Las fichas cuentan el trabajo de cada operación y una tabla da su tiempo de ejecución. Elige una estructura, escribe un valor y pulsa una operación. Cada operación se reproduce paso a paso: los nodos resaltados muestran qué se compara, se mueve o cambia, y la línea bajo la imagen dice qué ocurre y por qué. Atrás, Paso, Reproducir y Fin recorren de nuevo los pasos. Rellenar al azar y Vaciar empiezan de cero, y Deshacer revierte una operación. Las fichas muestran el tamaño, la altura de los árboles, el trabajo de la última operación (comparaciones, sondeos o enlaces al padre recorridos) y una cifra que importa para la estructura; la tabla da el tiempo de ejecución de cada operación.

Cómo funciona

  1. Elige una estructura, como un árbol binario de búsqueda, una tabla hash o un trie. Empieza con contenido aleatorio; Rellenar al azar y Vaciar empiezan de cero.
  2. Escribe un valor y pulsa una operación: apilar, encolar, insertar, borrar, buscar, un recorrido, union o find. Los pasos se reproducen solos; Atrás, Paso, Reproducir y Fin los recorren de nuevo.
  3. Lee en la línea bajo la imagen qué hace cada paso, mira en las fichas el tamaño, la altura y el trabajo de la última operación, y compara los tiempos de ejecución en la tabla.

Listas, pilas y colas

Las estructuras más sencillas guardan los elementos en fila. Una pila solo trabaja por un extremo, así que el último elemento en entrar es el primero en salir, como una pila de platos; una cola añade al final y saca por el frente, como una fila ante una ventanilla. Aquí la cola vive en un búfer circular: el frente y el final dan la vuelta a un arreglo fijo y vuelven al principio tras el final, y cuando se llena, los elementos se copian a otro del doble de tamaño. Una lista enlazada une nodos con punteros, así que insertar en la cabeza no cuesta nada, pero encontrar la cola o un índice obliga a seguir los enlaces uno a uno.

Árboles, montículos, tablas hash y conjuntos

Un árbol binario de búsqueda guarda los valores menores a la izquierda y los mayores a la derecha, así que una búsqueda divide a la mitad los candidatos en cada paso, siempre que el árbol se mantenga frondoso. Los árboles AVL y rojo-negros se encargan de ello con rotaciones que puedes ver y que llevan el nombre de su caso. Un montículo solo guarda arriba el valor menor o mayor, que es todo lo que necesita una cola de prioridad. Una tabla hash salta directamente a una cubeta calculada a partir de la clave y tiene que lidiar con colisiones; un trie comparte los prefijos de las palabras; union-find dice en tiempo casi constante si dos elementos pertenecen al mismo conjunto.

Preguntas frecuentes

¿Qué estructura de datos debo usar?

Depende de las preguntas que hagas con más frecuencia. Una pila o una cola cuando los elementos se tratan en el orden en que llegan o al revés; una tabla hash para buscar una clave; un árbol de búsqueda equilibrado, como un AVL o un rojo-negro, cuando también necesitas las claves ordenadas o la clave más cercana; un montículo cuando solo necesitas siempre el elemento menor o el mayor; un trie para palabras y prefijos; union-find para seguir grupos que se fusionan.

¿Qué diferencia hay entre un árbol AVL y un árbol rojo-negro?

Ambos mantienen poco profundo un árbol binario de búsqueda, así que cada búsqueda, inserción y borrado tarda un tiempo proporcional a log n. Un árbol AVL se equilibra de forma más estricta, con las alturas de los dos lados de cada nodo a una de distancia como mucho, por lo que las búsquedas son algo más rápidas. Un árbol rojo-negro permite más holgura y necesita menos rotaciones al cambiar, y por eso muchas bibliotecas estándar lo usan para sus mapas y conjuntos ordenados.

¿Por qué una tabla hash puede ser lenta en el peor caso?

Si muchas claves caen en la misma cubeta, una búsqueda tiene que comprobarlas una a una, igual que en una lista. Una buena función hash reparte las claves de manera uniforme y la tabla crece antes de llenarse demasiado, así que una búsqueda tarda en promedio un tiempo constante. Prueba una tabla de tamaño 10 con números que terminan en la misma cifra, o palabras que son anagramas entre sí, para ver cómo se acumulan las colisiones.

¿Qué significan los números junto a los nodos AVL?

Son factores de equilibrio: la altura del subárbol izquierdo de un nodo menos la de su subárbol derecho. En un árbol AVL, cada factor debe ser −1, 0 o +1. Cuando una inserción o un borrado deja uno en +2 o −2, el árbol rota en ese nodo; el caso (LL, RR, LR o RL) indica hacia dónde se inclina la altura de más y decide entre una rotación y dos.

¿Se envía algo a un servidor?

No. Cada operación se ejecuta en tu navegador, y el contenido de cada estructura se guarda en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor