Kas yra skip list ir kaip ji pasiekia O(log n) paiešką?

Question

Accepted Answer

**Skip list** yra sutvarkyta susieta sąrašą, papildyta keliais **"greitųjų juostų"** lygiais. Aukštesni lygiai peršoka per daug mazgų, todėl paieška leidžiasi ir juda į dešinę, pasiekdama **O(log n)** tikėtiną laiką — tai yra tikimybinis, paprastesnis balansuoto medžio alternatyva. ## Struktūra ```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) ``` Kiekvienas mazgas yra paaukštinamas į aukštesnius lygius su tikimybe `p` (dažnai 0.5), todėl vidutiniškai kiekvienas lygis turi perpus mažiau mazgų nei žemiau esantis. ## Paieška ```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 ``` ## Sudėtingumas | Operacija | Tikėtina | Vieta | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Kompromisai prieš subalansuotus medžius - **Stiprybės:** daug paprastesnis diegti nei red-black/AVL; nereikalingos rotacijos; lengva sukurti lygiagrečias versijas (naudojama Redis rūšiuotuose rinkinėse, Java `ConcurrentSkipListMap`). - **Silpnybės:** tikimybinės garantijos (ne blogiausiu atveju); papildomi rodyklės kiekvienam mazgui. ## Kodėl tai svarbu Skip list suteikia medžio panašias O(log n) tvarkytų operacijų su daug mažiau kodo ir lengva lock-free lygiagretybe, todėl realios sistemos, tokios kaip Redis, jas pasirenka. Tai puikus pavyzdys naudojant **atsitiktinumą** sudėtingai deterministinei balansuojamo kodo logikai pakeisti.