Les skip lists

Les Skip-Lists sont des structures de données probabiliste. Elles ont été inventées par William Pugh dans son article de juin 1990 [1]. Comme explicité dans le titre de l’article, les skip lists ont pour but de remplacer les arbres équilibrés en proposant une autre méthode de recherche d’un élément dans une liste en O(log(n)).

Détails

Nous pouvons voir sur le schéma une skip lists. La structure de données contient plusieurs listes chaînées triées. Chaque liste chaînée correspond à un niveau. Le dernier niveau correpond à la liste contenant tous les éléments triés. Le niveau supérieur est un index du niveau précédent. Ce niveau supérieur permet de faire saut vers l’avant sur le niveau inférieur.

Lors de la création de la liste, il faut définir le paramètre p : la probabilité qu’un élément de la couche i appartienne à la couche i + 1. Chaque élément de la couche apparait en moyenne dans 1/(1-p) listes.

Recherche d’un élémént

Nous partons du niveau le plus haut. Nous testons l’élément sur lequel nous nous trouvons si l’élement recherché est celui du noeud courant alors la recherche s’arrête, sinon nous testons si le noeud suivant de la liste est inférieur , nous avançons dans notre liste sinon nous descendons (sauf si nous sommes sur la dernière liste auquel cas nous n’avons pas trouvé l’élément recherché).

L’espérance du nombre d’étapes dans chaque couche est 1/p. Plus p est grand plus il y aura de noeuds et de niveaux et ainsi plus d’espace mémoire sera nécessaire, l’algorithme sera moins performant.

Remarques

Les Skip lists apportent des résultats intéressants en pratique par rapport aux arbres équilibrés malgré le fait qu’il y ait une probabilité que la construction soit déséquilibrée.

Il est facile de trouver sur internet des implémentations de cette structure. Facebook a ouvert du code ici qui est une implémentation en C++. Cette implémentation s’appuie sur l’article suivant A Provably Correct Scalable Concurrent Skip List by Herlihy.