Avevo postato in modo incrociato questa domanda sul sito Web Redis e Pieter Noordhuis ha fornito una risposta lì, che sto postando qui:
È corretto. L'insieme ordinato si basa su un RNG per determinare il numero di livelli per nodo (è una struttura dati probabilistica). L'inserimento/cancellazione di un elemento all'inizio della skiplist può essere O(1), mentre la prestazione teorica nel caso peggiore è O(N) (con ogni nodo avente lo stesso livello). Tuttavia, la complessità temporale ammortizzata è O(log N) se si tiene conto della distribuzione dei livelli tra i nodi.
