স্কিপ লিস্ট কী এবং এটি কীভাবে 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` এ ব্যবহৃত)। - **দুর্বলতা:** সম্ভাব্যমূলক নিশ্চয়তা (সর্বোচ্চ-কেসের নয়); প্রতি নোডে অতিরিক্ত পয়েন্টার। ## কেন এটি গুরুত্বপূর্ণ স্কিপ লিস্টগুলি গাছ-সদৃশ O(log n) ক্রমবর্ধমান অপারেশন প্রদান করে অনেক কম কোড এবং সহজ লক-মুক্ত সমসাময়িকতার সাথে, যা কেন Redis-এর মতো বাস্তব সিস্টেমগুলি তাদের বেছে নেয়। তারা জটিল নির্ধারণমূলক ভারসাম্য যুক্তির প্রতিস্থাপন করতে **র্যান্ডমাইজেশন** ব্যবহার করার একটি দুর্দান্ত উদাহরণ।