AVL Trees in Java: Mastering Self-Balancing Binary Search Trees

A Binary Search Tree (BST) is a powerful data structure, but it has a fatal flaw: if elements are inserted in sorted order, it degenerates into a linked list, turning $O(\log N)$ operations into $O(N)$.

The AVL Tree (named after Adelson-Velsky and Landis) was the first self-balancing BST ever invented to solve this exact problem.

The Core Concept: The Balance Factor

In an AVL tree, the heights of the two child subtrees of any node differ by at most one.

$$\text{Balance Factor} = \text{Height}(\text{Left Subtree}) - \text{Height}(\text{Right Subtree})$$

A node is considered balanced if its balance factor is -1, 0, or 1. If it falls outside this range, the tree must be rebalanced using rotations.

The Four Rotation Types

When an insertion or deletion causes an imbalance, we apply one of four rotations:

1. Left-Left (LL) Case: Right rotation.
2. Right-Right (RR) Case: Left rotation.
3. Left-Right (LR) Case: Left rotation on the child, then right rotation on the parent.
4. Right-Left (RL) Case: Right rotation on the child, then left rotation on the parent.

AVL Tree Implementation in Java

class Node {
    int key, height;
    Node left, right;

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

public class AVLTree {
    Node root;

    // Get height of the node
    int height(Node N) {
        if (N == null) return 0;
        return N.height;
    }

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

    // Right rotate subtree rooted with y
    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T2;

        // Update heights
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    // Left rotate subtree rooted with x
    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    public Node insert(Node node, int key) {
        // 1. Perform standard BST insertion
        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;

        // 2. Update height of this ancestor node
        node.height = 1 + Math.max(height(node.left), height(node.right));

        // 3. Get the balance factor
        int balance = getBalance(node);

        // 4. If unbalanced, then there are 4 cases

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

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

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

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

        return node;
    }
}

AVL Tree vs. Red-Black Tree

Summary

AVL Trees are the gold standard for maintaining optimal search performance in dynamic datasets. While they require more overhead during updates compared to Red-Black trees, their strict balancing guarantees that you will never face the $O(N)$ worst-case scenario of a standard BST. Mastering AVL rotations is a classic way to demonstrate your proficiency with recursive data structures in any technical interview.