Testing the AVLTree Class

This section gives an example of using the AVLTree class. The code below gives a test program. The program creates an AVLTree initialized with an array of the integers 25, 20, and 5 (lines 7), inserts elements in lines 11–20, and deletes elements in lines 24–30. Since AVLTree is a subclass of BST and the elements in a BST are iterable, the program uses a foreach loop to traverse all the elements in lines 35–37.

package demo;

public class TestAVLTree {

    public static void main(String[] args) {
        // Create an AVL tree
        AVLTree<Integer> 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

Figure below shows how the tree evolves as elements are added to the tree. After 25 and 20 are added, the tree is as shown in Figure below (a). 5 is inserted as a left child of 20, as shown in Figure below (b). The tree is not balanced. It is left-heavy at node 25. Perform an LL rotation to result in an AVL tree, as shown in Figure below (c).

After inserting 34, the tree is shown in Figure below (d). After inserting 50, the tree is as shown in Figure below (e). The tree is not balanced. It is right-heavy at node 25. Perform an RR rotation to result in an AVL tree, as shown in Figure below (f).

After inserting 30, the tree is as shown in Figure below (g). The tree is not balanced. Perform an RL rotation to result in an AVL tree, as shown in Figure below (h).

After inserting 10, the tree is as shown in Figure below (i). The tree is not balanced. Perform an LR rotation to result in an AVL tree, as shown in Figure below (j).

Figure below shows how the tree evolves as elements are deleted. After deleting 34, 30, and 50, the tree is as shown in Figure below (b). The tree is not balanced. Perform an LL rotation to result in an AVL tree, as shown in Figure below (c).

After deleting 5, the tree is as shown in Figure below (d). The tree is not balanced. Perform an RL rotation to result in an AVL tree, as shown in Figure below (e)