Listas

LISTAS POR SALTOS
1. DEFINICION
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 representauna 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 mecanismode 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 delos mismos.
Una lista por saltos se construye por capas. La capa del fondo (la más baja) es una sencilla lista enlazada. Cada capa subsiguiente es como una "vía rápida" para la lista de la capa debajo. Un elemento de la capa i aparece en la capa i+1 con una probabilidad fija p. En promedio, cada elemento aparece en 1/(1-p) listas, el elemento más alto (generalmente un elemento inicial colocado alprincipio de la lista por saltos) aparece en O(log(1/p) n) listas.



Para buscar un elemento se empieza con el elemento inicial de la lista de la capa más alta hasta alcanzar el máximo elementoque es menor o igual al buscado, se pasa a la capa siguiente (debajo de la actual) y se continúa la búsqueda. Se puede verificar que el número esperado de pasos en cada lista enlazada es 1/p. Demanera que el costo total de búsqueda es O(log(1/p) n / p), que es lo mismo que O(log n) cuando p es una constante. Dependiendo del valor escogido para p, se puede favorecer el costo de búsqueda contra elcosto de almacenamiento.
Las operaciones de inserción y borrado se implantan como las de sus correspondientes listas enlazadas, salvo que los elementos de las capas superiores deben ser insertados oborrados de más de una lista enlazada.
A diferencia de los árboles de búsqueda balanceados, el peor caso para las operaciones de listas por saltos no está garantizado como logarítmico, dado que es...