X'inhu skip list u kif jilħaq l-istħarriġ O(log n)?

Question

Accepted Answer

**Skip list** huwa lista mqabbda mfassla li thaħħen b'multipli livelli ta' **"tunelliet tat-tfakka"**. Livelli ogħla jaqfdu fuq ħafna nodi, għalhekk it-tfittxija tinżel u timxi fuq il-lemin, tilħaq ħin aspettat ta' **O(log n)** — din hija alternattiva probabilistika aktar sempliċi għal siġra mibalanċata. ## 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) ``` Kull nodu titħaffef għal livelli ogħla b'probabbiltà `p` (ħafna drabi 0.5), għalhekk medja kull livell għandu nofs inħamm il-nodi minn dawk taħt. ## Tfittxija ```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 ``` ## Ikkomplessità | Operazzjoni | Aspettata | Ispazju | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Trade-offs vs siġar mibalanċati - **Qawwiet:** ħafna aktar sempliċi biex titwettaq milli red-black/AVL; l-ebda rotazzjonijiet; verżjonijiet konkorenti faċli (użati f'Redis sorted sets, Java `ConcurrentSkipListMap`). - **Dgħajjef:** garanziji probabilistiċi (mhux agħar każ); puntier żidew għal kull nodu. ## Għaliex dan hu importanti Skip lists jipprovdu operazzjonijiet mfassla bħall-siġar O(log n) b'ħafna inqas kodiċi u konkurenza lock-free faċli, għaliex sistemi reali bħal Redis jagħżluhom. Dan huwa eżempju eċċellenti tal-użu ta' **ċ-ċaż** biex tissostitwixxi loġika kumplessa deterministika ta' bilanċ.