Wat is een skip list en hoe bereikt het O(log n) zoeken?

Question

Accepted Answer

Een **skip list** is een geordende linked list aangevuld met meerdere **"express lane"** niveaus. Hogere niveaus overslaan veel nodes, dus zoeken daalt en beweegt naar rechts, waardoor **O(log n)** verwachte tijd wordt bereikt — zoals een probabilistisch, eenvoudiger alternatief voor een gebalanceerde boom. ## Structuur ```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) ``` Elke node wordt bevorderd tot hogere niveaus met waarschijnlijkheid `p` (vaak 0.5), dus gemiddeld heeft elk niveau half zoveel nodes als het niveau eronder. ## Zoeken ```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 ``` ## Complexiteit | Bewerking | Verwacht | Ruimte | |---|---|---| | zoeken | O(log n) | O(n) | | invoegen / verwijderen | O(log n) | — | ## Afwegingen versus gebalanceerde bomen - **Sterken:** veel eenvoudiger te implementeren dan red-black/AVL; geen rotaties; makkelijke gelijktijdige versies (gebruikt in Redis sorted sets, Java `ConcurrentSkipListMap`). - **Zwakten:** probabilistische garanties (niet worst-case); extra pointers per node. ## Waarom het belangrijk is Skip lists leveren boom-achtige O(log n) geordende bewerkingen met veel minder code en makkelijke lock-free gelijktijdigheid, daarom kiezen systemen als Redis ervoor. Ze zijn een uitstekend voorbeeld van het gebruik van **randomization** om complexe deterministische balanceringslogica te vervangen.