قائمة التخطي skip list هي قائمة مرتبطة مرتبة معززة بعدة مستويات "حارات سريعة". تخطي المستويات الأعلى على عدد كبير من العقد، لذا يتم البحث بالنزول والحركة لليمين، محققة وقت متوقع O(log n) — مثل بديل احتمالي وأبسط من الشجرة المتوازنة.
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)، لذا في المتوسط كل مستوى يحتوي على نصف عدد العقد من المستوى أدناه.
search(25): start top-left, move RIGHT while next <= target,
else drop DOWN a level. Repeat to level 0.
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) | — |
ConcurrentSkipListMap في Java).توفر قوائم التخطي عمليات O(log n) مرتبة تشبه الأشجار مع كود أقل بكثير وتزامن خالي من القفل بسهولة، وهذا هو السبب في اختيار الأنظمة الحقيقية مثل Redis لها.
إنها مثال رائع على استخدام العشوائية لاستبدال منطق الموازنة الحتمي المعقد.
مكتبة من أسئلة مقابلات تقنية المعلومات مع إجابات مفصّلة — من المبتدئ إلى المتقدم.
تبرع