أشجار البحث الثنائية - دليل دراسة شامل

🎯 مقدمة عن أشجار البحث الثنائية

ما هي شجرة البحث الثنائية (BST)؟

شجرة البحث الثنائية هي شجرة ثنائية مرتبة بشكل متماثل. هذا يعني:

كل عقدة تحتوي على مفتاح وقيمة مرتبطة
مفتاح كل عقدة أكبر من جميع المفاتيح في شجرتها الفرعية اليسرى
مفتاح كل عقدة أصغر من جميع المفاتيح في شجرتها الفرعية اليمنى

هيكل الشجرة الثنائية

الشجرة الثنائية إما:

فارغة (null)
عقدة تحتوي على مراجع إلى شجرتين ثنائيتين منفصلتين (الشجرتان الفرعيتان اليسرى واليمنى)

تشريح شجرة البحث الثنائية

E (الجذر) / \ / \ A S \ / \ C R X / \ H \ M

ملاحظة: المفاتيح الأصغر من E على اليسار، والمفاتيح الأكبر من E على اليمين

🏗️ أساسيات أشجار البحث الثنائية

هيكل العقدة

private class Node {
    private Key key;           // مرتب حسب المفتاح
    private Value val;         // القيمة المرتبطة
    private Node left, right;  // الشجرتان الفرعيتان اليسرى واليمنى
    
    public Node(Key key, Value val) {
        this.key = key;
        this.val = val;
    }
}
                

⚠️ المتطلبات الأساسية

يجب أن ينفذ نوع المفتاح واجهة Comparable لعمليات الترتيب.

يجب أن تكون المفاتيح فريدة وتدعم عمليات المقارنة.

خصائص أشجار البحث الثنائية

الخاصية	الوصف
الترتيب المتماثل	الشجرة الفرعية اليسرى < العقدة < الشجرة الفرعية اليمنى
الجذر	العقدة العلوية للشجرة
الورقة	عقدة بدون أطفال (كلتا الروابط null)
الأصل	العقدة التي لها رابطة إلى عقدة أخرى
العمق	عدد الروابط من الجذر إلى العقدة
الارتفاع	أقصى عمق لأي عقدة

⚙️ عمليات أشجار البحث الثنائية

1. عملية البحث

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

القاعدة: إذا كانت أقل، اذهب لليسار؛ إذا كانت أكبر، اذهب لليمين؛ إذا تساوت، نجح البحث!

public Value get(Key key) {
    Node x = root;
    while (x != null) {
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x = x.left;   // اذهب لليسار
        else if (cmp > 0) x = x.right;  // اذهب لليمين
        else              return x.val;   // وجد!
    }
    return null;  // لم يتم العثور
}
                

✅ تعقيد البحث

التكلفة: عدد المقارنات = 1 + عمق العقدة

أفضل حالة: O(log n) للشجرة المتوازنة

أسوأ حالة: O(n) للشجرة المتدهورة

2. عملية الإدراج

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

القاعدة: إذا كانت أقل، اذهب لليسار؛ إذا كانت أكبر، اذهب لليمين؛ إذا كانت null، أدخل!

public void put(Key key, Value val) {
    root = put(root, key, val);
}

private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val);  // أدخل هنا
    
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) x.left  = put(x.left,  key, val);
    else if (cmp > 0) x.right = put(x.right, key, val);
    else              x.val   = val;  // تحديث القيمة
    
    return x;  // إعادة تعيين الروابط في المسار العودي
}
                

مثال الإدراج: إضافة G إلى شجرة بحث ثنائية

قبل: بعد: S S / \ / \ E X E X / \ / \ A R A R \ / \ H H \ \ M M / G ← جديد

ابدأ من الجذر S (G < S، اذهب لليسار)
قارن مع E (G > E، اذهب لليمين)
قارن مع R (G < R، اذهب لليسار)
قارن مع H (G < H، اذهب لليسار)
H.left هي null → أدخل G هنا!

3. إيجاد الحد الأدنى/الأقصى

// الحد الأدنى: اذهب لليسار حتى الوصول إلى null
private Node min(Node x) {
    if (x.left == null) return x;
    return min(x.left);
}

// الحد الأقصى: اذهب لليمين حتى الوصول إلى null
private Node max(Node x) {
    if (x.right == null) return x;
    return max(x.right);
}
                

🗑️ حذف أشجار البحث الثنائية (حذف هيبارد)

⚠️ تعقيد الحذف

الحذف هو أكثر العمليات تعقيداً في أشجار البحث الثنائية. هناك ثلاث حالات يجب التعامل معها.

الحالة 0: لا يوجد أطفال (عقدة ورقة)

الحل: ببساطة احذف العقدة عن طريق تعيين رابط الأصل إلى null.

احذف C: E E / \ / \ A S → A S \ C (احذف) (تم الحذف)

الحالة 1: طفل واحد

الحل: استبدل العقدة بطفلها (تجاوز العقدة).

احذف R: E E / \ / \ A S → A S / \ / \ R X H X \ \ H M \ M

الحالة 2: طفلان (الأكثر تعقيداً)

خوارزمية حذف هيبارد

ابحث عن العقدة t للحذف
ابحث عن الخليفة x = الحد الأدنى للعقد في الشجرة الفرعية اليمنى لـ t
احذف الحد الأدنى في الشجرة الفرعية اليمنى لـ t
استبدل t بـ x:
- عيّن x.left = t.left
- عيّن x.right = deleteMin(t.right)

مثال: حذف E (له طفلان)

الخطوة 1: ابحث عن الخليفة (الحد الأدنى في الشجرة الفرعية اليمنى) E ← احذف الخليفة = H (الأدنى في الشجرة الفرعية اليمنى) / \ A S / \ / \ C H R X \ M الخطوة 2: احذف الحد الأدنى من الشجرة الفرعية اليمنى E / \ A S / / \ C R X \ M الخطوة 3: استبدل E بـ H H ← جذر جديد / \ A S / / \ C R X \ M

دالة مساعدة لحذف الحد الأدنى

private Node deleteMin(Node x) {
    if (x.left == null) return x.right;  // استبدل بالطفل الأيمن
    x.left = deleteMin(x.left);  // تكرار عودي لليسار
    x.count = 1 + size(x.left) + size(x.right);  // تحديث العدد
    return x;
}
                

تنفيذ الحذف الكامل

public void delete(Key key) {
    root = delete(root, key);
}

private Node delete(Node x, Key key) {
    if (x == null) return null;
    
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) x.left  = delete(x.left,  key);
    else if (cmp > 0) x.right = delete(x.right, key);
    else {  // وجدت العقدة المراد حذفها
        // الحالة 0 و 1: لا يوجد طفل أيمن أو لا يوجد طفل أيسر
        if (x.right == null) return x.left;
        if (x.left  == null) return x.right;
        
        // الحالة 2: طفلان - استخدم حذف هيبارد
        Node t = x;
        x = min(t.right);              // ابحث عن الخليفة
        x.right = deleteMin(t.right);  // احذف الخليفة من اليمين
        x.left = t.left;               // أرفق الشجرة الفرعية اليسرى
    }
    x.count = size(x.left) + size(x.right) + 1;
    return x;
}
                

⚠️ مشكلة حذف هيبارد

حل غير مرضٍ: ليس متماثلاً!

النتيجة: تصبح الأشجار غير متوازنة بعد عمليات حذف كثيرة

تدهور الأداء: √N لكل عملية (بدلاً من log N)

مشكلة مفتوحة: حذف بسيط وفعال لأشجار البحث الثنائية لا يزال غير محلول!

بديل الحذف الكسول

نهج شاهد القبر

عيّن قيمة العقدة إلى null
اترك المفتاح في الشجرة لتوجيه عمليات البحث
لا تعتبره متساوياً أثناء البحث

المشكلة: يزداد حمل الذاكرة مع الوقت (تكاثر شواهد القبور)

التكلفة: ~2 ln N' حيث N' = إجمالي المفاتيح المُدرجة أبداً

📊 تحليل الأداء

شكل الشجرة مهم!

أفضل حالة (متوازنة): الحالة النموذجية: أسوأ حالة (متدهورة): H S A / \ / \ \ C S E X C / \ / \ / \ \ A E R X A R E \ \ \ C H H \ \ M M \ الارتفاع: log N log N الارتفاع: N R O(log n) O(log n) O(n) \ S \ X

التحليل الرياضي

إدراج عشوائي (الحالة المتوسطة)

الافتراض: إذا تم إدراج N من المفاتيح المميزة بترتيب عشوائي:

العدد المتوقع للمقارنات: ~2 ln N ≈ 1.39 log₂ N
الارتفاع المتوقع للشجرة: ~4.311 ln N (ريد، 2003)

البرهان: مراسلة 1-1 مع تقسيم الفرز السريع

أسوأ حالة

الارتفاع: N - 1 (قائمة مرتبطة)
يحدث عندما يتم إدراج المفاتيح بترتيب مصفى
الاحتمال: صغير بشكل أسي للإدراجات العشوائية

جدول ملخص التعقيد

العملية	أفضل حالة	الحالة المتوسطة	أسوأ حالة
بحث	log N	1.39 log N	N
إدراج	log N	1.39 log N	N
حذف	log N	√N	N
الحد الأدنى/الأقصى	log N	1.39 log N	N

⚠️ تدهور أداء الحذف

بعد عمليات حذف كثيرة باستخدام حذف هيبارد، تصبح الأشجار غير متوازنة!

جميع العمليات تتدهور إلى √N في المتوسط

💻 تنفيذ كامل لشجرة البحث الثنائية

هيكل الفئة

public class BST<Key extends Comparable<Key>, Value> {
    private Node root;  // جذر شجرة البحث الثنائية
    
    private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        private int count;  // عدد العقد في الشجرة الفرعية
        
        public Node(Key key, Value val) {
            this.key = key;
            this.val = val;
            this.count = 1;
        }
    }
    
    public void put(Key key, Value val) { /* كما بالأعلى */ }
    public Value get(Key key) { /* كما بالأعلى */ }
    public void delete(Key key) { /* كما بالأعلى */ }
    public Iterable<Key> iterator() { /* اجتياز بالترتيب */ }
}
                

طرق إضافية مفيدة

// الحجم: عدد العقد في الشجرة
public int size() {
    return size(root);
}

private int size(Node x) {
    if (x == null) return 0;
    return x.count;
}

// الارتفاع: أقصى عمق
public int height() {
    return height(root);
}

private int height(Node x) {
    if (x == null) return -1;
    return 1 + Math.max(height(x.left), height(x.right));
}

// الأرضية: أكبر مفتاح ≤ مفتاح معطى
public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null) return null;
    return x.key;
}

private Node floor(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    if (cmp < 0) return floor(x.left, key);
    Node t = floor(x.right, key);
    if (t != null) return t;
    else return x;
}
                

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

// اجتياز بالترتيب: يسار → عقدة → يمين (يعطي ترتيباً مصفى!)
private void inorder(Node x) {
    if (x == null) return;
    inorder(x.left);
    System.out.println(x.key);
    inorder(x.right);
}

// اجتياز مسبق: عقدة → يسار → يمين
private void preorder(Node x) {
    if (x == null) return;
    System.out.println(x.key);
    preorder(x.left);
    preorder(x.right);
}

// اجتياز لاحق: يسار → يمين → عقدة
private void postorder(Node x) {
    if (x == null) return;
    postorder(x.left);
    postorder(x.right);
    System.out.println(x.key);
}
                

💡 نصيحة للاجتياز

الاجتياز بالترتيب لشجرة البحث الثنائية ينتج مفاتيح مرتبة!

لهذا تسمى "الترتيب المتماثل" - الاجتياز بالترتيب يحترم الترتيب.

📝 ملخص ومقارنة

مقارنة تنفيذ جدول الرموز

التنفيذ	بحث (أسوأ)	إدراج (أسوأ)	حذف (أسوأ)	بحث (متوسط)	إدراج (متوسط)	حذف (متوسط)	مرتب؟
بحث تسلسلي (قائمة غير مرتبة)	N	N	N	N/2	N	N/2	❌
بحث ثنائي (مصفوفة مرتبة)	log N	N	N	log N	N/2	N/2	✅
شجرة بحث ثنائية	N	N	N	1.39 log N	1.39 log N	√N	✅

الاستنتاجات الرئيسية

✅ مزايا أشجار البحث الثنائية

بحث وإدراج فعالان: O(log N) في المتوسط
تدعم العمليات المرتبة (الحد الأدنى، الأقصى، الأرضية، السقف، الرتبة)
الاجتياز بالترتيب يعطي ترتيباً مصفى
هيكل ديناميكي (لا حاجة لتحديد الحجم مسبقاً)
تنفيذ عودي بسيط

⚠️ قيود أشجار البحث الثنائية

لا يوجد ضمان للأداء: يمكن أن تتدهور إلى O(N)
الشكل يعتمد على ترتيب الإدراج
عملية الحذف تتدهور الأداء إلى √N
غير مناسبة عندما يكون الأداء المضمون مطلوباً

🚀 ما التالي؟

أشجار البحث الثنائية المتوازنة تحل مشكلة ضمان الأداء!

أشجار 2-3: ضمان أداء log N
أشجار الأحمر-أسود: تنفيذ عملي لأشجار البحث الثنائية المتوازنة
أشجار AVL: أشجار متوازنة بشكل صارم
أشجار B: للتخزين المستند إلى القرص

المحاضرة القادمة ستغطي كيفية ضمان الأداء اللوغاريتمي لجميع العمليات!

بطاقة مرجعية سريعة

ورقة غش لعمليات أشجار البحث الثنائية

العملية	الخوارزمية	التعقيد (متوسط)
بحث	قارن، اذهب يسار/يمين، كرر	O(log N)
إدراج	ابحث، أدخل عند رابط null	O(log N)
حذف (0 أطفال)	عيّن رابط الأصل إلى null	O(log N)
حذف (1 طفل)	استبدل بالطفل	O(log N)
حذف (2 أطفال)	استبدل بالخليفة (هيبارد)	O(√N)
الحد الأدنى/الأقصى	اذهب كل اليسار/اليمين	O(log N)
أرضية/سقف	ابحث مع منطق احتياطي	O(log N)

نصائح للدراسة

📚 كيف تتقن أشجار البحث الثنائية

ارسم أشجاراً! تدرب على رسم الإدراج والحذف يدوياً
تتبع الخوارزميات: اتبع الاستدعاءات العودية خطوة بخطوة
قارن الحالات: أفضل مقابل متوسط مقابل أسوأ - افهم متى يحدث كل منها
نفّذ من الصفر: اكتب الكود دون النظر إلى الملاحظات
حلل التعقيد: دائماً احسب المقارنات وفكر في ارتفاع الشجرة

أسئلة امتحان شائعة

🎓 مسائل تدريبية

ارسم شجرة البحث الثنائية الناتجة عن إدراج المفاتيح بالترتيب: 5, 2, 8, 1, 3, 7, 9
اعرض خطوة بخطوة حذف عقدة بها طفلان
ما هو أسوأ ارتفاع لشجرة بحث ثنائية بـ N عقدة؟
لماذا يتدهور حذف هيبارد الأداء؟
قارن بين شجرة البحث الثنائية والبحث الثنائي على المصفوفات - متى تستخدم كل منها؟
اكتب كوداً عودياً لاجتياز أشجار البحث الثنائية (بالترتيب، مسبق، لاحق)