Hva er en skip list og hvordan oppnår den O(log n) søk?

Question

Accepted Answer

En **skip list** er en ordnet lenket liste utvidet med flere **"express lane"** nivåer. Høyere nivåer hopper over mange noder, så søk stiger og beveger seg til høyre, og oppnår **O(log n)** forventet tid — som et sannsynlighetsbasert, enklere alternativ til et balansert tre. ## 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 fremmes til høyere nivåer med sannsynlighet `p` (ofte 0.5), så i gjennomsnitt har hvert nivå halvparten så mange noder som det under. ## Søk ```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 | Operasjon | Forventet | Plass | |---|---|---| | søk | O(log n) | O(n) | | sett inn / slett | O(log n) | — | ## Avveiinger versus balanserte trær - **Styrker:** mye enklere å implementere enn red-black/AVL; ingen rotasjoner; enkle samtidige versjoner (brukt i Redis sorterte sett, Java `ConcurrentSkipListMap`). - **Svakheter:** sannsynliggjørende garantier (ikke verste tilfelle); ekstra pekere per node. ## Hvorfor det betyr noe Skip lists leverer tre-lignende O(log n) ordnede operasjoner med langt mindre kode og enkel lock-free samtidighet, noe som er grunnen til at systemer som Redis velger dem. De er et flott eksempel på bruk av **randomization** til å erstatte kompleks deterministisk balanseringslogikk.