package ThirdWork class Node public int key public int height public N

package ThirdWork;

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

    public Node(int key) {
        this.key = key;
        height = 1;
    }

}

public class AVLTree {
    private Node root;

    public AVLTree() {
        root = null;
    }


    public Node getRoot() {
        return root;
    }


    public Node find(int key, Node root) {

        if (root == null)
            return null;
        else if (root.key == key)
            return root;
        else if (root.key < key)
            return find(key, root.right);
        else
            return find(key, root.left);


    }


    public int height(Node x) {
        if (x == null) return 0;
        else return x.height;
    }

    private Node rotateRight(Node p) {

        Node q = p.left;
        p.left = q.right;
        q.right = p;

        fixHeight(p);
        fixHeight(q);

        return q;

    }

    private Node rotateLeft(Node q) {

        Node p = q.right;
        q.right = p.left;
        p.left = q;

        fixHeight(q);
        fixHeight(p);

        return p;

    }


    public void insert(int key) {
        if (root == null)
            root = new Node(key);
        else {
            root = insert(root, key);
        }
    }

    private Node insert(Node p, int key) {
        if (p == null) return new Node(key);
        if (key < p.key) {
            p.left = insert(p.left, key);
        }
        else {
            p.right = insert(p.right, key);
        }
        return balance(p);
    }

    private Node findMin(Node p) {
        return p.left == null ? p : findMin(p.left);
    }

    private Node removeMin(Node p) {
        if (p.left == null) {
            return p.right;
        }
        p.left = removeMin(p.left);
        return balance(p);
    }


    public void remove(int key) {
        remove(root, key);
    }

    private Node remove(Node p, int key) {
        if (p == null) return null;

        if (key < p.key) {
            p.left = remove(p.left, key);
        }
        else if (key > p.key){
            p.right = remove(p.right, key);
        }
        else {
            Node q = p.left;
            Node r = p.right;
            p = null;
            if (r == null) return q;
            Node min = findMin(r);
            min.right = removeMin(r);
            min.left = q;
            return balance(min);
        }
        return balance(p);
    }


    private Node balance(Node p) {
        fixHeight(p);
        if (balanceFactor(p) == 2) {
            if (balanceFactor(p.right) < 0) {
                p.right = rotateRight(p.right);
            }
            return rotateLeft(p);
        }
        if (balanceFactor(p) == -2 ){
            if (balanceFactor(p.left) > 0) {
                p.left = rotateLeft(p.left);
            }
            return rotateRight(p);
        }
        return p;
    }

    private void fixHeight(Node p) {
        p.height = Math.max(height(p.left), height(p.right)) + 1;
    }

    private int balanceFactor(Node p) {
        return height(p.right) - height(p.left);
    }

}