Eine Skip-Liste ist eine randomisierte Datenstruktur, die sich als Alternative zu balancierten Binärbäumen anbietet.
Definition
- Sie besteht aus
vielen linearen, sortierten Listen - Jeder Wert ist in der Liste
enthalten - Die Höhe
eines Wertes gibt an, in welchen Listen der Wert enthalten ist. Diese wird einmalig beim Einfügen des Wertes bestimmt. - Ein Wert
hat Höhe mit Wahrscheinlichkeit - Für die erwartete Höhe gilt somit:
- Erwarteter Speicheraufwand für eine Skip-Liste mit
Werten: - Die erwartete Höhe einer Skip-Liste ist
Laufzeit
Jede Wörterbuchoperation (Suchen, Einfügen, Entfernen) hat im Mittel eine Komplexität von
Beispiel
L4 X --------------> X --------------------------------> X
L3 X --------------> X --------------------------> X --> X
L2 X --> X --------> X --------------> X --------> X --> X
L1 X --> X --------> X --> X --------> X---> X --> X --> X
L0 X --> X --> X --> X --> X --> X --> X --> X --> X --> X
^ 2 5 7 8 11 12 14 23 ^
first last