Skip List

Skip List

Una lista de saltos (skip list) representa una lista ordenada simplemente enlazada, en la cual cada nodo contiene un número variable de enlaces con otros nodos de la estructura. El n-avo enlace de un nodo apunta a los nodos de n-enlaces siguiente de la lista, saltando los nodos intermedios de menos de n enlaces.

Lista ordenada (y en principio sin claves repetidas) en la que cada nodo puede tener uno o varios enlaces al nodo siguiente y a diversos nodos a distancias variables, bien establecidas de forma aleatoria o siguiendo un patrón establecido de saltos a longitudes fijas.

Puede estudiarse como una colección de listas enlazadas en diferentes niveles. Un recorrido por la lista de menor nivel, el cero, pasa por todas las claves de la lista.

La estructura tiene además un nodo con el máximo número de niveles que sirve de encabezado, y un solo nodo centinela, en el que se almacena un valor mayor que el máximo valor de clave que puede almacenarse en la estructura. A ese nodo apuntan los últimos enlaces de cada lista.

La operación de búsqueda parte por la lista de mayor nivel, que tenga nodos con valores; hasta que se encuentre el nodo con el valor o un nodo con una clave menor que el buscado. En este último caso, en el nodo con clave menor se repite el procedimiento anterior, pero en la lista de un nivel menor.

Por ejemplo para buscar el nodo con clave 12, se parte en la lista de nivel 3, se revisa el nodo con clave 6 y se continúa con el siguiente, pero éste es el centinela que tiene clave mayor que 12. Entonces se desciende un nivel y se recorre ahora la lista del segundo nivel a partir del nodo con clave 6. Se avanza al 10, saltándose el 8; pero como la clave 15 es mayor que la buscada, se vuelve a descender un nivel y se repite la búsqueda a partir de la lista del primer nivel que comienza en 10. Es preciso volver a descender un nivel y repetir la búsqueda, encontrándose finalmente el 12. Si se hubiera buscado el valor 13, el proceso es similar al anterior, pero la búsqueda falla, ya que luego del 12 se encuentra un nodo con clave mayor que el buscado.

Fue publicada y establecida por William Pugh en su artículo in "Skip Lists: A Probabilistic Alternative to Balanced Trees", W. Pugh (CACM, June 1990), y representa una estructura que proporciona mecanismos de búsqueda altamente eficaces del orden de O(Log n), y en que en muchos casos es superior al manejo de ABB balanceados, ya que mientras en este el mecanismo de enlace de nodos es fijo en la lista con saltos el mecanismo de enlace puede ser ajustado a las necesidades propias del problema, variando tanto el determinismo de dichos saltos como la longitud de los mismos.

Comparándolo con los ABB balanceados, las operaciones de inserción, añadido y eliminación de elementos son siempre más simples y de complejidad mucho menor y es una estructura mucho más robusta en la que las posibilidades de error y degradado son menores y su recuperación mucho más sencilla. La razón de todo ello viene del hecho de que en la lista con saltos solo se manejan enlaces a nodos en posiciones siguientes con algoritmos de establecimiento de los mismos muy sencillos y que no necesitan el cambio de la estructura en sí.

Por otra parte la eficacia de las operaciones en la Lista con saltos no depende del orden de inserción de los elementos en la estructura, con lo que su eficacia es constante.

Resumiendo:

1. Ventajas frente a los ABB balanceados

a. Su implementación es más sencilla

b. Es necesario menos espacio de almacenamiento para su manejo (en operaciones intermedias)

c. En las operaciones de Inserción y eliminación no es necesario rehacer (Rebalancear) la estructura

d. Soporta fácilmente la mezcla, unión y diferencia de listas

2. Desventajas

a. No siempre la operación de búsqueda (e inserción) es Más rápida (tiempo máquina) que en los ABB

b. En muchos casos la dependencia de algoritmos con carácter aleatorio puede dificultar el seguimiento de los movimientos en la estructura y depuración de operaciones

Estructura de una Skip List

Cada Nodo de una lista con saltos tiene un conjunto finito de enlaces a otros nodos de la lista estos nodos pueden clasificarse:

1. Nodo con enlace Corto

que es el primero y apunta al siguiente nodo de la lista. Es no nulo en todos los nodos excepto el último

2. Nodo con enlace Medio

que pueden existir en algunos de los nodos y tienen referencias a otros nodos a corta distancia

3. Nodos con enlace largo

establecidos en un pequeño número de nodos y contienen referencias a nodos a largas distancias

El Primer nodo de una lista con saltos tiene el máximo número de enlaces posibles en la lista, en el resto de los nodos el número de enlaces puede ser establecido:

1. De forma aleatoria, mediante un criterio probabilista en el que se parte de la situación particular de la estructura para el establecimiento del número total de enlaces

2. De forma probabilista en el que se establecen criterios fijos para determinar el número de enlaces

...