لا تعد إزالة العقد من شجرة حمراء سوداء مهمة سهلة ، لذلك من المنطقي تقسيمها إلى عدة أجزاء والنظر في كل حالة على حدة.
cartoonbank.ru
في المقالة الأخيرة ، درسنا قواعد تكوين شجرة بحث باللونين الأحمر والأسود ودرسنا حالات الموازنة عند إضافة العناصر.
الآن دعنا نتحدث عن حذف العناصر.
خذ ، على سبيل المثال ، هذه الشجرة ذات اللون الأحمر والأسود:
تذكر أن الخاصية الرئيسية للشجرة ذات اللون الأحمر والأسود هي نفس الارتفاع الأسود على يسار ويمين كل عقدة. لذلك ، في الأشكال ، بجانب كل عقدة ، سنشير إلى قيمة الارتفاع الأسود ، حتى نتمكن في كل مرحلة من التحقق من ثباتها.
فرق تسد
إن إزالة عنصر من شجرة حمراء سوداء ليست مهمة سهلة كما قد تبدو للوهلة الأولى ، لذلك أقترح تقسيمها إلى عدة أجزاء والنظر في كل منها على حدة.
أولاً ، دعنا نقسم المهمة إلى فئتين:
- لون العقدة التي تمت إزالتها: K أو H.
- عدد العقد الفرعية: 2 ، 1 أو 0
نتيجة لذلك ، نحصل على مصفوفة من 6 خيارات: K2 ، Ch2 ، K1 ، Ch1 ، K0 ، Ch0.
لكل خيار ، يشار إلى العقدة المقابلة لشجرتنا.
دعنا نفكر في عملية الإزالة لكل خيار.
K2 - عقدة حمراء مع طفلين
يتم تقليل مهمة إزالة عقدة مع طفلين إلى مهمة إزالة عقدة مع طفل واحد أو صفر.
للقيام بذلك ، تحتاج إلى البحث عن أقرب عنصر أقل أو أكثر من العنصر المحذوف وتبديله.
يرجى ملاحظة أنه عند تبديل العناصر ، تحتاج فقط إلى تغيير القيم في العقد ، وترك اللون كما هو ، حتى لا تكسر هيكل الشجرة ولا تغير الارتفاع الأسود.
بعد التبادل ، تحتاج إلى إزالة العنصر من موقعه الجديد سيكون إما العنصر الموجود في أقصى اليمين في الفرع الأيسر (الحد الأقصى على اليسار) ، أو العنصر الموجود في أقصى اليسار في اليمين (الحد الأدنى على اليمين) ، على أي حال لن يكون لديه طفل واحد على اليسار أو اليمين. وبالتالي ، يتم تقليل مهمة إزالة عقدة مع طفلين إلى مهمة إزالة عنصر مع طفل واحد أو 0 طفل:
- K2 => K1 أو K0
Ch2 - عقدة سوداء مع طفلين
على غرار الحالة السابقة ، سنقدم مثالًا على حذف العقدة السوداء 16.
كما ترى ، بعد التبادل ، يتم تقليل المهمة إلى حذف عنصر مع طفل واحد:
- Ch2 => Ch1 أو Ch0
K1 - عقدة حمراء مع طفل واحد
إذا لم يكن للعقدة الحمراء طفل واحد ، فعندئذٍ يوجد عنصر NIL أسود بدلاً من ذلك ، ويكون الارتفاع الأسود للعقدة الحمراء هو 1. لذلك ، من ناحية أخرى ، يجب أن يكون الارتفاع الأسود أيضًا 1. ولكن نظرًا لأن العقدة الحمراء لا يمكن أن يكون لها طفل أحمر الألوان ، ثم طفله الآخر يجب أن يكون أسود. نظرًا لأن الارتفاع الأسود يجب أن يكون 1 ، فلا يمكن أن يكون سوى عنصر أسود NIL ، لأنه في حالة وجود عنصر أسود عادي ، سيكون الارتفاع أعلى.
وبالتالي ، لا تحدث حالة K1.
Ch1 - عقدة سوداء مع طفل واحد
إذا لم يكن للعنصر الأسود طفل واحد ، فبدلاً من ذلك يوجد عنصر NIL أسود بارتفاع أسود 1. لذلك ، على الجانب الآخر يجب أن تكون هناك عقدة حمراء بدون أطفال. لإزالة مثل هذا العنصر ، يكفي نقل قيمة العنصر الأحمر إلى العقدة السوداء ، مع الحفاظ على الارتفاع الأسود.
K0 - عقدة حمراء بدون أطفال
أبسط حالة. نقوم ببساطة بإزالة العنصر واستبداله بمرجع NIL: لا
تؤدي إزالة العنصر الأحمر إلى تغيير ارتفاع اللون الأسود.
CH0 - عقدة سوداء بدون أطفال
تعد إزالة العقدة السوداء بدون أطفال أيضًا أمرًا بسيطًا للغاية: نستبدلها بإشارة إلى NIL.
هل تعتقد أن هذا كله تقريبا؟ هاها ، ست مرات.
بعد إزالة العنصر الأسود ، يتغير الارتفاع الأسود للشجرة الفرعية وتحتاج إلى موازنة العنصر الأصلي.
العنصر المحذوف في الأشكال يُرمز له ب x ، ارتفاعه - h. عندما نبدأ للتو في الموازنة ، h = 1 ، ولكن مع الاستدعاءات المتكررة يمكن أن تزيد.
من أجل التحديد ، دعنا نثبت أن العنصر المحذوف هو الطفل المناسب. بعد الإزالة ، انخفض ارتفاعه وأصبح h. هذا يعني أن ارتفاع الابن الأيسر يبقى ح + 1. نحتاج إلى محاذاة ارتفاعات الشجرة الفرعية اليمنى واليسرى وجعلها تساوي h + 1.
أقترح تقسيم المهمة إلى عدة أجزاء مرة أخرى. ما هي الخيارات التي لدينا؟
يمكن أن يكون الوالد أحمر أو أسود. يمكن أن يكون الابن الأيسر أسود أو أحمر أيضًا. والابن المناسب أسود دائمًا - ومن هناك توصلنا إلى التوازن بعد الإزالة.
هناك 6 حالات مختلفة يجب مراعاتها:
- KCH1 و KCH2 - الوالد أحمر ، الطفل الأيسر أسود.
- CHK3 و CHK4 - الوالد أسود ، الطفل الأيسر أحمر.
- HH5 و HH6 - الوالد أسود ، الطفل الأيسر أسود.
سنخزن الصبر والفشار ، أكثر الأشياء إثارة وغموضًا تكمن في المستقبل.
KCH1 - الوالد الأحمر ، الطفل الأيسر أسود مع الأحفاد السود
طالما لدينا العقد الحمراء ، يمكننا تحريكها و / أو إعادة تلوينها لاستعادة توازن الارتفاع الأسود. في هذه الحالة ، يمكننا خفض اللون الأحمر من الوالد إلى الابن الأيسر ، وبالتالي محاذاة الارتفاع الأسود للوالد:
تأكد من التحقق مرة أخرى من الشكل أن الارتفاعات السوداء للعقد a و b محفوظة ، وأن ارتفاع الشجرة الفرعية بأكملها أصبح كما هو ويساوي h + 1.
2 - الوالد أحمر ، الطفل الأيسر أسود مع الحفيد الأحمر الأيسر.
في هذه الحالة ، لا تكفي إعادة الطلاء وحدها. نحتاج إلى انعطاف صغير إلى اليمين بين العقد 3-7. نتيجة لذلك ، سنتمكن من زيادة ارتفاع الشجرة الفرعية اليمنى حتى h + 1:
تعني العقدة الخضراء أنها يمكن أن تكون إما سوداء أو حمراء.
ملحوظة. إذا كانت العقدة "1" سوداء ، و "c" باللون الأحمر ، فيمكن تقليل المشكلة إلى المتغير HH5.
CHK3 - الوالد أسود ، الابن الأيسر أحمر ، الحفيد الأيمن لديه أحفاد أسود
يسمح لك وجود أحفاد الأحفاد السود بإعادة طلاء الحفيد باللون الأحمر وإرساله إلى الشجرة الفرعية الصحيحة عن طريق إجراء انعطاف يمين صغير 3-7 ، ولا تسأل لماذا ، فقط ثق وتحقق من أن الارتفاع الأسود قد استقر:
لاحظ أن العقدة الحمراء 5 لا تزيد من اللون الأسود ارتفاع.
CHK4 - الوالد أسود ، الابن الأيسر أحمر ، الحفيد الأيمن له حفيد أحمر
في الغابة الحمراء ، يوجد المزيد من حطب الوقود السوداء ، وهناك عدد أقل وأقل من الحطب الحمراء ، أي من خلال إعادة تلوين العقد الحمراء ، من الممكن تثبيت الارتفاع الأسود.
في هذه الحالة ، تحتاج إلى عمل دوران كبير إلى اليسار ، والذي يتكون من دورتين صغيرتين 5-3 و5-7. غيرت العقدة ب لونها من الأحمر إلى الأسود وبالتالي زاد ارتفاعها بمقدار 1. تأكد من استقرار ارتفاع الأسود.
HCH5 - الوالد أسود ، الابن الأيسر أسود مع الحفيد الأيمن الأحمر.
عناصر حمراء أقل وأقل في شجرتنا الفرعية ، أعد طلاء آخر حفيد باللون الأسود وقم باستدارة كبيرة إلى اليسار ، كما في الحالة السابقة.
تحقق من استقرار الارتفاع الأسود للشجرة الفرعية.
HCH6 - الوالد أسود ، الابن الأيسر أسود ، أحفاده سود أيضًا
ثم جاءت اللحظة التي نفد فيها الخشب الأحمر. لا يوجد ما تفعله ، عليك أن ترسم العقدة السوداء باللون الأحمر وبالتالي تعادل الارتفاع الأسود للعقدة 7 ، ولكن ليس عن طريق زيادة الارتفاع الأسود للشجرة الفرعية اليمنى ، ولكن عن طريق تقليل الارتفاع الأسود للشجرة الفرعية اليسرى. نتيجة لذلك ، سوف ينخفض الارتفاع الأسود لكامل هيكلنا بمقدار 1 ويجب أن نطلب الموازنة بشكل متكرر للأسلاف.
مثال على الحذف مع الموازنة والعودية
نظرنا في جميع الحالات الست لموازنة الارتفاع الأسود بعد إزالة عنصر من الشجرة ذات اللون الأحمر والأسود. للتعرف بشكل أفضل على كيفية عمل كل هذا ، دعنا نواصل إزالة العقدة 30 من الشجرة الأصلية.
الخطوة الأولى - ببساطة قم بإزالة العقدة 30.
الخطوة الثانية - تشغيل متوازن على والدتها - عقدة 25.
هناك حالة CHCH6:
مع الحزن في نصف ارتفاع الوحدة المستقرة 25.
الخطوة الثالثة - الجد على مستوى التوازن - للعقدة 20.
لجعلها أكثر متعة وأكثر وضوحًا لنرسم الشجرة بأكملها قبل الموازنة وبعدها. هذا هو الحال بالنسبة لـ HK4:
لاحظ كيف تغيرت الشجرة ذات اللون الأحمر والأسود بعد الموازنة ، حيث انتقلت بعض العناصر من الشجرة الفرعية اليسرى إلى اليمين ، واستقر الارتفاع ، وتمت إزالة العنصر ، والجميع سعداء!
تعد إزالة العناصر من شجرة حمراء سوداء واحدة من أصعب العمليات عند العمل مع أشجار البحث الثنائية. في الدورة التدريبية " الخوارزميات وهياكل البيانات " ، لا نأخذ في الاعتبار أشجار البحث الثنائية فحسب ، بل أيضًا العديد من الخوارزميات الأخرى المثيرة للاهتمام ، لمزيد من التفاصيل راجع برنامج الدورة.
