تست AVLTree Class – DEV Community

در این بخش مثالی از استفاده از AVLTree کلاس کد زیر یک برنامه آزمایشی را ارائه می دهد. برنامه یک AVLTree با آرایه ای از اعداد صحیح مقدار دهی اولیه می شود 25، 20، و 5 (خطوط 7)، عناصر را در خطوط 11-20 درج می کند، و عناصر را در خطوط 24-30 حذف می کند. از آنجا که AVLTree یک زیر کلاس از BST و عناصر موجود در a BST قابل تکرار هستند، برنامه از یک حلقه foreach برای عبور از تمام عناصر در خطوط 35-37 استفاده می کند.

package demo;

public class TestAVLTree {

    public static void main(String[] args) {
        // Create an AVL tree
        AVLTree tree = new AVLTree(new Integer[]{25, 20, 5});
        System.out.print("After inserting 25, 20, 5:");
        printTree(tree);

        tree.insert(34);
        tree.insert(50);
        System.out.print("\nAfter inserting 34, 50:");
        printTree(tree);

        tree.insert(30);
        System.out.print("\nAfter inserting 30");
        printTree(tree);

        tree.insert(10);
        System.out.print("\nAfter inserting 10");
        printTree(tree);

        tree.delete(34);
        tree.delete(30);
        tree.delete(50);
        System.out.print("\nAfter removing 34, 30, 50:");
        printTree(tree);

        tree.delete(5);
        System.out.print("\nAfter removing 5:");
        printTree(tree);

        System.out.print("\nTraverse the elements in the tree: ");
        for (int e: tree) {
            System.out.print(e + " ");
        }
    }

    public static void printTree(BST tree) {
        // Traverse tree
        System.out.print("\nInorder (sorted): ");
        tree.inorder();
        System.out.print("\nPostorder: ");
        tree.postorder();
        System.out.print("\nPreorder: ");
        tree.preorder();
        System.out.print("\nThe number of nodes is " + tree.getSize());
        System.out.println();
    }
}

After inserting 25, 20, 5:
Inorder (sorted): 5 20 25
Postorder: 5 25 20
Preorder: 20 5 25
The number of nodes is 3

After inserting 34, 50:
Inorder (sorted): 5 20 25 34 50
Postorder: 5 25 50 34 20
Preorder: 20 5 34 25 50
The number of nodes is 5

After inserting 30
Inorder (sorted): 5 20 25 30 34 50
Postorder: 5 20 30 50 34 25
Preorder: 25 20 5 34 30 50
The number of nodes is 6

After inserting 10
Inorder (sorted): 5 10 20 25 30 34 50
Postorder: 5 20 10 30 50 34 25
Preorder: 25 10 5 20 34 30 50
The number of nodes is 7

After removing 34, 30, 50:
Inorder (sorted): 5 10 20 25
Postorder: 5 20 25 10
Preorder: 10 5 25 20
The number of nodes is 4

After removing 5:
Inorder (sorted): 10 20 25
Postorder: 10 25 20
Preorder: 20 10 25
The number of nodes is 3

Traverse the elements in the tree: 10 20 25

شکل زیر نشان می دهد که چگونه درخت با اضافه شدن عناصر به درخت تکامل می یابد. پس از اضافه شدن 25 و 20، درخت مانند شکل زیر (الف) است. 5 به عنوان فرزند سمت چپ 20 درج شده است، همانطور که در شکل زیر (ب) نشان داده شده است. درخت متعادل نیست. در گره 25 به سمت چپ سنگین است. همانطور که در شکل زیر نشان داده شده است، یک چرخش LL را انجام دهید تا به درخت AVL منجر شود.

پس از درج عدد 34، درخت در شکل زیر (د) نشان داده شده است. پس از درج 50، درخت مانند شکل زیر (ه) است. درخت متعادل نیست. در گره 25 به سمت راست سنگین است. همانطور که در شکل زیر (f) نشان داده شده است، یک چرخش RR را انجام دهید تا یک درخت AVL ایجاد شود.

پس از درج 30، درخت مانند شکل زیر (g) است. درخت متعادل نیست. همانطور که در شکل زیر نشان داده شده است، یک چرخش RL را انجام دهید تا یک درخت AVL ایجاد شود.

پس از درج 10، درخت مانند شکل زیر (i) است. درخت متعادل نیست. همانطور که در شکل زیر نشان داده شده است، یک چرخش LR را انجام دهید تا به درخت AVL منجر شود.

شکل زیر نشان می دهد که چگونه درخت با حذف عناصر تکامل می یابد. پس از حذف 34، 30 و 50، درخت مانند شکل زیر (ب) است. درخت متعادل نیست. همانطور که در شکل زیر نشان داده شده است، یک چرخش LL را انجام دهید تا یک درخت AVL ایجاد شود.

پس از حذف 5، درخت مانند شکل زیر (d) است. درخت متعادل نیست. همانطور که در شکل زیر نشان داده شده است، یک چرخش RL انجام دهید تا یک درخت AVL ایجاد شود.