AVL Tree Implementation in Java

1. Introduction

An AVL Tree (Adelson-Velsky and Landis Tree) is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for every node is not more than one. This ensures that the AVL tree remains approximately balanced, leading to O(log n) time for search, insert, and delete operations. The balancing is maintained by rotating the nodes whenever an imbalance is detected.

2. Implementation Steps

1. Define a Node class to represent individual elements of the AVL Tree. This class should also store the height of the node for balancing purposes.

2. Define an AVLTree class which will:

a. Maintain a reference root pointing to the start of the tree.

b. Provide methods such as insert(), delete(), and inOrderTraversal().

c. Include rotation methods to keep the tree balanced: rightRotate(), leftRotate(), getBalance().

3. Implement these methods to manage the AVL Tree.

4. Showcase the AVL tree's functionality in a main() method.

3. Implementation in Java

class Node {
    int data, height;
    Node left, right;
    Node(int data) {
        this.data = data;
        height = 1;  // New nodes are added at leaf
    }
}
class AVLTree {
    Node root;
    // A utility function to get height of the tree
    int height(Node node) {
        return (node == null) ? 0 : node.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) {
        return (N == null) ? 0 : height(N.left) - height(N.right);
    }
    public Node insert(Node node, int data) {
        if (node == null) {
            return (new Node(data));
        }
        if (data < node.data) {
            node.left = insert(node.left, data);
        } else if (data > node.data) {
            node.right = insert(node.right, data);
        } else {
            return node;  // Duplicate data not allowed
        }
        node.height = 1 + max(height(node.left), height(node.right));
        int balance = getBalance(node);
        // Left Left Case
        if (balance > 1 && data < node.left.data) {
            return rightRotate(node);
        }
        // Right Right Case
        if (balance < -1 && data > node.right.data) {
            return leftRotate(node);
        }
        // Left Right Case
        if (balance > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // Right Left Case
        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }
    // Inorder traversal of the tree
    void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.data + " ");
            inOrderTraversal(node.right);
        }
    }
    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("Inorder traversal of AVL tree is:");
        tree.inOrderTraversal(tree.root);
    }
}

Output:

Inorder traversal of AVL tree is:
10 20 25 30 40 50

Explanation:

1. The Node class represents each node of the AVL tree. Each node has an integer data, a height value, and references to its left and right children.

2. The AVLTree class houses the root reference marking the starting point of the tree and utility functions like height(), max(), rightRotate(), leftRotate(), and getBalance().

3. The insert() method ensures the insertion of new nodes while maintaining the balance of the tree.

4. The balancing of the tree is handled by the rotation methods (rightRotate(), leftRotate()) that get triggered upon detecting an imbalance.

5. The inOrderTraversal() method offers a way to traverse and print the tree in an in-order manner.

6. In the main() method, we instantiate an AVLTree, insert integer values, and then showcase the in-order traversal of the tree.