ما هي قائمة التخطي (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 المرتبة، `ConcurrentSkipListMap` في Java). - **العيوب:** ضمانات احتمالية (ليست الحالة الأسوأ)؛ مؤشرات إضافية لكل عقدة. ## لماذا يهم توفر قوائم التخطي عمليات O(log n) مرتبة تشبه الأشجار مع كود أقل بكثير وتزامن خالي من القفل بسهولة، وهذا هو السبب في اختيار الأنظمة الحقيقية مثل Redis لها. إنها مثال رائع على استخدام **العشوائية** لاستبدال منطق الموازنة الحتمي المعقد.