Ich hatte diese Frage auf der Redis-Website gepostet, und Pieter Noordhuis hat dort eine Antwort gegeben, die ich hier querposte:
Das ist richtig. Die sortierte Menge beruht auf einem RNG, um die Anzahl der Ebenen pro Knoten zu bestimmen (es ist eine probabilistische Datenstruktur). Das Einfügen/Löschen eines Elements am Anfang der Skiplist kann O(1) sein, während die theoretische Worst-Case-Leistung O(N) ist (wobei jeder Knoten dieselbe Ebene hat). Die amortisierte Zeitkomplexität beträgt jedoch O(log N), wenn Sie die Verteilung der Ebenen auf die Knoten berücksichtigen.
