Skip List

Explora la inserción y la búsqueda en una Skip List ordenada. Introduce hasta 31 enteros de −99999999 a 99999999, separados por comas o espacios. Se rechazan las entradas vacías entre comas y las claves no válidas; se omiten los duplicados.

Iniciar inserta una clave cada 0,6 segundos. Pausa y Paso permiten revisar el proceso. Borrar elimina la lista construida; cambiar las claves o la semilla también la borra. Intro en el campo de búsqueda busca al terminar la construcción. El editor admite saltos de línea; Ctrl/Meta+Intro inicia la inserción.

L0 contiene todas las claves ordenadas. Los nodos suben con probabilidad 1/2, hasta cuatro niveles L0–L3. La misma semilla (0–4294967295) reproduce las alturas con el mismo orden de entrada. −∞ es el nodo inicial, no una clave almacenada.

La búsqueda avanza a la derecha mientras la siguiente clave sea menor que el objetivo y luego baja. El naranja muestra los predecesores visitados y el camino; un borde azul marca una coincidencia en L0. La tabla opcional muestra los punteros actuales y siguientes, incluidas las paradas antes de bajar. Las filas repetidas pueden representar una parada tras avanzar.

Prueba 3,7,2,9,5,1,8 con semilla 42 y busca 5 y 6. 5 existe; 6 se detiene antes de su posible posición de inserción. Los diagramas grandes se desplazan localmente sin reducir el texto.

Las entradas, el progreso, el último camino y los detalles abiertos se guardan localmente. Al recargar, la animación queda pausada. Editar la búsqueda borra el camino anterior. Los borradores demasiado grandes permanecen en la sesión activa; descarga las claves antes de recargar.

Modelo educativo de conjunto sin eliminación ni datos asociados. Cuatro niveles fijos no demuestran el rendimiento asintótico con entradas arbitrariamente grandes. Fuente: algoritmo Skip List de William Pugh.