DE 
English
Українська
Polski
Español
日本語
Italiano
Português (BR)
Français
العربية
Nederlands
中文
한국어
हिन्दी
Türkçe
Tiếng Việt
Русский
Bahasa Indonesia
فارسی
বাংলা
ไทย
Filipino
Kiswahili
اردو
Bahasa Melayu
தமிழ்
עברית
Ελληνικά
ਪੰਜਾਬੀ
አማርኛ
မြန်မာဘာသာ
ខ្មែរ
ქართული
नेपाली
Монгол хэл
Հայերեն
සිංහල
ລາວ
Čeština
Română
Magyar
Български
Svenska
Dansk
Suomi
Norsk
Slovenčina
Hrvatski
Српски
Slovenščina
Lietuvių
Latviešu
Eesti
Íslenska
Shqip
Македонски
Bosanski
Malti
Azərbaycanca
Қазақша
O'zbekcha
Тоҷикӣ
Кыргызча⏭️ Skip-Liste — Probabilistische balancierte Suche
Eine Skip-Liste stapelt Express-Spuren über einer sortierten verketteten Liste: Jeder Knoten wird mit Wahrscheinlichkeit ½ befördert, was eine erwartete O(log n)-Suche ermöglicht, indem auf hohen Ebenen vorausgesprungen und dann abgestiegen wird.
Über die Skip-Liste
Eine Skip-Liste, 1990 von William Pugh eingeführt, ist eine probabilistische Datenstruktur, die eine sortierte Folge von Elementen über mehrere verkettete Listenebenen hinweg pflegt. Die unterste Ebene ist eine vollständige sortierte Liste; jede höhere Ebene fungiert als „Express-Spur", indem sie nur eine zufällige Teilmenge der darunterliegenden Ebene beibehält, wobei jedes Element unabhängig mit Wahrscheinlichkeit p (typischerweise 0,5) befördert wird. Suche, Einfügen und Löschen erreichen alle eine erwartete O(log n)-Zeit — vergleichbar mit einem balancierten BST — ohne den deterministischen Ausgleichsaufwand von AVL- oder Rot-Schwarz-Bäumen.
Diese Simulation lässt Sie Integer-Schlüssel einfügen und löschen, während Sie beobachten, wie der Turm jedes Knotens auf eine zufällige Höhe wächst. Der hervorgehobene Traversierungspfad während der Suche zeigt, wie der Algorithmus durch Express-Spuren absteigt, bevor er zur nächsten Ebene fällt, und veranschaulicht, warum die durchschnittliche Anzahl der Vergleiche ungefähr log1/p n beträgt.
Häufig gestellte Fragen
Wie erreicht eine Skip-Liste eine O(log n)-Suche ohne deterministische Balance?
Die Höhe jedes Knotens wird unabhängig aus einer geometrischen Verteilung mit Erfolgswahrscheinlichkeit p gezogen, sodass die erwartete Anzahl der Knoten auf Ebene k n·pk beträgt. Eine Suche beginnt auf der höchsten Ebene, geht so weit wie möglich vor und steigt dann ab — die erwartete Gesamtzahl der Vergleiche ist log1/p n + 1/p, was O(log n) ist. Zufälligkeit balanciert die Struktur im Erwartungswert effektiv ohne explizite Rotationen.
Was ist die Worst-Case-Zeitkomplexität einer Skip-Liste?
Die Worst-Case-Zeit ist O(n) — zum Beispiel, wenn zufällig jeder Knoten auf jede Ebene befördert wird — aber dies tritt mit exponentiell kleiner Wahrscheinlichkeit auf. In der Praxis werden Skip-Listen dort eingesetzt, wo probabilistische Garantien akzeptabel sind (z. B. verwenden Redis' Sorted Sets intern eine Skip-Liste), da Worst-Case-Garantien von balancierten Bäumen in diesen Kontexten selten benötigt werden.
Wie viel Speicher verwendet eine Skip-Liste im Vergleich zu einem balancierten BST?
Bei einer Beförderungswahrscheinlichkeit von p = 0,5 beträgt die erwartete Gesamtzahl der Zeiger über alle Ebenen 2n (jeder Knoten trägt einen Zeiger pro Ebene bei, erwartete Höhe 1/(1−p) = 2). Ein Standard-Rot-Schwarz-Baumknoten speichert ebenfalls zwei Kindzeiger plus einen Elternzeiger und ein Farbbit, sodass der Speicherverbrauch vergleichbar ist; Skip-Listen haben oft etwas höhere Konstantenfaktoren aufgrund der variablen Turm-Allokationen.
Wie erhält das Einfügen in eine Skip-Liste die sortierte Reihenfolge?
Das Einfügen sucht zunächst nach der Position, an der der neue Schlüssel gehört (wobei der am weitesten rechts besuchte Knoten auf jeder Ebene in einem Update-Array festgehalten wird), erzeugt dann eine zufällige Höhe h für den neuen Knoten und spleißt ihn schließlich auf jeder Ebene von 0 bis h−1 ein, indem die während der Suche aufgezeichneten Vorwärtszeiger aktualisiert werden. Dies ist analog zum Einfügen in eine verkettete Liste, wiederholt für jede aktive Ebene.
Welcher Wert der Beförderungswahrscheinlichkeit p liefert die beste Leistung?
p = 0,5 balanciert erwartete Suchzeit und Speicherplatz: Ein niedrigeres p reduziert den Speicherbedarf, erhöht aber die erwarteten Vergleiche pro Ebene; ein höheres p erhöht den Speicherbedarf. Pughs ursprüngliche Analyse zeigte, dass p = 0,25 nahezu die gleiche erwartete Zeit bei 25 % weniger Zeigern liefert, und Redis verwendet p = 0,25 für seine Skip-Listen-Implementierung. Die optimale Wahl hängt vom Lese-/Schreibverhältnis und den Speicherbeschränkungen der Anwendung ab.
Wie schneidet eine Skip-Liste im Vergleich zu einem binären Suchbaum bei nebenläufiger Nutzung ab?
Skip-Listen werden in nebenläufigen Umgebungen oft bevorzugt, weil lock-freie und wait-freie Varianten viel einfacher zu implementieren sind als nebenläufige balancierte BSTs. Lock-freie Skip-Listen (z. B. der Harris-Fraser-Shavit-Algorithmus) benötigen nur atomares Compare-and-Swap auf einzelnen Zeigern, während nebenläufige AVL- oder Rot-Schwarz-Bäume ganze Rotationsketten sperren oder sorgfältig versionieren müssen. Javas ConcurrentSkipListMap verwendet diesen Ansatz.
Gibt es eine deterministische Version einer Skip-Liste?
Ja. Deterministische Skip-Listen (auch 1–2-Skip-Listen oder B-Skip-Listen genannt) erzwingen exakte strukturelle Regeln statt sich auf Randomisierung zu verlassen und garantieren so O(log n) Worst-Case-Zeit. Sie erfordern jedoch eine komplexere Einfüge- und Löschlogik, die einem B-Baum näher steht als der eleganten Münzwurf-Einfachheit, die probabilistische Skip-Listen beliebt macht.
Welche realen Systeme verwenden Skip-Listen?
Redis verwendet eine Skip-Liste, um seinen Sorted-Set-Datentyp zu unterstützen und ermöglicht so O(log n)-Rangabfragen und Bereichsscans nach Score. Apache Cassandra verwendete früher Skip-Listen für seinen In-Memory-Memtable-Speicher. LevelDB und RocksDB verwenden eine Variante für ihren In-Memory-Schreibpuffer. Auch die ConcurrentSkipListMap und ConcurrentSkipListSet der Java-Standardbibliothek werden von einer Skip-Liste unterstützt.
Wie wird aus Skip-Listen gelöscht?
Das Löschen lokalisiert den Knoten und aktualisiert für jede Ebene, auf der er vorkommt, den Vorwärtszeiger des Vorgängers, um ihn zu überspringen. Nach dem Entfernen kann der Turm des gelöschten Knotens freigegeben werden. Wenn die Löschung die effektive Höhe der Liste verringert (d. h. die oberen Ebenen leer werden), wird der maximale Ebenenzähler verringert. Die erwartete Zeit ist O(log n), passend zur Suche.
Kann eine Skip-Liste Bereichsabfragen effizient unterstützen?
Ja — das ist einer der praktischen Vorteile von Skip-Listen gegenüber Hashtabellen. Nach einer O(log n)-Suche zum Finden des Bereichsanfangs bietet die verkettete Liste auf unterster Ebene eine O(k)-Traversierung, um alle k Elemente im Bereich zu sammeln. Redis nutzt dies für ZRANGEBYSCORE- und ZRANGEBYLEX-Befehle, die für Rangliste- und Zeitreihen-Anwendungsfälle zentral sind.
Eine Skip-Liste stapelt Express-Spuren über einer sortierten verketteten Liste: Jeder Knoten wird mit Wahrscheinlichkeit ½ befördert, was eine erwartete O(log n)-Suche ermöglicht, indem auf hohen Ebenen vorausgesprungen und dann abgestiegen wird.
3D · Three.js / WebGL-Renderer · Ziel 60 FPS · läuft vollständig clientseitig, keine Installation nötig