Che cos'è una skip list e come raggiunge la ricerca O(log n)?

Question

Accepted Answer

Una **skip list** è una linked list ordinata aumentata con più livelli di **"corsie veloci"**. I livelli superiori saltano molti nodi, quindi la ricerca scende e si muove a destra, raggiungendo un tempo atteso di **O(log n)** — un'alternativa probabilistica e più semplice a un albero bilanciato. ## Struttura ```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) ``` Ogni nodo è promosso ai livelli superiori con probabilità `p` (spesso 0.5), quindi in media ogni livello ha metà dei nodi rispetto a quello sottostante. ## Ricerca ```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 ``` ## Complessità | Operazione | Atteso | Spazio | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Trade-off rispetto agli alberi bilanciati - **Vantaggi:** molto più semplice da implementare di red-black/AVL; senza rotazioni; versioni concorrenti facili (utilizzate in Redis sorted sets, Java `ConcurrentSkipListMap`). - **Svantaggi:** garanzie probabilistiche (non caso peggiore); puntatori extra per nodo. ## Perché è importante Le skip list offrono operazioni ordinate O(log n) simili agli alberi con molto meno codice e concorrenza lock-free facile, per questo sistemi reali come Redis le scelgono. Sono un ottimo esempio di utilizzo della **casualità** per sostituire la complessa logica deterministica di bilanciamento.