Skip list

Skip list

Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O(log n) para la mayoría de las operaciones).

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 bajo esta. 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 al principio de la lista por saltos) aparece en O(log(1/p) n) listas.

Skip list.svg

Para buscar un elemento se empieza con el elemento inicial de la lista de la capa más alta, hasta alcanzar el máximo elemento que es menor o igual al buscado. Luego se pasa a la capa siguiente (debajo de la actual) y se continua la búsqueda. Se puede verificar que el número esperado de pasos en cada lista enlazada es 1/p. De manera 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 el costo 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 o borrados 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 posible aunque poco probable, que se produzca una estructura no balanceada. Sin embargo, las listas por saltos trabajan bien en la práctica y el esquema de balanceo es más sencillo de implementar que el de los árboles binarios balanceados. Las listas por saltos son útiles también para cómputo paralelo, dado que se pueden realizar inserciones en paralelo sobre segmentos diferentes sin tener luego que balancear la estructura.

Origen

Las listas por saltos fueron creadas por William Pugh y publicadas en su artículo Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676. Véase también en [1].

El creador de la estructura de datos las describe así:

Las listas por saltos son una estructura probabilística que podría remplazar los árboles balanceados como método de implementación preferido en muchas aplicaciones. Las operaciones de listas por saltos tienen el mismo comportamiento asintótico esperado que las de los árboles balanceados, son más rápidas y utilizan menos espacio.

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Skip list — Invented in 1990 by William Pugh, a skip list is a probabilistic data structure, based on multiple parallel, sorted linked lists, with efficiency comparable to a binary search tree (order log n average time for most operations).Underlying the… …   Wikipedia

  • Skip-list — Une Skip list (liste à enjambements) est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s effectuent en O(log n)[1] avec une grande probabilité. Sommaire 1 Description 2 Opération de… …   Wikipédia en Français

  • Skip list — Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O(log n) para la mayoría de las operaciones). Una lista por saltos se construye… …   Enciclopedia Universal

  • Skip liste — Skip list Une Skip list (liste à enjambements) est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s effectuent en O(log n)[1] avec une grande probabilité. Sommaire 1 Description 2… …   Wikipédia en Français

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Skip (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Skip (homonymie) », sur le Wiktionnaire (dictionnaire universel) Un skip est une benne roulant sur un… …   Wikipédia en Français

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Skip James — The only photograph of James in his youth. Background information Birth name Nehemiah Curtis James Born …   Wikipedia

  • List of Skip Beat chapters — Skip Beat! by Yoshiki Nakamura is currently being published in Japan by Hakusensha. It is being serialized in the magazine Hana to Yume since February of 2005. In North America it is being published by the Shojo Beat label. There are currently 19 …   Wikipedia

  • Skip Weshner — (1927 1995) was a disc jockey on stations in New York and Los Angeles from the mid 1950 s until the mid 1980 s. In particular, he hosted a popular show on KRHM FM in Los Angeles. He hosted Accent On Sound on WBAI (FM) and later WNCN (FM) in New… …   Wikipedia

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”