Što je skip lista i kako postiže O(log n) pretraživanje?

Question

Accepted Answer

**Skip lista** je uređena povezana lista pojačana s više **"brze vozne trake"** razine. Više razine preskakuju preko mnogih čvorova, tako da pretraživanje silazi i ide desno, postižući **O(log n)** očekivano vrijeme — probabilistička, jednostavnija alternativa uravnoteženom stablu. ## 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) ``` Svaki čvor je promocijom na više razine s vjerovatnoćom `p` (često 0.5), tako da u prosjeku svaka razina ima upola manje čvorova od one ispod. ## Pretraživanje ```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 ``` ## Složenost | Operacija | Očekivano | Prostor | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Kompromisi u odnosu na uravnotežena stabla - **Prednosti:** mnogo lakše za implementaciju od red-black/AVL; bez rotacija; laka konkurentna verzija (korištena u Redis sorted setovima, Java `ConcurrentSkipListMap`). - **Nedostaci:** probabilističke garantije (ne najgori slučaj); dodatni pokazivači po čvoru. ## Zašto je važno Skip liste pružaju operacije slične stablu O(log n) s puno manje koda i laganom konkurencijom bez zaključavanja, što je razlog zašto sistemi poput Redisa biraju njih. Oni su odličan primjer korištenja **randomizacije** za zamjenu kompleksne determinističke logike uravnoteživanja.