ما هي قائمة التخطي؟

قائمة التخطي هي بنية بيانات احتمالية. تُستخدم قائمة التخطي لتخزين قائمة مرتبة من العناصر أو البيانات مع قائمة مرتبطة. يسمح بعرض العناصر أو البيانات بكفاءة. في خطوة واحدة، يتخطى عدة عناصر من القائمة بأكملها، ولهذا السبب تُعرف باسم قائمة التخطي.

قائمة التخطي هي نسخة موسعة من القائمة المرتبطة. يسمح للمستخدم بالبحث عن العنصر وإزالته وإدراجه بسرعة كبيرة. وتتكون من قائمة أساسية تتضمن مجموعة من العناصر التي تحافظ على التسلسل الهرمي للارتباطات للعناصر اللاحقة.

تخطي هيكل القائمة

وهي مبنية على طبقتين: الطبقة السفلى والطبقة العليا.

الطبقة السفلية من قائمة التخطي هي قائمة مرتبطة مرتبة بشكل شائع، والطبقات العليا من قائمة التخطي تشبه 'الخط السريع' حيث يتم تخطي العناصر.

جدول التعقيد لقائمة التخطي

العمل على قائمة التخطي

لنأخذ مثالاً لفهم طريقة عمل قائمة التخطي. في هذا المثال، لدينا 14 عقدة، بحيث يتم تقسيم هذه العقد إلى طبقتين، كما هو موضح في الرسم البياني.

الطبقة السفلية عبارة عن خط مشترك يربط جميع العقد، والطبقة العليا عبارة عن خط سريع يربط العقد الرئيسية فقط، كما ترون في الرسم التخطيطي.

لنفترض أنك تريد العثور على 47 في هذا المثال. ستبدأ البحث من العقدة الأولى للخط السريع وتستمر في التشغيل على الخط السريع حتى تجد العقدة التي تساوي 47 أو أكثر من 47.

يمكنك أن ترى في المثال أن 47 غير موجود في الخط السريع، فتبحث عن عقدة أقل من 47، وهي 40. والآن تذهب إلى السطر العادي بمساعدة 40، وتبحث عن 47، كما هو موضح في الرسم البياني.

ملاحظة: بمجرد العثور على عقدة مثل هذه على 'الخط السريع'، تنتقل من هذه العقدة إلى 'المسار العادي' باستخدام المؤشر، وعندما تبحث عن العقدة في الخط العادي.

تخطي قائمة العمليات الأساسية

هناك أنواع العمليات التالية في قائمة التخطي.

عملية الإدراج:يتم استخدامه لإضافة عقدة جديدة إلى موقع معين في موقف معين.عملية الحذف:يتم استخدامه لحذف عقدة في موقف معين.عملية البحث:يتم استخدام عملية البحث للبحث عن عقدة معينة في قائمة التخطي.

خوارزمية عملية الإدراج

 Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a 

خوارزمية عملية الحذف

 Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1 

خوارزمية عملية البحث

 Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure 

مثال 1: قم بإنشاء قائمة تخطي، نريد إدراج هذه المفاتيح التالية في قائمة التخطي الفارغة.

1. 6 مع المستوى 1.
2. 29 مع المستوى 1.
3. 22 مع المستوى 4.
4. 9 مع المستوى 3.
5. 17 مع المستوى 1.
6. 4 مع المستوى 2.

أعوام:

الخطوة 1: أدخل 6 مع المستوى 1

الخطوة 2: أدخل 29 مع المستوى 1

الخطوه 3: أدخل 22 مع المستوى 4

الخطوة 4: أدخل 9 مع المستوى 3

الخطوة 5: أدخل 17 بالمستوى 1

الخطوة 6: أدخل 4 مع المستوى 2

مثال 2: خذ بعين الاعتبار هذا المثال حيث نريد البحث عن المفتاح 17.

أعوام:

مزايا قائمة التخطي

1. إذا كنت ترغب في إدراج عقدة جديدة في قائمة التخطي، فسيتم إدراج العقدة بسرعة كبيرة لأنه لا توجد دورات في قائمة التخطي.
2. قائمة التخطي سهلة التنفيذ مقارنة بجدول التجزئة وشجرة البحث الثنائية.
3. من السهل جدًا العثور على عقدة في القائمة لأنها تخزن العقد في شكل مرتبة.
4. يمكن تعديل خوارزمية قائمة التخطي بسهولة شديدة في بنية أكثر تحديدًا، مثل قوائم التخطي القابلة للفهرسة أو الأشجار أو قوائم الانتظار ذات الأولوية.
5. قائمة التخطي هي قائمة قوية وموثوقة.

عيوب قائمة التخطي

1. يتطلب ذاكرة أكبر من الشجرة المتوازنة.
2. البحث العكسي غير مسموح به.
3. تبحث قائمة التخطي في العقدة بشكل أبطأ بكثير من القائمة المرتبطة.

تطبيقات قائمة التخطي

1. يتم استخدامه في التطبيقات الموزعة، ويمثل المؤشرات والنظام في التطبيقات الموزعة.
2. يتم استخدامه لتنفيذ قائمة انتظار متزامنة مرنة ديناميكية مع تنافس قفل منخفض.
3. يتم استخدامه أيضًا مع فئة قالب QMap.
4. يتم استخدام فهرسة قائمة التخطي في تشغيل المشكلات المتوسطة.
5. يتم استخدام قائمة التخطي لنشر ترميز دلتا في بحث Lucene.