An AVL tree is a self-balancing binary search tree where the height difference between left and right subtrees (balance factor) is at most 1 for every node. This guide provides a full implementation in Java, including insertion, deletion, rotations, and traversals.

Node Structure

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    // Height of the node
    public int height() {
        return Math.max(
            left == null ? 0 : left.height(),
            right == null ? 0 : right.height()
        ) + 1;
    }

    // Height of left subtree
    public int leftHeight() {
        return left == null ? 0 : left.height();
    }

    // Height of right subtree
    public int rightHeight() {
        return right == null ? 0 : right.height();
    }

    // Left rotation
    private void leftRotate() {
        Node newNode = new Node(value);
        newNode.left = left;
        newNode.right = right.left;
        value = right.value;
        right = right.right;
        left = newNode;
    }

    // Right rotation
    private void rightRotate() {
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;
    }

    // Insert a node recursively
    public void add(Node node) {
        if (node == null) return;

        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

        // After insertion, check balance and rotate if needed
        if (rightHeight() - leftHeight() > 1) {
            // Right-right case: single left rotation
            if (right != null && right.leftHeight() > right.rightHeight()) {
                // Right-left case: right rotate child, then left rotate current
                right.rightRotate();
            }
            leftRotate();
        } else if (leftHeight() - rightHeight() > 1) {
            // Left-left case: single right rotation
            if (left != null && left.rightHeight() > left.leftHeight()) {
                // Left-right case: left rotate child, then right rotate current
                left.leftRotate();
            }
            rightRotate();
        }
    }

    // Find a node by value
    public Node search(int value) {
        if (value == this.value) return this;
        if (value < this.value && this.left != null) {
            return this.left.search(value);
        } else if (value > this.value && this.right != null) {
            return this.right.search(value);
        }
        return null;
    }

    // Find parent of a given value
    public Node searchParent(int value) {
        boolean isLeftParent = left != null && left.value == value;
        boolean isRightParent = right != null && right.value == value;
        if (isLeftParent || isRightParent) return this;

        if (value < this.value && left != null) {
            return left.searchParent(value);
        } else if (value > this.value && right != null) {
            return right.searchParent(value);
        }
        return null;
    }

    @Override
    public String toString() {
        return "Node [value=" + value + "]";
    }
}

AVL Tree Class

public class AVLTree {
    private Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }
        infixOrderRecursive(root);
    }

    private void infixOrderRecursive(Node node) {
        if (node == null) return;
        infixOrderRecursive(node.left);
        System.out.println(node.value);
        infixOrderRecursive(node.right);
    }

    public Node search(int value) {
        if (root == null) return null;
        return root.search(value);
    }

    public Node searchParent(int value) {
        if (root == null) return null;
        return root.searchParent(value);
    }

    // Delete a node
    public void deleteNode(int value) {
        if (root == null) return;

        Node target = search(value);
        if (target == null) return;

        // If the tree has only one node
        if (root.left == null && root.right == null) {
            root = null;
            return;
        }

        Node parent = searchParent(value);

        // Case 1: target is leaf
        if (target.left == null && target.right == null) {
            if (parent.left != null && parent.left.value == value) {
                parent.left = null;
            } else if (parent.right != null && parent.right.value == value) {
                parent.right = null;
            }
        }
        // Case 2: target has two children
        else if (target.left != null && target.right != null) {
            int minValue = deleteMinFromRightSubtree(target.right);
            target.value = minValue;
        }
        // Case 3: target has one child
        else {
            Node child = (target.left != null) ? target.left : target.right;
            if (parent == null) {
                root = child;
            } else if (parent.left == target) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }
    }

    // Helper: find and delete the minimum node in a subtree
    private int deleteMinFromRightSubtree(Node node) {
        Node current = node;
        while (current.left != null) {
            current = current.left;
        }
        int minValue = current.value;
        deleteNode(minValue);
        return minValue;
    }
}

Usage Example

public class Main {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        int[] values = {10, 20, 30, 40, 50, 25};
        for (int v : values) {
            tree.add(new Node(v));
        }

        System.out.println("In-order traversal:");
        tree.infixOrder();

        System.out.println("Deleting 30:");
        tree.deleteNode(30);
        tree.infixOrder();
    }
}

Key Points

• After each insertion, the add method checks the balance factor and performs rotations to maintain balance.
• The deletion method handles three cases: leaf node, node with one child, and node with two children.
• Rotations (left, right, left-right, right-left) are implemneted in the Node class and triggered automatically when imbalances are detected.