موازنة شجرة AVL.

Question

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

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

أحدث رمز:

public BinaryNode<T> insert(BinaryNode<T> node) {
    if (this.getElement().compareTo(node.getElement()) > 0) {
        if (this.getLeftChild() != null) {
            BinaryNode<T> b = this.getLeftChild().insert(node);

            if(!this.isBalanced()) {
                this.balance();
            }

            return b;
        } else {
            this.setLeftChild(node);
        }

    } else if (this.getElement().compareTo(node.getElement()) < 0) {
        if (this.getRightChild() != null) {
            return this.getRightChild().insert(node);
        } else {
            this.setRightChild(node);
        }
    }

    return this;
}

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

حاولت أيضا وضع رمز التوازن حيث اقترح ص صموئيل كلاينجكو، ولكن فحص الرصيد على كل إدراج. على سبيل المثال: إذا قام أحد إدراج 7 و 9 و 5 و 3 و 1 على التوالي، أحصل على استثناء مؤشر فارقى عند محاولة إدراج 1.

تحرير: سبب واحد لما ذكر أعلاه قد يكون له علاقة بالطريقة التي كنت أقوم بها الارتفاع. إنه يعمل بشكل جيد مع دوران أيمن واحد إذا قمت بحساب الارتفاع في كل مرة مع الارتفاع () ولكنه يكسر وقت O (سجل (n)) في شجرة AVL.

أي أفكار حول كيفية إنجاز هذا؟

Answer 1

رمزك هو تسلق نفس المسار الذي نزلته. النظر في هذا الرمز:

if (this.getLeftChild() != null) {
    return this.getLeftChild().insert(node);
} 

وتعديلها قليلا:

if (this.getLeftChild() != null) {
    boolean b = this.getLeftChild().insert(node);
    // do something here
    return b;
} 

مع إرجاع التعليمات البرمجية من المكالمات العودية، فإن كل عودة يجلب لك العودة إلى الوالد. من خلال عدم إرجاع قيمة المكالمة التراكبية على الفور، لديك فرصة للقيام بإعادة التوازن.

تحديث للحصول على أحدث رمز

لا تنس التدوين عند إدراجك إلى اليمين.

Answer 2

قد تحاول اجتياز مؤشر الأصل في insert الطريقة، أو يمكنك تحويل insert في طريقة تكرارية واحتفظ بمكدس صريح قمت بتسجيل المسار أسفل الشجرة.

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