موازنة الشجرة الثنائية (AVL)

Question

حسنًا، هذا موضوع آخر في المجال النظري لرجال CS الموجودين حولنا.

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

هل يمكنكم يا رفاق مساعدتي في هذا؟

Answer 1

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

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

الرد على سؤال التحرير

سأقدم طريقي الشخصي لفهم أشجار AVL.

عليك أولاً أن تفهم ما هو دوران الشجرة، لذا تجاهل كل شيء آخر سمعته عن خوارزميات AVL وافهم ذلك.استقيم في رأسك وهو دوران لليمين ودوران لليسار، وما يفعله كل منهما بالشجرة، وإلا فإن وصف الطرق الدقيقة سوف يربكك.

بعد ذلك، افهم أن الحيلة لموازنة أشجار AVL هي أن كل عقدة تسجل فيها الفرق بين ارتفاع شجراتها الفرعية اليسرى واليمنى.تعريف "الارتفاع المتوازن" هو أن هذا يتراوح بين -1 و1 شاملاً لكل عقدة في الشجرة.

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

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

ثم هناك مهمة ترجمة كل ذلك إلى كود.

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

Answer 2

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

يعد هذان التطبيقان كافيين لمعظم سيناريوهات الأغراض العامة.

Answer 3

لقد قمت ببعض الأعمال مع أشجار AVL مؤخرًا.

أفضل مساعدة تمكنت من العثور عليها حول كيفية تحقيق التوازن بينهما كانت من خلال البحث في Google.

لقد قمت للتو بالتشفير حول هذا الكود الزائف (إذا كنت تفهم كيفية القيام بالتدوير، فمن السهل جدًا تنفيذه).

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

Answer 4

أوافق على أن البرنامج الكامل لن يكون مناسبًا.

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

Answer 5

شجرة AVL غير فعالة لأنه يتعين عليك إجراء العديد من عمليات التدوير لكل عملية إدراج/حذف.

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

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

Answer 6

من أجل موازنة شجرة AVL، كتبت للتو مجموعة من الوظائف التي فكرت في مشاركتها مع الجميع هنا.أعتقد أن هذا التنفيذ لا تشوبه شائبة.الاستفسارات/الأسئلة/النقد هي بالطبع موضع ترحيب:

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

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

هتافات.

Answer 7

هناك تنفيذ كامل لشجرة avl ذات التوازن الذاتي @ http://code.google.com/p/self-balancing-avl-tree/ .كما أنه ينفذ أيضًا عمليات تسلسل وتقسيم الوقت اللوغاريتمي بالإضافة إلى مجموعات الخرائط/الخرائط المتعددة