Hvad er en skip list, og hvordan opnår den O(log n) søgning?

Question

Accepted Answer

En **skip list** er en ordnet linked list udvidet med flere niveauer af **"ekspressbaner"**. Højere niveauer springer over mange noder, så søgningen går ned og til højre, hvilket opnår **O(log n)** forventet tid — som et probabilistisk, simplere alternativ til et balanceret træ. ## 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) ``` Hver node forfremmes til højere niveauer med sandsynlighed `p` (ofte 0,5), så i gennemsnit har hvert niveau halvt så mange noder som det under det. ## Søgning ```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 ``` ## Kompleksitet | Operation | Forventet | Plads | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Afvejninger vs balancerede træer - **Styrker:** meget enklere at implementere end red-black/AVL; ingen rotationer; lette concurrency-versioner (brugt i Redis sorted sets, Java `ConcurrentSkipListMap`). - **Svagheder:** probabilistiske garantier (ikke worst-case); ekstra pointere pr. node. ## Hvorfor det betyder noget Skip lists leverer træ-lignende O(log n) ordnede operationer med meget mindre kode og nem lock-free concurrency, hvilket er grunden til, at reelle systemer som Redis vælger dem. De er et glimrende eksempel på brug af **randomisering** til at erstatte kompleks deterministisk balancelogik.