स्किप लिस्ट म्हणजे काय आणि तो O(log n) शोध कसे साध्य करतो?

Question

Accepted Answer

**स्किप लिस्ट** एक क्रमबद्ध लिंक्ड लिस्ट आहे जी अनेक **"एक्सप्रेस लेन"** स्तरांनी वाढविली जाते. उच्च स्तर अनेक नोड्स को वगळून जातात, म्हणून शोध खाली उतरतो आणि उजवीकडे हलतो, **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` मध्ये वापरली). - **कमजोरी:** संभाव्य हमी (सर्वात वाईट केस नाही); प्रत्येक नोडसाठी अतिरिक्त पॉइंटर्स. ## हे महत्वाचे का आहे स्किप लिस्ट्स खूप कमी कोड आणि सहज lock-free समवर्तितेसह ट्रीसारखे O(log n) क्रमबद्ध ऑपरेशन प्रदान करते, म्हणून Redis सारख्या वास्तविक प्रणाली त्यांना निवडतात. हे जटिल निर्धारणीय संतुलन तर्क बदलण्यासाठी **यादृच्छिकता** वापरण्याचे एक उत्तम उदाहरण आहे.