Skip List

Una skip list és una estructura de dades probabilística a base de llistes encadenades paral·leles.

Descripció

Una skip list pretén ser una millora d'una llista encadenada ordenada. Conté una jerarquia de subllistes encadenades, cadascuna d'elles sent un subconjunt de la següent i amb la darrera sent un conjunt amb tots els elements. Els elements van sent afegits de forma aleatòria, de manera que la cerca arreu de la llista podria saltar (skip, en anglès) nombroses capes.

La skip list queda organitzada en capes (les subllistes). La capa de més avall és simplement una llista encadenada estàndard. Cada capa superior i+1 és una via ràpida per recórrer les capes inferiors. Un element present a la capa i té una probabilitat fixa p de formar part de la capa immediatament superior (i+1). De mitjana, cada element apareix a 1/(1-p) llistes i l'element més alt (sovint un element fantasma més petit que tots els altres) apareix a O(log_1/p n) capes.

1
1-----4---6
1---3-4---6-----9
1-2-3-4-5-6-7-8-9-10

Consulta

La consulta d'un element comença pel més petit, a la capa més alta. Per cada capa visitada, recorrem els elements fins a topar amb un element superior (o el final de la capa) o un element igual al que cerquem. En el primer cas, davallem verticalment (des del darrer element inferior que hem trobat, que sempre trobarem a sota) a la capa immediata. L'esperança del nombre de passos per cada capa és 1/p. El cost total de la consulta és O(log_1/p (n/p)); que esdevé O(log (n)) si hom considera p com fixa. Conforme juguem amb el valor d'aquest paràmetre p, obtenim un compromís entre temps de recerca i espai de memòria consumit.

Altres operacions

La inserció i la supressió s'implementen com una llista encadenada, excepte que els elements alts han de ser inserits i suprimits a múltiples capes.

Rendiment

Degut a la seva naturalesa probabilística, aquestes estructures de dades no ofereixen les mateixes garanties, al pitjor cas, que un arbre binari balancejat. En efecte, és poc probable però tanmateix possible que la distribució aleatòria produeixi una estructura molt desequilibrada.

De fet, aquestes llistes funcionen molt bé, a la pràctica, i tenen la fama de ser més fàcilment implementables que llurs equivalent deterministes a base de balanceig d'arbres.

Dintre de les implementacions reals, hom ha mesurat que llurs rendiments en temps i en espai són millors que els dels Arbre-B. Això és degut a factors com ara la proximitat de les dades des la memòria cau.

Història

Les skip lists van ser inventades per William Pugh l'any 1990.