Saya telah memposting silang pertanyaan ini di situs web Redis, dan Pieter Noordhuis memberikan jawaban di sana, yang saya posting silang di sini:
Itu betul. Set yang diurutkan bergantung pada RNG untuk menentukan jumlah level per node (ini adalah struktur data probabilistik). Memasukkan/menghapus elemen di awal skiplist dapat berupa O(1), sedangkan kinerja kasus terburuk secara teoritis adalah O(N) (dengan setiap node memiliki level yang sama). Namun, kompleksitas waktu yang diamortisasi adalah O(log N) ketika Anda memperhitungkan distribusi level di antara node.
