ملخص شامل لهياكل البيانات

تعقيد الخوارزميات وتدوين Big-O

التعريف: تدوين Big-O يصف أسوأ حالة لتعقيد الوقت لخوارزمية مع نمو حجم المدخلات. يعطي حداً أعلى لمعدل النمو.

نقاط رئيسية:

  • O(1) - وقت ثابت: العملية لا تعتمد على حجم المدخلات
  • O(log n) - لوغاريتمي: يقسم المشكلة للنصف كل خطوة (بحث ثنائي)
  • O(n) - خطي: يعالج كل عنصر مرة واحدة
  • O(n log n) - خطي لوغاريتمي: خوارزميات ترتيب فعالة
  • O(n²) - تربيعي: حلقات متداخلة على المدخلات
  • O(2ⁿ) - أسي: يتضاعف مع كل إضافة للمدخلات
مستخرج من امتحان سابق

مثال: حلل تعقيد الكود

int a = 0; 
for (i = 0; i < n; i++) { 
    for (j = 0; j < n; j++) { 
        a = a + i + j; 
    } 
}

الحل:

الخطوة 1: حدد الحلقات - الحلقة الخارجية تعمل n مرة
الخطوة 2: الحلقة الداخلية تعمل n مرة لكل تكرار خارجي
الخطوة 3: إجمالي العمليات: n × n = n²
الإجابة: O(n²)
العملية المصفوفة القائمة المرتبطة جدول التجزئة شجرة بحث ثنائية (متوازنة)
وصول/بحث O(1) / O(n) O(n) O(1) متوسط O(log n)
إدراج O(n) O(1) في الرأس O(1) متوسط O(log n)
حذف O(n) O(n) O(1) متوسط O(log n)

القوائم المرتبطة

التعريف: هيكل بيانات خطي حيث يتم تخزين العناصر في عقد، كل عقدة تحتوي على بيانات ومرجع للعقدة التالية.

نقاط رئيسية:

  • قائمة مرتبطة أحادية: كل عقدة تشير للعقدة التالية فقط
  • قائمة مرتبطة ثنائية: كل عقدة لها مراجع للعقدة التالية والسابقة
  • قائمة مرتبطة دائرية: العقدة الأخيرة تشير للعقدة الأولى
  • حجم ديناميكي - يمكن أن ينمو/ينكمش أثناء التنفيذ
  • إدراج/حذف فعال في أي موقع (O(1) إذا عُرف الموقع)
  • لا يوجد وصول عشوائي - يجب الاجتياز من الرأس (O(n))
  • حمل ذاكرة إضافي لتخزين المؤشرات
مستخرج من امتحان سابق

مثال: إدراج في قائمة مرتبة

void insertSorted(int X) {
    // أدخل X في قائمة مرتبطة مرتبة
}

الحل:

الخطوة 1: أنشئ عقدة جديدة بالقيمة X
الخطوة 2: إذا كانت القائمة فارغة أو X < head.value، أدخل في البداية
الخطوة 3: وإلا، اجتيز للعثور على موقع حيث current.value < X < current.next.value
الخطوة 4: أدخل العقدة الجديدة في الموقع الموجود
تعقيد الوقت: O(n) أسوأ حالة
مثال مولد

مثال: اعكس قائمة مرتبطة

القائمة المعطاة: 1 -> 2 -> 3 -> 4 -> null
اعكسها إلى: 4 -> 3 -> 2 -> 1 -> null

الحل:

الخطوة 1: ابدأ بثلاث مؤشرات: prev = null, current = head, next = null
الخطوة 2: بينما current ليست null:
  - خزن next = current.next
  - اعكس الرابط: current.next = prev
  - حرك المؤشرات: prev = current, current = next
الخطوة 3: أرجع prev كرأس جديد
تعقيد الوقت: O(n), المساحة: O(1)

المكدسات

التعريف: هيكل بيانات يعمل بمبدأ (LIFO) حيث تضاف العناصر وتزال من نفس النهاية (الأعلى).

نقاط رئيسية:

  • دفع: أضف عنصراً للأعلى - O(1)
  • سحب: احذف عنصراً من الأعلى - O(1)
  • نظرة/أعلى: اعرض العنصر الأعلى دون حذفه - O(1)
  • التطبيقات: مكدس استدعاء الدوال، عمليات التراجع، تقييم العبارات، التتبع الرجوعي
  • يمكن تنفيذها باستخدام مصفوفات أو قوائم مرتبطة
  • تنفيذ المصفوفة: حجم ثابت لكن صديق للذاكرة المخبأة
  • تنفيذ القائمة المرتبطة: حجم ديناميكي لكن حمل مؤشرات إضافي
مستخرج من امتحان سابق

مثال: استخدام مكدس لطباعة الأسماء بترتيب عكسي

المشكلة: اقرأ قائمة من الأسماء واطبعها بالترتيب المعاكس.

الحل:

الخطوة 1: أنشئ مكدساً فارغاً
الخطوة 2: ادفع كل اسم للمكدس أثناء قراءته
الخطوة 3: اسحب واطبع كل اسم من المكدس حتى يفرغ
لماذا يعمل: خاصية LIFO للمكدس تضمن طباعة آخر اسم أدخل أولاً
مثال مولد

مثال: موازنة الأقواس

افحص إذا كانت الأقواس متوازنة: "((a+b)*(c-d))"

الحل:

الخطوة 1: ابدأ بمكدس فارغ
الخطوة 2: لكل حرف:
  - إذا كان '(', ادفع للمكدس
  - إذا كان ')', اسحب من المكدس (إذا كان فارغاً، أرجع خطأ)
الخطوة 3: بعد المعالجة، يجب أن يكون المكدس فارغاً
النتيجة: السلسلة المعطاة متوازنة ✓

الطوابير

التعريف: هيكل بيانات يعمل بمبدأ (FIFO) حيث تضاف العناصر في المؤخرة وتزال من المقدمة.

نقاط رئيسية:

  • إضافة للطابور: أضف عنصراً للمؤخرة - O(1)
  • إزالة من الطابور: احذف عنصراً من المقدمة - O(1)
  • مقدمة: اعرض العنصر الأمامي دون حذفه - O(1)
  • طابور دائري: تنفيذ فعال للمصفوفة باستخدام حساب المعيار
  • التطبيقات: جدولة العمليات، BFS، طوابير الطابعات، مخازن الرسائل
  • حالة الفيض في الطابور الدائري: (rear + 1) % size == front
  • حالة الفراغ: front == -1 أو front == rear (بعد الإزالة)
مستخرج من امتحان سابق

مثال: اعكس طابوراً باستخدام مكدس

الطابور: [1, 2, 3, 4, 5] -> اعكس إلى: [5, 4, 3, 2, 1]

الحل:

الخطوة 1: أنشئ مكدساً فارغاً
الخطوة 2: بينما الطابور غير فارغ:
  stack.push(queue.dequeue())
الخطوة 3: بينما المكدس غير فارغ:
  queue.enqueue(stack.pop())
النتيجة: الطابور معكوس الآن

العودية

التعريف: تقنية برمجة حيث تستدعي الدالة نفسها لحل نسخ أصغر من نفس المشكلة.

نقاط رئيسية:

  • الحالة الأساسية: شرط لإيقاف العودية (يمنع الاستدعاءات اللانهائية)
  • الحالة العودية: الدالة تستدعي نفسها بمعاملات معدلة
  • كل استدعاء يضيف إطاراً لمكدس الاستدعاء
  • قد يؤدي لفيض المكدس إذا كان عميقاً جداً
  • غالباً أنظف ولكن قد يكون أقل كفاءة من التكرار
  • أنماط شائعة: فرق تسد، اجتياز الأشجار/الرسوم البيانية، التتبع الرجوعي
  • تحليل تعقيد الوقت: استخدام علاقات التكرار
مستخرج من امتحان سابق

مثال: حلل دالة عودية

function(int n) { 
    if (n==1) 
        return 0; 
    else
        return 1 + function(n-1); 
}

الحل:

الخطوة 1: حدد الحالة الأساسية: n==1, ترجع 0
الخطوة 2: الحالة العودية: تستدعي function(n-1)
الخطوة 3: عدد الاستدعاءات: n-1 استدعاء عودي
الخطوة 4: تعقيد الوقت: O(n)
هدف الدالة: ترجع n-1

الأشجار والأشجار الثنائية

التعريف: هيكل بيانات هرمي مع عقد متصلة بحواف، حيث لكل عقدة أب واحد على الأكثر وأي عدد من الأبناء.

نقاط رئيسية:

  • الجذر: العقدة العلوية بدون أب
  • الورقة: عقدة بدون أبناء
  • الارتفاع: أطول مسار من الجذر للورقة
  • العمق: طول المسار من الجذر للعقدة
  • شجرة ثنائية: كل عقدة لها ابنان على الأكثر
  • شجرة ثنائية كاملة: كل المستويات مملوءة ما عدا الأخير ربما
  • تمثيل المصفوفة: العقدة عند الفهرس i لها:
      - الابن الأيسر عند 2i+1
      - الابن الأيمن عند 2i+2
      - الأب عند ⌊(i-1)/2⌋
  • الحد الأدنى للارتفاع: ⌈log₂(n+1)⌉ - 1, الحد الأقصى للارتفاع: n-1

اجتياز الأشجار

الاجتياز الترتيب حالة الاستخدام
ما قبل الترتيب جذر → يسار → يمين نسخ الشجرة، التعبير البادئ
بالترتيب يسار → جذر → يمين تسلسل مرتب في أشجار البحث الثنائية
ما بعد الترتيب يسار → يمين → جذر حذف الشجرة، التعبير اللاحق
بالمستوى مستوى تلو مستوى (BFS) بحث بالعرض أولاً
مستخرج من امتحان سابق

مثال: افحص إذا كانت الشجرة الثنائية كاملة

boolean isComplete(Node root, int index, int number_nodes) {
    if (root == null) return true;
    if (index >= number_nodes) return false;
    return isComplete(root.left, 2*index+1, number_nodes)
        && isComplete(root.right, 2*index+2, number_nodes);
}

الحل:

الخطوة 1: الدالة تفحص إذا كانت الشجرة ثنائية كاملة
الخطوة 2: تستخدم خاصية فهرسة المصفوفة
الخطوة 3: إذا كان فهرس أي عقدة ≥ إجمالي العقد، الشجرة ليست كاملة
الخطوة 4: تفحص جميع العقد بشكل عودي

أشجار البحث الثنائية (BST)

التعريف: شجرة ثنائية حيث لكل عقدة، جميع القيم في الشجرة الفرعية اليسرى أصغر وجميع القيم في الشجرة الفرعية اليمنى أكبر.

نقاط رئيسية:

  • بحث: O(h) حيث h هو الارتفاع - O(log n) متوازنة، O(n) منحرفة
  • إدراج: O(h) - دائماً أدخل كورقة
  • حذف: O(h) - ثلاث حالات:
      1. عقدة ورقية: احذف ببساطة
      2. طفل واحد: استبدل بالطفل
      3. طفلان: استبدل بالخليفة أو السلف بالترتيب
  • الاجتياز بالترتيب: يعطي تسلسلاً مرتباً
  • القيمة الدنيا: العقدة أقصى اليسار
  • القيمة العليا: العقدة أقصى اليمين
  • يمكن أن تصبح منحرفة (غير متوازنة) مؤدية لعمليات O(n)
مستخرج من امتحان سابق

مثال: احذف عقدة لها طفلان

احذف العقدة 60 من شجرة بحث ثنائية
الشجرة الأصلية بها 60 مع ابن أيسر 40 وابن أيمن 80

الحل:

الخطوة 1: العقدة لها طفلان - استخدم طريقة الخليفة بالترتيب
الخطوة 2: ابحث عن الحد الأدنى في الشجرة الفرعية اليمنى (أقصى اليسار من شجرة 80 الفرعية)
الخطوة 3: استبدل قيمة 60 بقيمة الخليفة
الخطوة 4: احذف عقدة الخليفة (لها طفل واحد على الأكثر)

أشجار AVL

التعريف: شجرة بحث ثنائية ذاتية التوازن حيث يكون فرق الارتفاع بين الأشجار الفرعية اليسرى واليمنى على الأكثر 1 لكل عقدة.

نقاط رئيسية:

  • عامل التوازن: ارتفاع(اليسار) - ارتفاع(اليمين) ∈ {-1, 0, 1}
  • الارتفاع: دائماً O(log n)
  • العمليات: جميعها O(log n) مضمونة
  • الدورانات: تستخدم للحفاظ على التوازن
      - دوران يمين مفرد (حالة LL)
      - دوران يسار مفرد (حالة RR)
      - يسار-يمين (حالة LR)
      - يمين-يسار (حالة RL)
  • إدراج: O(log n) - قد يتطلب دوراناً واحداً
  • حذف: O(log n) - قد يتطلب دورانات متعددة
  • أكثر توازناً من شجرة البحث الثنائية العادية لكن أكثر تعقيداً
مستخرج من امتحان سابق

مثال: تكلفة الدوران في شجرة AVL

ما هي تكلفة وقت التشغيل لدوران مزدوج في شجرة AVL؟

الحل:

الخطوة 1: الدوران المزدوج = دورانان مفردان
الخطوة 2: كل دوران يتضمن تحديثات مؤشرات ثابتة
الخطوة 3: لا حاجة للاجتياز، فقط تغييرات محلية
الإجابة: O(1)

الأكوام وطوابير الأولوية

التعريف: شجرة ثنائية كاملة تحقق خاصية الكوم - الأب أكبر (كوم عظمى) أو أصغر (كوم صغرى) من الأبناء.

نقاط رئيسية:

  • شجرة ثنائية كاملة: جميع المستويات مملوءة ما عدا الأخير ربما
  • تنفيذ المصفوفة: فعال، لا حاجة لمؤشرات
  • إدراج: O(log n) - أضف في النهاية، صاعد للأعلى
  • استخراج الأعلى/الأدنى: O(log n) - استبدل الجذر بالأخير، هابط للأسفل
  • احصل على الأعلى/الأدنى: O(1) - أرجع الجذر فقط
  • بناء الكوم: O(n) باستخدام النهج من الأسفل للأعلى
  • فرز الكوم: O(n log n) وقت، O(1) مساحة
  • التطبيقات: طوابير الأولوية، خوارزمية ديكسترا، الجدولة
مستخرج من امتحان سابق

مثال: طابور أولوية لحالات الطوارئ بالمستشفى

رتب المرضى حسب شدة الإصابة باستخدام هيكل البيانات المناسب.

الحل:

الخطوة 1: استخدم طابور أولوية قائم على كوم عظمى
الخطوة 2: الأولوية = درجة الشدة
الخطوة 3: أدخل المريض: O(log n)
الخطوة 4: احصل على الأكثر شدة: O(1)
الخطوة 5: احذف بعد العلاج: O(log n)
مثال مولد

مثال: أدخل 15 في كوم عظمى

مصفوفة الكوم: [20, 18, 10, 12, 9, 8, 3]

الحل:

الخطوة 1: أضف 15 في النهاية: [20, 18, 10, 12, 9, 8, 3, 15]
الخطوة 2: ابحث عن الأب: أب الفهرس 7 = (7-1)/2 = 3 (القيمة 12)
الخطوة 3: 15 > 12، بدل: [20, 18, 10, 15, 9, 8, 3, 12]
الخطوة 4: افحص الأب الجديد: أب الفهرس 3 = 1 (القيمة 18)
الخطوة 5: 15 < 18، توقف. النتيجة: [20, 18, 10, 15, 9, 8, 3, 12]

خوارزميات الترتيب

التعريف: خوارزميات ترتب العناصر بترتيب معين (تصاعدي/تنازلي).

الخوارزمية أفضل متوسط أسوأ مساحة ثابت الميزة الرئيسية
فرز الاختيار O(n²) O(n²) O(n²) O(1) لا n-1 مبادلة دائماً
فرز الإدراج O(n) O(n²) O(n²) O(1) نعم الأفضل للبيانات شبه المرتبة
الفرز الدمجي O(n log n) O(n log n) O(n log n) O(n) نعم فرق تسد
الفرز السريع O(n log n) O(n log n) O(n²) O(log n) لا أسرع في الحالة المتوسطة
فرز الكوم O(n log n) O(n log n) O(n log n) O(1) لا في المكان، ثابت
مستخرج من امتحان سابق

مثال: أفضل خوارزمية للبيانات المرتبة

بإعطاء مصفوفة مرتبة {2, 3, 5, 6, 9, 11, 15}، أي خوارزمية تأخذ O(n) مقارنات؟

الحل:

الخطوة 1: حلل كل خوارزمية على مدخلات مرتبة
الخطوة 2: فرز الإدراج: كل عنصر يُقارن مرة مع السابق
الخطوة 3: فرز الاختيار: لا يزال O(n²) مقارنات
الخطوة 4: الفرز الدمجي/الكوم: لا يزال O(n log n)
الإجابة: فرز الإدراج - O(n) على بيانات مرتبة
مثال مولد

مثال: تقسيم الفرز السريع

المصفوفة: [5, 2, 8, 3, 9, 1, 7] - المحور = 5

الحل:

الخطوة 1: ابدأ بـ i = -1, j = 0
الخطوة 2: قارن كل عنصر مع المحور (5):
  2 < 5: بدل مع الموضع 0
  3 < 5: بدل مع الموضع 1
  1 < 5: بدل مع الموضع 2
الخطوة 3: ضع المحور في الموضع الصحيح
النتيجة: [2, 3, 1, 5, 9, 8, 7]

الجداول التجزئة

التعريف: هيكل بيانات يعين المفاتيح للقيم باستخدام دالة تجزئة للوصول السريع.

نقاط رئيسية:

  • دالة التجزئة: تعين المفتاح لفهرس المصفوفة (h(k) = k mod حجم)
  • التصادم: عندما ينتج مفتاحان نفس الفهرس
  • عامل الحمل: n/m (العناصر/حجم الجدول) - يؤثر على الأداء
  • الحالة المتوسطة: O(1) للإدراج، الحذف، البحث
  • أسوأ حالة: O(n) عندما تنتج جميع المفاتيح نفس الفهرس

حل التصادم

الطريقة الوصف الإيجابيات السلبيات
التسلسل قائمة مرتبطة في كل فهرس بسيط، يتعامل مع حمل عال ذاكرة إضافية للمؤشرات
الفحص الخطي افحص الخانة التالية: (h+i) mod m صديق للذاكرة المخبأة مشكلة التكتل
الفحص التربيعي افحص: (h+i²) mod m يقلل التكتل قد لا يفحص جميع الخانات
التجزئة المزدوجة استخدم دالة تجزئة ثانية أفضل توزيع حسابات أكثر
مستخرج من امتحان سابق

مثال: الفحص الخطي

أدخل: 12, 5, 19, 2, 23 في جدول حجم 7
دالة التجزئة: h(k) = k mod 7

الحل:

الخطوة 1: 12 mod 7 = 5 → slot[5] = 12
الخطوة 2: 5 mod 7 = 5 → تصادم! جرب 6 → slot[6] = 5
الخطوة 3: 19 mod 7 = 5 → تصادم! جرب 6, 7=0 → slot[0] = 19
الخطوة 4: 2 mod 7 = 2 → slot[2] = 2
الخطوة 5: 23 mod 7 = 2 → تصادم! جرب 3 → slot[3] = 23
إجمالي الفحوصات: 1+2+3+1+2 = 9

الرسوم البيانية

التعريف: مجموعة من الرؤوس (العقد) متصلة بحواف، تمثل علاقات بين الكائنات.

نقاط رئيسية:

  • رسم بياني موجه: الحواف لها اتجاه (A→B)
  • رسم بياني غير موجه: حواف ثنائية الاتجاه (A—B)
  • رسم بياني موزون: الحواف لها تكاليف/أوزان مرتبطة
  • متصل: يوجد مسار بين أي رأسين
  • دورة: مسار يبدأ وينتهي عند نفس الرأس
  • DAG: رسم بياني موجه لا دوري - بدون دورات

تمثيل الرسوم البيانية

التمثيل المساحة إضافة حافة إيجاد حافة الأفضل لـ
مصفوفة التجاور O(V²) O(1) O(1) الرسوم البيانية الكثيفة
قائمة التجاور O(V+E) O(1) O(درجة) الرسوم البيانية المتفرقة
قائمة الحواف O(E) O(1) O(E) عمليات بسيطة

خوارزميات الرسوم البيانية

  • DFS (بحث بالعمق أولاً): O(V+E) - يستخدم مكدساً/عودية
  • BFS (بحث بالعرض أولاً): O(V+E) - يستخدم طابوراً
  • الفرز الطولوجي: O(V+E) - ترتيب رؤوس DAG
  • ديكسترا: O((V+E)log V) - أقصر مسار
  • التطبيقات: الشبكات الاجتماعية، الخرائط، التبعيات، الدوائر
مستخرج من امتحان سابق

مثال: اختر تخزين الرسم البياني

ابحث عن حافة (مصدر-وجهة) بوقت ثابت، قد توجد أو لا توجد.

الحل:

الخطوة 1: بحاجة للبحث عن حافة بـ O(1)
الخطوة 2: مصفوفة التجاور: matrix[i][j] - O(1) ✓
الخطوة 3: قائمة التجاور: يجب البحث في القائمة - O(درجة)
الخطوة 4: قائمة الحواف: يجب البحث في جميع الحواف - O(E)
الإجابة: مصفوفة التجاور
مثال مولد

مثال: اجتياز BFS

الرسم البياني: A-B, A-C, B-D, C-D, C-E. ابدأ من A.

الحل:

الخطوة 1: ابدأ: طابور=[A], زار=[A]
الخطوة 2: عالج A: أضف الجيران B,C → طابور=[B,C]
الخطوة 3: عالج B: أضف الجار D → طابور=[C,D]
الخطوة 4: عالج C: D موجود بالفعل في الطابور، أضف E → طابور=[D,E]
الخطوة 5: عالج D,E: لا يوجد جيران جدد
ترتيب BFS: A → B → C → D → E