J'avais cross-posté cette question sur le site Redis, et Pieter Noordhuis y a fourni une réponse, que je cross-poste ici :
C'est exact. L'ensemble trié s'appuie sur un RNG pour déterminer le nombre de niveaux par nœud (c'est une structure de données probabiliste). L'insertion/suppression d'un élément au début de la liste de sauts peut être O(1), tandis que la performance théorique dans le pire des cas est O(N) (chaque nœud ayant le même niveau). Cependant, la complexité en temps amorti est O(log N) lorsque l'on tient compte de la distribution des niveaux entre les nœuds.
