listas con saltos

Lista con Saltos (Skip List)

Concepto:
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 adistancias variables, bien establecidas de forma aleatoria o siguiendo un patrón establecido de saltos a longitudes fijas.
Establecimiento
Fue publicada y establecida por William Pugh en su artículoin "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 enque 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 lasnecesidades propias del problema, variando tanto el determinismo de dichos saltos como la longitud de los mismos.
listas con saltos vs abb:
1.       Ventajas frente a los ABB balanceados
a.       Suimplementació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 esnecesario 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ásrá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 deoperaciones

Estructura e Implementación
Cada Nodo de una lista con saltos tiene una conjunto finito de enlaces a otros nodos de la lista estos nodos pueden clasificarse:
1.       Nodo con enlaceCorto
que es el primero y apunta al siguiente nodo de la lista. Es no nulo en todos los nodos excepto el ultimo
2.      Nodo con enlace Medio
que pueden existir en algunos de los nodos y tienen...