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).
Descripción
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.
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 implementan 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.
Historia
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.[1][2]
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.
Pugh, William (abril de 1989, revisado: Junio 1990), Concurrent Maintenance of Skip Lists(PS, PDF) (CS-TR-2222), Dept. of Computer Science, U. Maryland.
Datos:Q2005893
Multimedia:Skip list
Enero 12, 2022
skip, list, skip, list, lista, saltos, estructura, datos, basada, listas, enlazadas, paralelas, eficiencia, comparable, árbol, binario, tiempo, orden, para, mayoría, operaciones, descripción, editaruna, lista, saltos, construye, capas, capa, fondo, más, baja, . Una skip list o lista por saltos es una Estructura de datos basada en Listas enlazadas paralelas con eficiencia comparable a la de un arbol binario tiempo en orden O log n para la mayoria de las operaciones Descripcion EditarUna lista por saltos se construye por capas La capa del fondo la mas baja es una sencilla lista enlazada Cada capa subsiguiente es como una via rapida 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 mas alto generalmente un elemento inicial colocado al principio 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 mas alta hasta alcanzar el maximo elemento que es menor o igual al buscado Luego se pasa a la capa siguiente debajo de la actual y se continua la busqueda Se puede verificar que el numero esperado de pasos en cada lista enlazada es 1 p De manera que el costo total de busqueda 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 busqueda contra el costo de almacenamiento Las operaciones de insercion y borrado se implementan como las de sus correspondientes listas enlazadas salvo que los elementos de las capas superiores deben ser insertados o borrados de mas de una lista enlazada A diferencia de los arboles de busqueda balanceados el peor caso para las operaciones de listas por saltos no esta garantizado como logaritmico dado que es posible aunque poco probable que se produzca una estructura no balanceada Sin embargo las listas por saltos trabajan bien en la practica y el esquema de balanceo es mas sencillo de implementar que el de los arboles binarios balanceados Las listas por saltos son utiles tambien para computo paralelo dado que se pueden realizar inserciones en paralelo sobre segmentos diferentes sin tener luego que balancear la estructura Historia EditarLas listas por saltos fueron creadas por William Pugh y publicadas en su articulo Skip lists a probabilistic alternative to balanced trees in Communications of the ACM June 1990 33 6 668 676 1 2 El creador de la estructura de datos las describe asi Las listas por saltos son una estructura probabilistica que podria remplazar los arboles balanceados como metodo de implementacion preferido en muchas aplicaciones Las operaciones de listas por saltos tienen el mismo comportamiento asintotico esperado que las de los arboles balanceados son mas rapidas y utilizan menos espacio Notas y referencias Editar Vease tambien en 1 Pugh William abril de 1989 revisado Junio 1990 Concurrent Maintenance of Skip Lists PS PDF CS TR 2222 Dept of Computer Science U Maryland Datos Q2005893 Multimedia Skip list Obtenido de https es wikipedia org w index php title Skip list amp oldid 120646383, wikipedia, wiki, leyendo, leer, libro, biblioteca,
