Skip List

Explorez l’insertion et la recherche dans une Skip List triée. Saisissez au plus 31 entiers de −99999999 à 99999999, séparés par des virgules ou des espaces. Les entrées vides entre virgules et les clés invalides sont refusées ; les doublons sont ignorés.

Démarrer insère une clé toutes les 0,6 seconde. Pause et Pas permettent une inspection progressive. Effacer supprime la liste construite ; modifier les clés ou la graine fait de même. Entrée dans le champ de recherche lance la recherche après construction. L’éditeur accepte les retours à la ligne ; Ctrl/Meta+Entrée lance l’insertion.

L0 contient toutes les clés triées. Les nœuds montent avec une probabilité de 1/2, jusqu’à quatre niveaux L0–L3. Une même graine (0–4294967295) reproduit les hauteurs pour le même ordre d’entrée. −∞ est la sentinelle de départ, pas une clé enregistrée.

La recherche avance à droite tant que la clé suivante est inférieure à la cible, puis descend. L’orange indique les prédécesseurs visités et le chemin ; un contour bleu marque une correspondance sur L0. Le tableau facultatif montre les pointeurs courants et suivants, y compris les arrêts avant descente. Des lignes répétées peuvent représenter un arrêt après déplacement.

Essayez 3,7,2,9,5,1,8 avec la graine 42, puis recherchez 5 et 6. 5 existe ; 6 s’arrête avant son éventuelle position d’insertion. Les grands diagrammes défilent localement sans réduire le texte.

Les saisies, la progression, le dernier chemin et les détails ouverts sont sauvegardés localement. Le rechargement restaure l’animation en pause. Modifier la recherche efface le chemin précédent. Les brouillons trop volumineux restent dans la session active ; téléchargez les clés avant de recharger.

Modèle pédagogique d’ensemble sans suppression ni données associées. Quatre niveaux fixes ne démontrent pas les performances asymptotiques sur des entrées arbitrairement grandes. Source : algorithme Skip List de William Pugh.