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

شجرة البحث الثنائية (Binary Search Tree) عبارة عن خوارزمية متقدمة تُستخدم لتحليل العقدة وفروعها اليمنى واليسرى والتي تم تشكيلها في هيكل شجرة وإرجاع القيمة. تم تصميم BST بناءً على بنية خوارزمية بحث ثنائية أساسية ومن ثم فإنه يتيح عمليات بحث وإدخال وإزالة أسرع للعقد. هذا يجعل البرنامج سريعًا ودقيقًا حقًا.

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

يتكون BST من عدة عقد ويتكون من السمات التالية:

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

لماذا نحتاج إلى شجرة بحث ثنائية؟

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

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

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

يتم استخدام BST بشكل شائع لتنفيذ عمليات البحث المعقدة ومنطق اللعبة القوي وأنشطة الإكمال التلقائي والرسومات.

تدعم الخوارزمية بكفاءة عمليات مثل البحث والإدراج والحذف.

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

ثلاثة أنواع من الأشجار الثنائية هي:

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

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

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

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

تقدم BST بشكل أساسي الأنواع الثلاثة التالية من العمليات لاستخدامك:

  1. بحث: يبحث في العنصر من الشجرة الثنائية
  2. إدراج: يضيف عنصرًا إلى الشجرة الثنائية
  3. حذف: حذف العنصر من الشجرة الثنائية

كل عملية لها هيكلها الخاص وطريقة تنفيذها / تحليلها ولكن الأكثر تعقيدًا هي عملية الحذف.

عملية البحث

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

كود للبحث في BST:

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

عملية Insert

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

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

توجد قائمة من 6 عناصر يجب إدراجها في BST بالترتيب من اليسار إلى اليمين

أدخل 12 كعقدة جذر وقارن القيم التالية 7 و 9 لإدراجها وفقًا لذلك في الشجرة الفرعية اليمنى واليسرى

قارن القيم المتبقية 19 و 5 و 10 مع العقدة الجذرية 12 وضعها وفقًا لذلك.

فی المرحله التالیة سیقوم البرنامج بلمقارنه طبق الشکل الاعلی.

الكود لإدخال عقدة في BST:

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

عمليات الحذف

لحذف عقدة من BST هناك بعض الحالات مثل حذف جذر أو حذف عقدة طرفية. أيضًا بعد حذف الجذر نحتاج إلى التفكير في عقدة الجذر.

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

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

هذه هي حالة الحذف الأولى التي تحذف فيها عقدة ليس لها توابع. كما ترى في الرسم التخطيطي فإن 19 و 10 و 5 ليس لديهم أطفال. لكننا سنحذف 19.

احذف القيمة 19 وأزل الرابط من العقدة.

شاهد الهيكل الجديد لـ BST بدون 19.

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

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

احذف العقدة 9 واستبدلها بالعقدة الفرعية 10 وأضف رابطًا من 7 إلى 10

عرض الهيكل الجديد لـ BST بدون 9.

هنا سوف تقوم بحذف العقدة 12 التي لديها طفلان

سيحدث حذف العقدة بناءً على قاعدة الترتيب السابق بالترتيب مما يعني أن العنصر الأكبر في الشجرة الفرعية اليسرى البالغ 12 سيحل محله.

احذف العقدة 12 واستبدلها بـ 10 لأنها أكبر قيمة على الشجرة الفرعية اليسرى

اعرض الهيكل الجديد لـ BST بعد حذف 12.

شجرة البحث الثنائية (BST)
  1. احذف عقدة 12 لها طفلان
  2. سيحدث حذف العقدة بناءً على قاعدة In Order Successor ، مما يعني أن العنصر الأكبر في الشجرة الفرعية اليمنى 12 سيحل محله
  3. احذف العقدة 12 واستبدلها بـ 19 لأنها أكبر قيمة على الشجرة الفرعية اليمنى
  4. اعرض الهيكل الجديد لـ BST بعد حذف 12

كود لحذف عقدة

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

شروط مهمة

  1. إدراج: إدراج عنصر في شجرة / إنشاء شجرة.
  2. بحث: يبحث عن عنصر في شجرة.
  3. اجتياز الطلب المسبق: اجتياز الشجرة بطريقة الترتيب المسبق.
  4. واجتياز الطلب: اجتياز شجرة بطريقة مرتبة.
  5. اجتياز الطلب اللاحق: اجتياز الشجرة بطريقة الترتيب اللاحق.

ملخص

BST هي خوارزمية ذات مستوى متقدم تؤدي عمليات مختلفة بناءً على مقارنة قيم العقدة مع العقدة الجذرية.

أي من النقاط في التسلسل الهرمي للأب والطفل يمثل العقدة. تظل العقدة الأصل أو العقدة الجذرية موجودة طوال الوقت.

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

يمكن أن تحتوي كل عقدة على صفر أو واحد أو طفلين.

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

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

تُستخدم الخوارزمية في حلول واقعية مثل الألعاب وبيانات الإكمال التلقائي والرسومات.

المصدر

منشور ذات صلة
ماهو CSS؟ 5 Minutes

(Cascading Style Sheets (CSS

آيات عامر

ما هو CSS؟ هي آلية بسيطة لإضافة نمط (على سبيل المثال، الخطوط والألوان والتباعد) إلى […]

لغة ++C 6 Minutes

ما هي لغة ++C؟

علي شفیعي

هل لغة ++C هي أفضل لغة برمجة؟ تعتمد الإجابة على المنظور والمتطلبات. يمكن إنجاز بعض المهام في ++C ، ولكن ليس بسرعة كبيرة. على سبيل المثال ، تصميم شاشات واجهة المستخدم الرسومية (GUI) للتطبيقات.

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

السلة