Skip list అంటే ఏమిటి మరియు ఇది O(log n) శోధనను ఎలా సాధిస్తుంది?

Question

Accepted Answer

A **skip list** అనేది బహుళ **"express lane"** స్థాయిలతో విస్తૃతమైన ఆర్డర్‌ చేసిన లింక్ చేసిన జాబితా. ఉన్నత స్థాయిలు అనేక నోడ్‌లను దాటవేస్తాయి, కాబట్టి శోధన పడిపోతుంది మరియు కుడికి కదులుతుంది, **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) | — | ## సమతుల్య చెట్ల సంధానం - **బలాలు:** red-black/AVL కంటే వాస్తవం చేయడానికి చాలా సరళమైనది; భ్రమణాలు లేవు; సులభమైన సమకాలీన సంస్కరణలు (Redis ఆర్డర్‌ చేసిన సెట్‌లలో, Java `ConcurrentSkipListMap` ఉపయోగించబడుతుంది). - **బలహీనతలు:** సంభావ్య గ్యారంటీలు (చెత్త కేసు కాదు); ప్రతి నోడ్‌కు అదనపు చర్చలు. ## ఇది ఎందుకు ముఖ్యమైనది Skip lists చెట్ట-లాంటి O(log n) ఆర్డర్‌ చేసిన ఆపరేషన్‌లను చాలా తక్కువ కోడ్ మరియు సులభమైన లాక్-ఫ్రీ సమకాలీనతతో సరఫరా చేస్తాయి, అందుకే Redis వంటి నిజమైన సిస్టమ్‌లు వాటిని ఎంచుకుంటాయి. వे సంక్లిష్ట నిర్ణయాత్మక సమతుల్య తర్కాన్ని భర్తీ చేయడానికి **యాదృచ్చికత**ను ఉపయోగించే సుందర ఉదాహరణ.