Saltar al contenido

Lista de omisión en la estructura de datos

octubre 16, 2021
skip list in data structure

¿Qué es una lista de omisión?

Una lista de omisión es una estructura de datos probabilística. La lista de omisión se utiliza para almacenar una lista ordenada de elementos o datos con una lista vinculada. Permite que el proceso de los elementos o datos se visualice de manera eficiente. En un solo paso, omite varios elementos de la lista completa, por lo que se conoce como lista de omisión.

La lista de omisión es una versión ampliada de la lista vinculada. Permite al usuario buscar, eliminar e insertar el elemento muy rápidamente. Consiste en una lista base que incluye un conjunto de elementos que mantiene la jerarquía de enlaces de los elementos subsiguientes.

Estructura de lista de omisión

Está construido en dos capas: la capa más baja y la capa superior.

La capa más baja de la lista de omisión es una lista enlazada ordenada común, y las capas superiores de la lista de omisión son como una «línea rápida» donde se omiten los elementos.

Tabla de complejidad de la lista de omisión

S. No Complejidad Caso medio Peor de los casos
1. Complejidad de acceso O (inicio de sesión) Sobre)
2. Complejidad de búsqueda O (inicio de sesión) Sobre)
3. Eliminar complejidad O (inicio de sesión) Sobre)
4. Insertar complejidad O (inicio de sesión) Sobre)
5. Complejidad espacial O (nlogn)

Funcionamiento de la lista de omisión

Tomemos un ejemplo para comprender el funcionamiento de la lista de omisión. En este ejemplo, tenemos 14 nodos, de modo que estos nodos se dividen en dos capas, como se muestra en el diagrama.

La capa inferior es una línea común que une todos los nodos, y la capa superior es una línea rápida que une solo los nodos principales, como puede ver en el diagrama.

Suponga que quiere encontrar 47 en este ejemplo. Comenzará la búsqueda desde el primer nodo de la línea rápida y continuará corriendo en la línea rápida hasta que encuentre un nodo que sea igual a 47 o más de 47.

Puedes ver en el ejemplo que 47 no existe en la línea express, entonces buscas un nodo de menos de 47, que es 40. Ahora, vas a la línea normal con la ayuda de 40, y buscas el 47, como se muestra en el diagrama.

Lista de omisión en la estructura de datos

Nota: Una vez que encuentre un nodo como este en la «línea rápida», vaya de este nodo a un «carril normal» usando un puntero, y cuando busque el nodo en la línea normal.

Operaciones básicas de la lista de omisión

Existen los siguientes tipos de operaciones en la lista de omisión.

  • Operación de inserción: Se utiliza para agregar un nuevo nodo a una ubicación particular en una situación específica.
  • Operación de eliminación: Se utiliza para eliminar un nodo en una situación específica.
  • Operación de búsqueda: La operación de búsqueda se utiliza para buscar un nodo en particular en una lista de omisión.

Algoritmo de la operación de inserción

Algoritmo de operación de eliminación

Algoritmo de operación de búsqueda

Ejemplo 1: Cree una lista de omisión, queremos insertar estas siguientes claves en la lista de omisión vacía.

  1. 6 con nivel 1.
  2. 29 con nivel 1.
  3. 22 con nivel 4.
  4. 9 con nivel 3.
  5. 17 con nivel 1.
  6. 4 con nivel 2.

Respuesta:

Paso 1: Insertar 6 con nivel 1

Lista de omisión en la estructura de datos

Paso 2: Insertar 29 con nivel 1

Lista de omisión en la estructura de datos

Paso 3: Insertar 22 con nivel 4

Lista de omisión en la estructura de datos

Paso 4: Insertar 9 con nivel 3

Lista de omisión en la estructura de datos

Paso 5: Insertar 17 con nivel 1

Lista de omisión en la estructura de datos

Paso 6: Insertar 4 con nivel 2

Lista de omisión en la estructura de datos

Ejemplo 2: Considere este ejemplo donde queremos buscar la clave 17.

Lista de omisión en la estructura de datos

Respuesta:

Lista de omisión en la estructura de datos

Ventajas de la lista de omisión

  1. Si desea insertar un nuevo nodo en la lista de omisión, insertará el nodo muy rápido porque no hay rotaciones en la lista de omisión.
  2. La lista de omisión es fácil de implementar en comparación con la tabla hash y el árbol de búsqueda binaria.
  3. Es muy sencillo encontrar un nodo en la lista porque almacena los nodos en forma ordenada.
  4. El algoritmo de lista de omisión se puede modificar muy fácilmente en una estructura más específica, como listas de omisión indexables, árboles o colas de prioridad.
  5. La lista de omisión es una lista sólida y confiable.

Desventajas de la lista de omisión

  1. Requiere más memoria que el árbol equilibrado.
  2. No se permite la búsqueda inversa.
  3. La lista de omisión busca en el nodo mucho más lento que la lista vinculada.

Aplicaciones de la lista de omisión

  1. Se utiliza en aplicaciones distribuidas y representa los punteros y el sistema en las aplicaciones distribuidas.
  2. Se utiliza para implementar una cola concurrente elástica dinámica con baja contención de bloqueo.
  3. También se utiliza con la clase de plantilla QMap.
  4. La indexación de la lista de omisión se utiliza para ejecutar problemas de mediana.
  5. La lista de omisión se utiliza para la publicación con codificación delta en la búsqueda de Lucene.

close