تسلسل / دمج / الانضمام إلى أشجار AVL

Question

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

Answer 1

على افتراض أنك قد تدمر أشجار المدخلات:

1. قم بإزالة العنصر في أقصى اليمين للشجرة اليسرى، واستخدمه لإنشاء عقدة جذرية جديدة، والذي يمثل الطفل الأيسر الشجرة اليسرى، والذي يمنح الطفل المناسب الشجرة الصحيحة: O (سجل N)
2. تحديد وتعيين عامل توازن العقدة: O (سجل N). في (مؤقت) انتهاك الثابتة، قد يكون عامل التوازن خارج النطاق {-1، 0، 1}
3. تدوير للحصول على عامل التوازن مرة أخرى في المدى: O (سجل ن) الدوران: O (سجل ن)

وبالتالي، يمكن إجراء العملية بأكملها في O (سجل N).

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

1. تحديد ارتفاع كلا الشجرات: O (سجل N).
   على افتراض أن الشجرة الصحيحة أطول (الحالة الأخرى متماثلة):
2. إزالة العنصر في أقصى اليمين من left شجرة (تدوير وضبط ارتفاعها المحسوب إذا لزم الأمر). يترك n يكون هذا العنصر. س (سجل ن)
3. في الشجرة الصحيحة، انتقل إلى اليسار حتى تصل إلى عقدة، والذي يكون الفرع الفرعي على الأكثر ثانية واحدة من left. وبعد يترك r يكون تلك العقدة. س (سجل ن)

4. استبدل هذه العقدة بعقدة جديدة ذات قيمة n، والخروج left و r. وبعد س (1)
   عن طريق البناء، العقدة الجديدة هي متوازنة AVL، والشععة الفرعية 1 أطول من r.

5. زيادة رصيد والدها وفقا لذلك. س (1)

6. وتدمير مثلك بعد إدراج. س (سجل ن)

Answer 2

أحد الحلول البسيطة الترا (التي تعمل دون أي افتراضات في العلاقات بين الأشجار) هي:

1. هل هناك نوع دمج كل من الأشجار في صفيف مدمج واحد (بشكل متزامن تكرار كل من الأشجار).
2. بناء شجرة AVL من الصفيف - خذ العنصر الأوسط ليكون الجذر، وتطبيق متكرر على النصفين الأيسر واليمين.

كلا الخطوتين س (ن). القضية الرئيسية معها هي أنها تأخذ O (N) مساحة إضافية.

Answer 3

يمكن العثور على أفضل حل قرأته لهذه المشكلة هنا. وبعد قريب جدا من ميريتونإجابة إذا قمت بتصحيح هذه المشكلة:

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

Answer 4

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