Vad är en skip list och hur uppnår den O(log n) sökning?

Question

Accepted Answer

A **skip list** är en ordnad länkad lista utökad med flera **"express lane"** nivåer. Högre nivåer hoppar över många noder, så sökningen descender och rör sig åt höger, vilket uppnår **O(log n)** förväntad tid — som ett probabilistiskt, enklare alternativ till ett balanserat träd. ## 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) ``` Varje nod befordras till högre nivåer med sannolikhet `p` (ofta 0.5), så i genomsnitt har varje nivå hälften så många noder som nivån under. ## Sökning ```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 ``` ## Komplexitet | Operation | Förväntad | Utrymme | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Avvägning mot balanserade träd - **Styrkor:** mycket enklare att implementera än red-black/AVL; inga rotationer; enkla concurrent versioner (används i Redis sorted sets, Java `ConcurrentSkipListMap`). - **Svagheter:** probabilistiska garantier (inte värsta fall); extra pekare per nod. ## Varför det är viktigt Skip lists levererar trädliknande O(log n) ordnade operationer med mycket mindre kod och enkel låsfri concurrency, vilket är varför riktiga system som Redis väljer dem. De är ett utmärkt exempel på att använda **slumpmässighet** för att ersätta komplex deterministisk balanseringslogik.