Skip List I -Busqueda

Estructura de búsqueda dinámica, aleatoria, simple y eficiente para almacenar listas organizadas de objetos. Para entender como funciona vamos a considerar una simple lista enlazada, que conecta todos los nodos ordenadamente, este es el Nivel 0 (N0). El primer cuandro donde está el nombre del nivel lo llamaremos cabecera.


Ahora agregaremos el nivel 1, que es otra lista enlazada pero los nodos son un subconjunto del nivel 0



El siguiente nivel 2 es ahora un subconjunto del nivel 1. Como te darás cuenta, cada vez que subimos de nivel tenemos menos nodos conectados.

Las skip lists o listas de saltos, tienen 3 operaciones básicas, buscar, insertar o eliminar.

Buscar  

Para encontrar el nodo 12, empezamos desde la cabecera del nivel mas arriba N2, buscamos el nodo de la lista mas cercano, que tambien es 12, comparamos ¿12 > 12? Falso, por lo que contamos un paso a la derecha, ¿12 = 12? Verdadero. Terminamos y solo necesitamos un paso para encontrarlo


Ahora busquemos el nodo7, este requiere mas pasos:

1. Iniciamos en la cabecera de N2 (nivel 2). Buscamos el nodo mas cercano a la cabecera que es 12 Comparamos ¿7 > 12? Falso, entonces bajamos a la cabecera N1, dibujamos una flecha y contamos un paso.
2. En la cabecera N1 Buscamos el nodo mas cercano que es 4, comparamos ¿7 > 4? Verdadero, entonces avanzamos un paso a la derecha ¿7=4? Falso, Continua el algoritmo
3. Buscamos el siguiente nodo, que es 12, ¿7>12? Falso, permanecemos en 4, bajamos un al nivel N0 y contamos otro paso.
4. En 4 de N0 Buscamos el siguiente nodo que es 7,comparamos ¿7>7? Falso, ¿7=7? Verdadero, Lo encontramos

Si quisiéramos buscar al nodo 8 que no está en la lista, el procedimiento sería el mismo, pero agregamos un paso de comparación 7<8<12, sin embargo pertenecemos en 7.

Otro ejemplo:

Buscar 78 requiere de 7 pasos



Buscar 12 requiere de 4 pasos


Buscar 63 requiere de 8 pasos, donde el último paso es de verificación sin avance ya la búsqueda se termina en el nodo 56