skip list کیا ہے اور یہ O(log n) search کو کیسے حاصل کرتا ہے؟

Question

Accepted Answer

ایک **skip list** ایک ترتیب شدہ linked list ہے جو متعدد **"express lane"** levels سے بہتر بنائی گئی ہے۔ اعلیٰ levels بہت سے nodes کو skip کرتے ہیں، اس لیے search descend اور دائیں جانب move کرتے ہوئے **O(log n)** متوقع وقت حاصل کرتا ہے — یہ balanced tree کا ایک احتمالی، سادہ متبادل ہے۔ ## ڈھانچہ ```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) ``` ہر node probability `p` (اکثر 0.5) کے ساتھ اعلیٰ levels پر promote ہوتا ہے، اس لیے اوسطاً ہر level میں اس کے نیچے والے کی نسبت آدھے nodes ہوتے ہیں۔ ## تلاش ```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 ``` ## پیچیدگی | Operation | Expected | Space | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Balanced trees کے ساتھ trade-offs - **طاقتیں:** red-black/AVL سے بہت آسان implement کرنا؛ کوئی rotations نہیں؛ آسان concurrent versions (Redis sorted sets، Java `ConcurrentSkipListMap` میں استعمال)۔ - **کمزوریاں:** احتمالی guarantees (worst-case نہیں)؛ ہر node میں اضافی pointers۔ ## یہ اہم کیوں ہے Skip lists بہت کم code کے ساتھ tree جیسے O(log n) ordered operations فراہم کرتے ہیں اور آسان lock-free concurrency دیتے ہیں، یہی وجہ ہے کہ Redis جیسے حقیقی systems انہیں منتخب کرتے ہیں۔ یہ **randomization** استعمال کرتے ہوئے complex deterministic balancing logic کو replace کرنے کی بہترین مثال ہے۔