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

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

• أشجار البحث الثنائية (BST) هي هياكل بيانات أساسية في علم الحاسوب.
• تتناول هذه المحاضرة تعريف وخصائص وعمليات أشجار البحث الثنائية، بالإضافة إلى تحليل تعقيدها الزمني.

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

• شجرة البحث الثنائية (BST) هي شجرة ثنائية حيث يكون لكل عقدة مفتاح، ويتم ترتيب المفاتيح بترتيب معين.
• بالنسبة لأي عقدة، يكون مفتاح العقدة أكبر من جميع المفاتيح في شجرتها الفرعية اليسرى.
• بالنسبة لأي عقدة، يكون مفتاح العقدة أصغر من جميع المفاتيح في شجرتها الفرعية اليمنى.
• يجب أن تكون كل من الأشجار الفرعية اليسرى واليمنى أيضًا أشجار بحث ثنائية.

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

• يؤدي الاجتياز الداخلي لشجرة البحث الثنائية إلى تسلسل مرتب للمفاتيح.
• يؤثر ارتفاع شجرة البحث الثنائية على التعقيد الزمني لعمليات البحث والإدراج والحذف.

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

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

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

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

مثال على شجرة البحث الثنائية

• فيما يلي مثال على شجرة بحث ثنائية:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

• الاجتياز الداخلي: 1، 3، 4، 6، 7، 8، 10، 13، 14
• البحث عن 6: ابدأ من 8، وانتقل يسارًا إلى 3، وانتقل يمينًا إلى 6 (تم العثور عليه)
• إدراج 5: ابدأ من 8، وانتقل يسارًا إلى 3، وانتقل يمينًا إلى 6، وانتقل يسارًا إلى 4، وأدخل 5 كطفل أيمن لـ 4.