حذف في شجرة البحث الثنائية

Question

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

الخوارزمية:

giveacodicetagpre.

على سبيل المثال، أريد حذف رقم العقدة $ 7 $ :

ولكن لا ينبغي أن تكون النتيجة النهائية؟

Answer 1

أنت خيار صحيح بالتأكيد.

ومع ذلك، لا يوجد خطأ في رمز المعلم الخاص بك، إما. هنا مقتطف من CLRS.

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

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

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

Answer 2

الرسم الخاص بك هو الحل الصحيح، ومع ذلك، فإن تحليلك إلى رمز المعلم الخاص بك غير دقيق (u mis intrepreted code)

عندما رأيت لأول مرة qi لم تقرأ الشفرة جيدا وكنت أعتقد (من الموافقة المسبقة عن علم / الرسم 1) يقوم معلمك بإجراء عملية حذف لنوع خاص من BST له ظروف إضافية من النظام النسبي، ولكن هذا ليس هو الحال

عند الحذف من BST (محاولة متابعة متغيرات رمزك، Z هي العقدة المراد حذفها)

إذا كانت z هي عقدة ورقة (لا أطفال) فقط استبدل مؤشر الأصل له مع null

إذا كان z لديه طفل واحد (سواء كان اليسار أو اليمين لا يهم) جعل نقاط المؤشر الأصل إلى طفلها الوحيد

هذا الترميز بسيط جدا، في رمز نصف زائف

إذا كان (z.left== null) {mission_delete (z، zright)؛ إرجاع()؛ // إما أن لدينا فقط الشجرة الحقيقية أو لا شيء }

// هنا نأخذ بالتأكيد هناك مجموعة فرعية يسارية

إذا كان (z. right== null) {mission_delete (z، z.left)؛ إرجاع()؛ }

// mission_delete لها استبدال مثل المعلمة الثانية، جميع الحلقات في رمز المعلم الخاص بك هو معرفة ما هو Incase لدينا اثنين من الفئة الفرعية

إذا كان Z لديه طفلين، ثم عليك أن تنتخب أحدهم لأخذ مكانه، وهنا يأتي رمز المعلم الخاص بك (وليس في الحالة السابقة)

في اور الموافقة المسبقة عن علم تخيلك حذف "5" هذا التعليمات البرمجية الطويلة هذه لضبط الشجرة الفرعية المتبقية من أطفالها 2 (كيفية ربط 7 و 3 وأطفالهم إلى العقدة 12 الحفاظ على تقييد BST)

إذا كنت بحاجة إلى تتبع مفصل، فقد نفعل ذلك، ولكن فقط إذا وجدت أن هذا مفيد كتبدأ