Was ist eine Skip List und wie erreicht sie O(log n) Suche?

Question

Accepted Answer

Eine **Skip List** ist eine sortierte verkettete Liste, die mit mehreren **"Expressbahnhofs"-Ebenen** erweitert ist. Höhere Ebenen überspringen viele Knoten, sodass die Suche hinab und nach rechts geht und **O(log n)** erwartete Zeit erreicht — wie eine probabilistische, einfachere Alternative zu einem balancierten Baum. ## Struktur ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Jeder Knoten wird mit Wahrscheinlichkeit `p` (oft 0,5) auf höhere Ebenen befördert, sodass durchschnittlich jede Ebene halb so viele Knoten wie die darunter hat. ## Suche ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Komplexität | Operation | Erwartet | Speicher | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Kompromisse vs balancierte Bäume - **Stärken:** viel einfacher zu implementieren als red-black/AVL; keine Rotationen; einfache Concurrent-Versionen (in Redis Sorted Sets und Java `ConcurrentSkipListMap` verwendet). - **Schwächen:** probabilistische Garantien (nicht Worst-Case); zusätzliche Zeiger pro Knoten. ## Warum es wichtig ist Skip Lists bieten baumähnliche O(log n) sortierte Operationen mit viel weniger Code und einfach umgesetzter Lock-Free Concurrency, weshalb echte Systeme wie Redis sie wählen. Sie sind ein großartiges Beispiel für die Verwendung von **Randomisierung** zum Ersetzen komplexer deterministischer Balancierungslogik.