كيفية حذف عقدة من شجرة BST مع طفلين؟

Question

i googled، وقراءة عدة برامج تعليمية وشاهدت تفسيرات خوارزمية حذف العقدة BST قبل نشر هذا السؤال. لسبب ما، لا يمكنني العثور على شرح كامل لخوارزميات حذف العقدة BST.

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

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

بالنسبة للخوارزمية الأولى، نختار العناصر 6 وسوف تفقد الشجرة الفرعية المناسبة. بالنسبة للخوارزمية الثانية، نختار العنصر 4 وسيخسر الشجرة الفرعية اليسرى. بالنسبة للخوارزمية الثالثة، نختار العناصر 7 والتي من شأنها أن تنتهك قواعد BST. بالنسبة للخوارزمية الرابعة، نختار العناصر 3 والتي من شأنها أن تنتهك قواعد BST أيضا.

ما هي الخوارزمية الصحيحة لحالة استخدام هذه؟

Answer 1

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

النظر في عقدة مع طفلين. قم بتبديل هذه العقدة مع سلفها في BST (هذه العقدة أقصى اليمين في الشجرة الفرعية اليسرى)، أو مبادلة - متماثلة متناظرة مع الخلف (العقدة اليسرى في الشجرة الفرعية اليمنى).

href="https://i.stack.imgur.com/gx6mf.png" rel="nofollow noreferrer">

قد تتم إزالة العقدة الآن في معظم الأطفال (في حال ذهبنا إلى السلف، لا يمكن أن يكون له طفل يمين). إذا لم يكن لديه أطفال نحذف العقدة، ونحن نفذنا.

في حالة وجود العقدة طفلة واحدة، نقوم بإزالة العقدة واستبدالها عن طريق Subtree. نحن مرة أخرى نحصل على BST.

في مثالك، نريد إزالة 5 وتبديله مع سلفها 4. الآن 4 في الجذر، وغادر 5 الطفل 3. أخيرا نحن نزيل 5 ووضع طفلها 3 في مكانه. الآن 3 هو الطفل المناسب في 2.

ps. تسمى هذه الطريقة أحيانا "الحذف عن طريق النسخ"، لأن القيم يتم نسخها من عقدة إلى أخرى. البعض لا يوافق على هذه العملية لسببين. قد تكون النسخ الأول عملية باهظة الثمن، والمراجع الثانية ضائعة (إذا كانت التحتية الأخرى تشير إلى عقدة بقيمة معينة). بدلا من ذلك، يغير المرء فقط المؤشرات.