Implementing an AVL Self-Balancing Binary Search Tree in Java

In computer science, an AVL tree is a self‑balancing binary search tree named after its inventors G.M. Adelson‑Velsky and E.M. Landis; it guarantees that the height difference between the left and right subtrees of any node is at most one, ensuring good performance for insertions and deletions.

Implementing an AVL tree in Java can be broken down into several steps.

Step 1: Define the node class. The node class stores the data element, references to left and right children, and the node height, and implements Comparable to allow ordering based on the data value.

public class Node implements Comparable
{
    int data;
    Node left, right;
    int height;

    public Node(int data) {
        this.data = data;
        left = right = null;
        height = 1;
    }

    @Override
    public int compareTo(Node other) {
        return this.data - other.data;
    }
}

Step 2: Define the AVL tree class. The AVLTree class maintains a reference to the root node and provides helper methods for obtaining a node’s height, computing its balance factor, and performing left and right rotations to restore balance after modifications.

public class AVLTree {
    Node root;

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        } else {
            return node.height;
        }
    }

    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        } else {
            return getHeight(node.left) - getHeight(node.right);
        }
    }

    private Node rightRotate(Node node) {
        Node newRoot = node.left;
        node.left = newRoot.right;
        newRoot.right = node;
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        newRoot.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        return newRoot;
    }

    private Node leftRotate(Node node) {
        Node newRoot = node.right;
        node.right = newRoot.left;
        newRoot.left = node;
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        newRoot.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        return newRoot;
    }
}