شجرة البحث الثنائية (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، تُرجع القيمة إلى المستخدم.

كنية Code للبحث في 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 عناصر يجب إدراجها في شجرة البحث الثنائية بالترتيب من اليسار إلى اليمين.
2. أدخل 12 كعقدة جذرية وقارن القيمتين التاليتين 7 و 9 لإدخالهما وفقًا لذلك في الشجرة الفرعية اليمنى واليسرى.
3. قارن القيم المتبقية 19 و5 و10 مع العقدة الجذرية 12، ثم ضعها في مكانها المناسب. بما أن 19 أكبر من 12، ضعها كابن أيمن لـ 12؛ وبما أن 5 أصغر من 12 وأصغر من 7، ضعها كابن أيسر لـ 7. الآن قارن 10، بما أن 10 أصغر من 12 وأكبر من 7 وأكبر من 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ستعقد

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

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

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

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

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

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

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

كنية Code لحذف عقدة

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, delete the successor
        free(newNode)
    else
        free(y)

شروط مهمة

• أدخل: يُدرج عنصرًا في شجرة / يُنشئ شجرة.
• بحث: يبحث عن عنصر في شجرة.
• مسار الطلب المسبق: يجتاز الشجرة بطريقة الترتيب المسبق.
• اجتياز الترتيب الداخلي: يجتاز الشجرة بطريقة منظمة.
• اجتياز ما بعد الطلب: يجتاز الشجرة بطريقة لاحقة للترتيب.

الأسئلة الشائعة