Co je skip list a jak dosahuje O(log n) vyhledávání?

Question

Accepted Answer

**Skip list** je uspořádaný linked list rozšířený o více úrovní **"expresních jízdních pruhů"**. Vyšší úrovně přeskakují mnoho uzlů, takže vyhledávání klesá a pohybuje se doprava, čímž dosahuje **O(log n)** očekávaného času — jako pravděpodobnostní, jednodušší alternativa k vyvažovanému stromu. ## 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) ``` Každý uzel je povýšen na vyšší úrovně s pravděpodobností `p` (často 0,5), takže v průměru má každá úroveň polovinu uzlů jako ta pod ní. ## Vyhledávání ```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žitost | Operace | Očekávaná | Prostor | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Kompromisy vs vyvažované stromy - **Silné stránky:** mnohem jednodušší implementace než red-black/AVL; bez rotací; snadné souběžné verze (používané v Redis sorted sets, Java `ConcurrentSkipListMap`). - **Slabé stránky:** pravděpodobnostní záruky (ne nejhorší případ); extra ukazatele na uzel. ## Proč na tom záleží Skip listy poskytují operace O(log n) podobné stromu s mnohem menším kódem a snadnou lock-free souběžností, což je důvod, proč si je volí skutečné systémy jako Redis. Jsou skvělým příkladem použití **randomizace** k nahrazení složité deterministické logiky vyvažování.