Qu'est-ce qu'une skip list et comment atteint-elle une recherche en O(log n) ?

Question

Accepted Answer

Une **skip list** est une liste chaînée ordonnée augmentée de plusieurs niveaux de **« voies express »**. Les niveaux supérieurs ignorent de nombreux nœuds, de sorte que la recherche descend et se déplace vers la droite, obtenant un temps attendu de **O(log n)** — une alternative probabiliste et plus simple à un arbre équilibré. ## Structure ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Chaque nœud est promu à des niveaux supérieurs avec probabilité `p` (souvent 0,5), donc en moyenne chaque niveau a deux fois moins de nœuds que celui en dessous. ## Recherche ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Complexité | Opération | Attendu | Espace | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Compromis par rapport aux arbres équilibrés - **Forces :** beaucoup plus simple à implémenter qu'un red-black/AVL ; pas de rotations ; versions concurrentes faciles (utilisées dans les ensembles triés de Redis, `ConcurrentSkipListMap` de Java). - **Faiblesses :** garanties probabilistes (non pire cas) ; pointeurs supplémentaires par nœud. ## Pourquoi c'est important Les skip lists fournissent des opérations ordonnées ressemblant à un arbre en O(log n) avec beaucoup moins de code et une concurrence sans verrouillage facile, c'est pourquoi les systèmes réels comme Redis les choisissent. Elles sont un excellent exemple d'utilisation de **randomisation** pour remplacer une logique d'équilibrage déterministe complexe.