Skip list

Una skip list o llista per bots és una Estructura de senyes, basada en Llestes enllaçades paraleles en eficiència comparable a la d'un arbre binari (temps en orde O(log n) per a la majoria de les operacions).

Descripció

Una llista per bots es construïx per capes. La capa del fondo (la més baixa) és una senzilla llista enllaçada. Cada capa subsegüent és com una "via ràpida" per a la llista de la capa baix esta. Un element de la capa i apareix en la capa i+1 en una provabilitat fixa p. En promig, cada element apareix en 1/(1-p) llestes, l'element més alt (generalment un element inicial colocat al principi de la llista per bots) apareix en O(log(1/p) n) llestes.

Per a buscar un element s'escomença en l'element inicial de la llista de la capa més alta, fins a alcançar el màxim element que és menor o igual al buscat. Després es passa a la capa següent (baix de l'actual) i es contínua la busca. Es pot verificar que el número esperat de passos en cada llista enllaçada és 1/p. De manera que el cost total de busca és O(log(1/p) n / p), que és lo mateix que O(log n) quan p és una constant. Depenent del valor triat per a p, es pot favorir el cost de busca contra el cost d'almagasenament.

Les operacions d'inserció i borrat s'implementen com les de les seues corresponents llistes enllaçades, llevat que els elements de les capes superiors deuen ser insertats o borrats de més d'una llista enllaçada.

A diferència dels arbres de busca balancejats, el pijor cas per a les operacions de llistes per bots no està garantisat com a logarítmic, ya que és possible encara que poc provable, que es produïxca una estructura no balancejada. No obstant, les llistes per bots treballen be en la pràctica i l'esquema de balancege és més senzill d'implementar que el dels arbres binaris balancejats. Les llistes per bots són útils també per a còmput paralel, ya que es poden realisar insercions en paralel sobre segments diferents sense tindre luego que balancejar l'estructura.

Història

Les llistes per bots varen ser creades per William Pugh i publicades en el seu artícul Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676.

El creador de l'estructura de senyes les descriu aixina:

Les llistes per bots són una estructura provabilística que podria remplazar els arbres balancejats com a método d'implementació preferit en moltes aplicacions. Les operacions de llistes per bots tenen el mateix comportament asintòtic esperat que les dels arbres balancejats, són més ràpides i utilisen menys espai.