Mi az a skip lista, és hogyan éri el az O(log n) keresést?

Question

Accepted Answer

A **skip lista** egy rendezett linkelt lista, amely több **"expressz sáv"** szinttel van kiegészítve. A magasabb szintek sok csomópontot átugranak, így a keresés lefelé megy és jobbra halad, **O(log n)** várható időt érve el — egy valószínűségi, egyszerűbb alternatíva egy kiegyensúlyozott fához. ## Szerkezet ```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) ``` Minden csomópontot `p` valószínűséggel (gyakran 0.5) magasabb szintre lenni promoveálnak, így átlagosan minden szintnek fele annyi csomópontja van, mint az alatta lévőnek. ## Keresés ```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 ``` ## Összetettség | Művelet | Várható | Hely | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Kiegyensúlyozott fákkal szembeni kompromisszumok - **Erősségek:** sokkal egyszerűbb megvalósítani, mint a red-black/AVL; nincs forgatás; könnyű párhuzamos verzió (a Redis rendezett halmazaiban, a Java `ConcurrentSkipListMap`-ban használatos). - **Gyengeségek:** valószínűségi garantálások (nem legrosszabb eset); extra mutatók csomópontonként. ## Miért is fontos A skip listák fához hasonló O(log n) rendezett műveleteket nyújtanak sokkal kevesebb kóddal és könnyű zárolás nélküli párhuzamossággal, és ezért a Redis-hez hasonló valós rendszerek választják őket. Ezek kiváló példája annak, hogy a **randomizációt** használjuk az összetett determinisztikus kiegyensúlyozási logika helyettesítésére.