Skip Lists

Une Skip List est une alternative intéressante à certaines structures arborescentes comme std::set ou std::map. Cette structure de données associative de type {clé,valeur} n'admet qu'une valeur par clé, conserve les valeurs en ordre croissant de clé, et offre plusieurs caractéristiques intéressantes sur le plan de la complexité algorithmique.

Merci à André Caron pour m'avoir recommandé d'en discuter ici.

Image tirée du Wiki sur le sujet : http://en.wikipedia.org/wiki/Skip_list

L'idée générale va comme suit :

Une Skip List est une liste de noeuds à plusieurs niveaux, au sens où chaque noeud possède une paire {clé,valeur}et au moins un pointeur sur un noeud suivant
Le niveau maximal (nombre maximal de suivants par noeud) est choisi à la construction, mais le nombre de suivants d'un noeud est déterminé de manière pseudoaléatoire
Le niveau zéro de chaque noeud mène au noeud suivant. Si nous parcourions une Skip List strictement à partir des suivants de niveau zéro, alors la Skip List serait essentiellement une liste simplement chaînée avec un coût en espace pour tenir compte des autres niveaux
Les autres niveaux mènent vers un noeud « en avant » un peu plus loin. Plus le niveau est haut et plus épars sont les suivants. Conséquemment, parcourir une Skip List à partir de suivants de niveau près du niveau maximum escamote plusieurs noeuds à la fois
Le parcours d'une Skip List suivra d'abord des suivants de haut niveau, puis des noeuds de plus bas niveau, jusqu'à parcourir des noeuds de niveau zéro dans le pire cas. Ceci correspond à escamoter d'abord les noeuds par grands « blocs », puis par blocs progressivement plus petits, jusqu'à ce que la clé recherchée soit trouvée, ou jusqu'à ce qu'il soit déterminé qu'elle n'est pas dans la Skip List

Ceci fait d'une Skip List un hybride entre une liste simplement chaînée et une structure facilitant un parcours de complexité logarithmique.

Opérations clés

Les opérations clés d'une Skip List suivent. Une implémentation peut bien sûr offrir d'autres services, ou utiliser d'autres noms que ceux utilisés ici.

Nom (français)	Nom (anglais)	Sémantique	Complexité typique	Risques d'échec / d'exception	Remarques
ajouter	insert	Ajouter un élément dans la Skip List. Retourne true seulement si cela a fonctionné	$O(\log{n})$ en moyenne, $O(n)$ dans le pire cas	L'expression skip.insert(k,v) échouera si skip contient déjà un élément à la clé k
retirer	remove	Retirer un élément de la Skip List. Retournera true seulement si l'élément a été retiré	$O(\log{n})$ en moyenne, $O(n)$ dans le pire cas	L'expression skip.remove(k) échouera si skip ne contient pas un élément à la clé k
est_vide	empty	Prédicat qui s'avère seulement si la Skip List est vide	$O(1)$		Si le langage le supporte, sera typiquement const Si le langage le supporte, sera typiquement noexcept
contient	retrieve	Retrouver un élément par sa clé, ou retourner une valeur particulière pour indiquer l'absence d'un tel élément	$O(\log{n})$ en moyenne, $O(n)$ dans le pire cas		Si le langage le supporte, sera typiquement const Plusieurs options sont possibles pour représenter la dualité là, pas là. En pratique, je privilégie un std::optional<T> ou un maybe<T>

Technique

Une implémentation opérationnelle en C++ est disponible ici : ../../Sources/skip_list.html

Lectures complémentaires

Quelques liens pour enrichir le propos.

http://en.wikipedia.org/wiki/Skip_list
Le texte séminal sur le sujet, par William Pugh en 1989 : http://homepage.cs.uiowa.edu/~ghosh/skip.pdf
Une étude des caractéristiques algorithmiques de cette structure de données, par William Pugh en 1989 : http://cglab.ca/~morin/teaching/5408/refs/p90b.pdf
Implémentation C++ d'une Skip List, par Bill Whitney en 1998 : http://www.drdobbs.com/cpp/skip-lists-in-c/184403579 (prudence : il y a plusieurs bogues d'indice dans son implémentation)
Implémenter une Skip List en Python, par Guilherme Kunigami en 2012 : https://kunigami.wordpress.com/2012/09/25/skip-lists-in-python/
Explication avec code dans quelques langages, texte de 2015 : http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_skip.aspx
Bien implémenter une Skip List, texte de 2017 : http://ticki.github.io/blog/skip-lists-done-right/
Une Skip List implémentée en Go, proposée par Stefanie Lai en 2022 : https://www.pixelstech.net/article/1649142989-SkipList-in-Go