Skip list ni nini na inapataje O(log n) utafutaji?

Question

Accepted Answer

A **skip list** ni orodha iliyounganisha iliyoamriwa na kuongezwa kwa viwango vingi vya **"express lane"**. Viwango vya juu vinaruka juu ya nodi nyingi, hivyo utafutaji unaposhuka na kusonga kulia, kupata **O(log n)** wakati unaotarajiwa — kama mbadala ya uwezekano, rahisi kuliko mti wenye usawa. ## Muundo ```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) ``` Kila nodi inakuzwa kwa viwango vya juu na uwezekano `p` (mara kwa mara 0.5), kwa hivyo kwa wastani kila kiwango kina nusu ya nodi kuliko kiwango chini yake. ## Utafutaji ```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 ``` ## Ugumu | Operesheni | Inatarajiwa | Nafasi | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Kompromiso dhidi ya miti yenye usawa - **Nguvu:** rahisi sana kutekeleza kuliko red-black/AVL; hakuna mizunguko; matolikali ya utofautiano unaofanya kazi kwa wakati mmoja (inatumiwa katika Redis sorted sets, Java `ConcurrentSkipListMap`). - **Ujinga:** dhamana za uwezekano (si kwa haraka mbaya); viashiria vya ziada kwa nodi. ## Kwa nini inakuwa muhimu Skip lists inatoa operesheni za O(log n) kama mti wenye usawa na neno mfupi zaidi na uhusiano rahisi wa kufa, ambayo ndiyo sababu mifumo halisi kama Redis inayachagua. Zipo mfano mzuri wa kutumia **nasibu** kutofautiana na mantiki ngumu kaburi kwa usawa.