Kaj je skip list in kako doseže O(log n) iskanje?

Question

Accepted Answer

A **skip list** je urejena povezana lista, ki je razširjena z več **"express lane"** nivojem. Višji nivoji preskočijo številne vozlišča, zato iskanje pada in se premika desno, dosega **O(log n)** pričakovan čas — kot verjetnostna, enostavnejša alternativa uravnoteženemu drevesu. ## Struktura ```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) ``` Vsako vozlišče je promovano na višje nivoje z verjetnostjo `p` (pogosto 0.5), zato na povprečje ima vsak nivo polovico manj vozlišč kot nivo pod njim. ## Iskanje ```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 ``` ## Zahtevnost | Operacija | Pričakovan | Prostor | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Primerjava z uravnoteženimi drevesi - **Prednosti:** veliko enostavnejše za implementacijo kot red-black/AVL; brez rotacij; lahka hkratna različica (uporabljena v Redis sorted sets, Java `ConcurrentSkipListMap`). - **Slabosti:** verjetnostne garancije (ne najslabši primer); dodatni kazalci na vozlišče. ## Zakaj je pomembno Skip liste zagotavljajo operacije, kot sta dreveso, O(log n) z urejenimi podatki in daleč manj kode ter preprostim brez-zaklepanja hkratnostjo, zato realni sistemi, kot je Redis, izberejo to. So odličen primer uporabe **naključnosti** za zamenjavo kompleksne determinističke logike uravnoteževanja.