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

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

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

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

1. توجد العقدة الرئيسية أو المستوى الأصلي 11. وتحتها، توجد العقد/الفروع اليسرى واليمنى بقيمها الأساسية الخاصة
2. تحتوي الشجرة الفرعية اليمنى على قيم أساسية أكبر من العقدة الأصلية
3. تحتوي الشجرة الفرعية اليسرى على قيم أعلى من العقدة الأصلية

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

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

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

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

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

لمعرفة المزيد عن شجرة ثنائية في بنية البيانات إذا كنت مهتم.

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

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

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

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

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

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

البحث Operaالإنتاج

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

1. العنصر المطلوب البحث عنه هو 10
2. قارن العنصر بالعقدة الجذرية 12، 10 < 12، ومن ثم تنتقل إلى الشجرة الفرعية اليسرى. لا حاجة لتحليل الشجرة الفرعية اليمنى
3. قارن الآن 10 بالعقدة 7، 10 > 7، لذا انتقل إلى الشجرة الفرعية اليمنى
4. ثم قارن 10 بالعقدة التالية، وهي 9، 10 > 9، وانظر إلى الشجرة الفرعية اليمنى
5. 10 تطابقات مع القيمة الموجودة في العقدة، 10 = 10، تُرجع القيمة إلى المستخدم.

الكود الزائف للبحث في 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)

إدراج Operaالإنتاج

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

1. توجد قائمة بـ 6 عناصر يجب إدراجها في BST بالترتيب من اليسار إلى اليمين
2. أدخل 12 كعقدة جذر وقارن القيمتين التاليتين 7 و9 لإدراجهما وفقًا لذلك في الشجرة الفرعية اليمنى واليسرى
3. قارن القيم المتبقية 19 و5 و10 مع العقدة الجذرية 12 وضعها وفقًا لذلك. 19 > 12 ضعه كالابن الأيمن للرقم 12، 5 < 12 و 5 < 7، وبالتالي ضعه كالابن الأيسر للرقم 7. الآن قارن 10، 10 < 12 و 10 > 7 و 10 > 9، ضع 10 كشجرة فرعية صحيحة من 9.

الكود الزائف لإدراج عقدة في 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

حذف Operaستعقد

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

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

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

1. هذه هي حالة الحذف الأولى التي تقوم فيها بحذف عقدة لا تحتوي على عناصر فرعية. كما ترون في الرسم البياني أن 19 و 10 و 5 ليس لديهم أطفال. لكننا سنحذف 19.
2. احذف القيمة 19 وأزل الرابط من العقدة.
3. عرض الهيكل الجديد للـ BST بدون 19

1. هذه هي حالة الحذف الثانية التي تقوم فيها بحذف عقدة بها طفل واحد، كما ترون في الرسم التخطيطي أن 1 لها طفل واحد.
2. احذف العقدة 9 واستبدلها بالعقدة الفرعية 10 وأضف رابطًا من 7 إلى 10
3. عرض الهيكل الجديد للـ BST بدون 9

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

1. 1 احذف العقدة 12 التي تحتوي على طفلين
2. 2 سيتم حذف العقدة بناءً على قاعدة In Order Successor، مما يعني أن العنصر الأكبر في الشجرة الفرعية اليمنى المكون من 12 سيحل محله
3. 3 احذف العقدة 12 واستبدلها بـ 19 لأنها أكبر قيمة في الشجرة الفرعية اليمنى
4. 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)

شروط مهمة

• إدراج: إدراج عنصر في شجرة/إنشاء شجرة.
• البحث: يبحث عن عنصر في شجرة.
• اجتياز الطلب المسبق: اجتياز شجرة بطريقة الطلب المسبق.
• اجتياز النظام: اجتياز شجرة بطريقة مرتبة.
• اجتياز ما بعد الطلب: اجتياز شجرة بطريقة ما بعد الطلب.

ملخص

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