1. Introduction

An AVL Tree (Adelson-Velsky and Landis tree) is a self-balancing binary search tree. In an AVL tree, the height difference between the left and right subtree (balance factor) for every node is either -1, 0, or 1. If this balance factor becomes less than -1 or more than 1 after any operation like insertion or deletion, rotations are used to rebalance the tree. This post will demonstrate the implementation of an AVL tree in Java and cover the insertion operation and in-order traversal.

2. Program Steps

1. Define the Node class, which will represent individual elements of the AVL Tree.

2. Create an AVLTree class that includes methods for insertion and in-order traversal.

3. Implement the AVL rotations and balancing.

4. Test the AVLTree with multiple insertion operations and perform an in-order traversal.

3. Code Program

// Step 1: Define the Node class
class Node {
    int key, height;
    Node left, right;

    Node(int d) {
        key = d;
        height = 1;
    }
}

class AVLTree {
    Node root;

    // A utility function to get the height of the tree
    int height(Node N) {
        if (N == null) return 0;
        return N.height;
    }

    // A utility function to get maximum of two integers
    int max(int a, int b) {
        return (a > b) ? a : b;
    }

    // A utility function to right rotate subtree rooted with y
    Node rightRotate(Node y) {
        Node x = y.left;
        Node T3 = x.right;

        x.right = y;
        y.left = T3;

        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        return x;
    }

    // A utility function to left rotate subtree rooted with x
    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;

        return y;
    }

    // Get Balance factor of node N
    int getBalance(Node N) {
        if (N == null) return 0;
        return height(N.left) - height(N.right);
    }

    Node insert(Node node, int key) {
        if (node == null) return (new Node(key));

        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        } else return node;

        node.height = 1 + max(height(node.left), height(node.right));

        int balance = getBalance(node);

        if (balance > 1 && key < node.left.key) return rightRotate(node);

        if (balance < -1 && key > node.right.key) return leftRotate(node);

        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // A utility function to print in-order traversal of the tree
    void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.key + " ");
            inOrder(node.right);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 25);

        System.out.println("In-order traversal of the AVL tree is:");
        tree.inOrder(tree.root);
    }
}

Output:

In-order traversal of the AVL tree is:
10 20 25 30 40 50

4. Step By Step Explanation

Step 1: The Node class represents individual elements of the AVL tree. Each node contains a key, height, and pointers to its left and right child.

Step 2: The AVLTree class provides:

1. Utility functions for tree height, maximum value, and rotation operations.

2. insert: Inserts a new node into the AVL tree and ensures it remains balanced.

3. inOrder: A method for in-order traversal.

Step 3: Implement rotations and balancing to ensure the AVL property is maintained after every insertion.

Step 4: The Main class tests the AVL tree by inserting several nodes and then prints the in-order traversal of the tree. The AVL tree ensures that the tree remains balanced after each insertion operation.

The output displays the AVL tree nodes in ascending order due to the in-order traversal.