Avls.java

class AVLNode {
    int data;
    AVLNode left;
    AVLNode right;
    int height;

    AVLNode(int value) {
        this.data = value;
        this.height = 1;
    }
}

class AVLTree {
    AVLNode root;

    int height(AVLNode node) {
        if (node == null) return 0;
        return node.height;
    }

    int balancing(AVLNode node) {
        if (node == null) return 0;
        return height(node.left) - height(node.right);
    }

    AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode c = x.right;

        x.right = y;
        y.left = c;

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

        return x;
    }

    AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode c = y.left;

        y.left = x;
        x.right = c;

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

        return y;
    }

    AVLNode insert(AVLNode node, int value) {
        if (node == null) {
            return new AVLNode(value);
        }

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

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

        int blnc = balancing(node);

        if (blnc > 1 && value < node.left.data) {
            return rightRotate(node);
        }

        if (blnc < -1 && value > node.right.data) {
            return leftRotate(node);
        }

        if (blnc > 1 && value > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (blnc < -1 && value < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    void insert(int value) {
        root = insert(root, value);
    }

    AVLNode minVal(AVLNode node) {
        AVLNode curr = node;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    }

    AVLNode deleteNode(AVLNode root, int value) {
        if (root == null) {
            return root;
        }

        if (value < root.data) {
            root.left = deleteNode(root.left, value);
        } else if (value > root.data) {
            root.right = deleteNode(root.right, value);
        } else {
            if ((root.left == null) || (root.right == null)) {
                AVLNode tmp = null;
                if (tmp == root.left) {
                    tmp = root.right;
                } else {
                    tmp = root.left;
                }

                if (tmp == null) {
                    tmp = root;
                    root = null;
                } else {
                    root = tmp;
                }
            } else {
                AVLNode temp = minVal(root.right);
                root.data = temp.data;
                root.right = deleteNode(root.right, temp.data);
            }
        }

        if (root == null) {
            return root;
        }

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

        int blnc = balancing(root);

        if (blnc > 1 && balancing(root.left) >= 0) {
            return rightRotate(root);
        }

        if (blnc > 1 && balancing(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        if (blnc < -1 && balancing(root.right) <= 0) {
            return leftRotate(root);
        }

        if (blnc < -1 && balancing(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }

    void delete(int value) {
        root = deleteNode(root, value);
    }

    boolean search(AVLNode root, int value) {
        if (root == null) {
            return false;
        }
        if (value == root.data) {
            return true;
        }
        else if (value < root.data) {
            return search(root.left, value);
        }
        else {
            return search(root.right, value);
        }
    }

    boolean search(int value) {
        return search(root, value);
    }

    void inorder(AVLNode root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    void inorder() {
        inorder(root);
        System.out.println();
    }


    int findMax(AVLNode root) {
        if (root == null) return -1;
        while (root.right != null) {
            root = root.right;
        }
        return root.data;
    }
    int findMax() {
        return findMax(root);
    }


    int countNodes(AVLNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    int countNodes() {
        return countNodes(root);
    }


}

public class Avls {

    public static void main(String[] args) {
        AVLTree avl = new AVLTree();
        avl.insert(6);
        avl.insert(2);
        avl.insert(3);
        avl.insert(5);
        avl.inorder();
        avl.delete(5);
        avl.delete(3);
        avl.inorder();
        System.out.println(avl.findMax());
        System.out.println(avl.countNodes());
        avl.insert(8);
        avl.insert(11);
        avl.insert(9);
        avl.inorder();
        System.out.println(avl.search(2));
        System.out.println(avl.countNodes());
    }
}