Skip list શું છે અને તે O(log n) શોધ કેવી રીતે પ્રાપ્ત કરે છે?

Question

Accepted Answer

એક **skip list** એક ક્રમાંકિત લિંક્ડ લિસ્ટ છે જે બહુવિધ **"એક્સપ્રેસ લેન"** સ્તરો સાથે વધારી છે. ઉચ્ચ સ્તરો ઘણા નોડ્સ પર જાય છે, તેથી શોધ નીચે ઉતરે છે અને જમણી તરફ ફરે છે, **O(log n)** અપેક્ષિત સમય પ્રાપ્ત કરે છે — સંતુલિત ટ્રી માટે સંભાવનાશીલ, સરળ વિકલ્પ. ## બંધારણ ```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) ``` પ્રત્યેક નોડ સંભાવના `p` (ઘણીવાર 0.5) સાથે ઉચ્ચ સ્તર પર બढ્ઢો પામે છે, તેથી સરેરાશ પ્રત્યેક સ્તર નીચે એકમાંથી અડધા નોડ્સ ધરાવે છે. ## શોધ ```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 ``` ## જટિલતા | ક્રિયા | અપેક્ષિત | જગ્યા | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## સંતુલિત વૃક્ષ વિરુદ્ધ ટ્રેડ-અપ - **શક્તિઓ:** લાલ-કાળો/AVL કરતા અમલમાં મૂકવું ઘણું સરળ; કોઈ પરિભ્રમણ નથી; સરળ સમવર્તી સંસ્કરણો (Redis સૉર્ટેડ સેટમાં, Java `ConcurrentSkipListMap`માં વપરાય છે). - **નબળાઈઓ:** સંભાવનાશીલ ગ્યારંટીઓ (સૌથી ખરાબ કેસ નથી); નોડ દીઠ વધારાના પોઇન્ટર. ## શા માટે તે મહત્વનું છે Skip lists વૃક્ષ જેવી O(log n) ક્રમાંકિત કામગીરી ઘણા ઓછા કોડ અને સરળ તાળો-મુક્ત સમવર્તન સાથે પ્રદાન કરે છે, તેથી Redis જેવી વાસ્તવિક સિસ્ટમો તેમને પસંદ કરે છે. તેઓ જટિલ નિર્ણયાત્મક સંતુલનશીલતા તર્કને બદલવા માટે **રેન્ડમાઇઝેશન** ઉપયોગ કરવાનું એક શ્રેષ્ઠ ઉદાહરણ છે.