تحقيق التوازن بين شجرة البحث الثلاثية

Question

كيف يمكن للمرء أن يدور حول "موازنة" شجرة البحث الثلاثية؟ لا تتناول معظم تطبيقات TST الموازنة ، ولكنها تقترح الإدراج في ترتيب مثالي (لا يمكنني التحكم فيه.)

Answer 1

المقال في الدكتور دوبس عن أشجار البحث الثلاثية يقول: يصف DD Sleator و Re Tarjan خوارزميات التوازن النظري لأشجار البحث الثلاثية في "أشجار البحث الثنائية المعدلة ذاتيا" (Journal of the ACM ، يوليو 1985). يمكنك العثور على إصدارات عبر الإنترنت من هذه الورقة مع محرك البحث المفضل لديك.

Answer 2

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

هذا يضمن أن يتم اجتياز كل طبقة من trie في وقت السجل (ص) ، على الرغم من أنه من المحتمل أن تفعل أفضل من خلال مراعاة حجم المجموعات الفرعية في كل عقدة. يبدو أن هذا أكثر تعقيدًا!

Answer 3

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

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

Answer 4

اقرأ هذه المقالة:

"تعديل الذات للبحث الثلاثية يحاول استخدام الدورات الشرطية والاستدلال العشوائي" بقلم "Ghada Hany Badr ∗ و B. John Oommen †"

سيساعدك ذلك على فهم TSTs وموازنة TST.