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) | — | ## संतुलित पेड़ों के विरुद्ध ट्रेड-ऑफ - **ताकत:** red-black/AVL की तुलना में कार्यान्वयन के लिए बहुत आसान; कोई घुमाव नहीं; आसान सहवर्ती संस्करण (Redis sorted sets में, Java `ConcurrentSkipListMap` में उपयोग किए जाते हैं)। - **कमजोरियां:** संभाव्य गारंटी (सबसे खराब मामले में नहीं); नोड प्रति अतिरिक्त सूचक। ## यह क्यों मायने रखता है Skip lists पेड़ जैसे O(log n) क्रमबद्ध संचालन प्रदान करते हैं कहीं कम कोड के साथ और आसान लॉक-मुक्त समवर्तिता, यही कारण है कि Redis जैसी वास्तविक प्रणालियां उन्हें चुनती हैं। वे **यादृच्छिकता** का उपयोग करके जटिल निर्धारक संतुलन तर्क को बदलने का एक शानदार उदाहरण हैं।