Skip list

Les skip lists ont été inventées par William Pugh, d'abord présentées dans un rapport technique en 1989[3] puis présentées dans une publication en 1990[4]. L'auteur, dans son rapport technique les compare avec les arbres binaires de recherche balancés, écrit :

''Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.''

(Les skip lists sont une structure de données qui a l'air de surpasser les arbres (binaires de recherche) balancés comme une méthode d'implémentation de choix pour plusieurs applications. Les algorithmes des skip lists ont la même complexité asymptotique en espérance que les arbres balancés, et sont plus simples, plus rapides et utilisent moins de mémoire)

Une skip list se présente comme une amélioration d'une liste chaînée triée. Elle contient des pointeurs supplémentaires vers l'avant, ajoutés de façon aléatoire, de sorte que la recherche dans la liste puisse « sauter » (to skip en anglais) de nombreux éléments.

La skip list est organisée en couches. La couche la plus basse est simplement une liste chaînée standard. Chaque couche supérieure i+1 est une « voie rapide » pour parcourir les couches inférieures 1, …, i. Un élément présent sur la couche i a une probabilité fixée p de faire partie de la couche i+1. En moyenne, chaque élément apparaît dans 1/(1-p) couches, et l'élément le plus haut (souvent un élément factice[5] plus petit que tous les autres) apparaît dans toutes les couches. La skip list contient O(log_1/p n) couches, où n est le nombre d'éléments total.

Exemple d'une skip list contenant 10 éléments avec 4 couches.

L'exemple suivant montre une skip list contenant 10 éléments avec 4 couches :

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

La recherche commence par le plus petit élément, sur la couche la plus haute. Pour chaque couche visitée, on parcourt les chaînons jusqu'à atteindre le dernier élément inférieur ou égal à l'élément recherché. Alors, si cet élément est strictement inférieur à la valeur recherchée, on descend verticalement dans la couche suivante. L'espérance du nombre de pas dans chaque couche est 1/p. Le coût total de la recherche est en ${\displaystyle O\left(\log _{\frac {1}{p}}\left(n/p\right)\right)}$ ; ce qui revient à ${\displaystyle O(\log(n))}$ si l'on considère p comme fixé.

En jouant sur la valeur de ce paramètre p, on obtient un compromis entre-temps de recherche et espace mémoire consommé. Pour p = 0, la skip list est une liste chaînée standard (une couche seulement). Plus p proche de 1, plus il y a de couches.

Insertion de 80 dans une skip list.

L'insertion et la suppression s'implémentent comme dans une liste chaînée, sauf que les éléments « hauts »[6] doivent être insérés et supprimés dans plusieurs couches.

De par sa nature probabiliste, cette structure de données ne donne pas les mêmes garanties sur les pires cas que, par exemple, les arbres équilibrés. En effet, il est très peu probable mais néanmoins possible que l'agencement aléatoire ait pu produire une structure très déséquilibrée[7].

En fait, ces listes fonctionnent très bien en pratique, et sont réputées plus faciles à implémenter que leur équivalent déterministe à base de rééquilibrage d'arbres. Dans les implémentations réelles, on a mesuré que leurs performances en temps et en espace sont inférieures à celles des B-trees. Cela est dû à des problématiques telles que la proximité des données dans les mémoires cache.

Dans les skip listes déterministes, les éléments à sauter ne sont pas choisis aléatoirement mais de manière déterministe[8].

• « Lecture 7: Randomization: Skip Lists (vidéo) », sur MIT