Skip list என்றால் என்ன மற்றும் அது O(log n) தேடலை எப்படி அடையும்?

Question

Accepted Answer

**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 போன்ற உண்மையான அமைப்புகள் அவற்றைத் தேர்ந்தெடுக்கின்றன. அவை **சமூக ஆய்வு** கொண்டு சிக்கலான நிர்ணய சமநிலை தர்க்கத்தை மாற்ற சிறந்த உதாரணமாகும்.