package classes;

public class SelfBalancingTree {

    private NodeTwo root;

    private int svd = -1;
    private int size;

    public SelfBalancingTree(int size) {
        this.size = size;
    }

    public int height(NodeTwo N) {
        if (N == null)
            return 0;

        return N.height;
    }

    // A utility function to get maximum of two integers
    public int max(int a, int b) {
        return (a > b) ? a : b;
    }

    // A utility function to right rotate subtree rooted with y
    // See the diagram given above.
    public NodeTwo rightRotate(NodeTwo y) {
        NodeTwo x = y.left;
        NodeTwo T2 = x.right;

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

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

        // Return new root
        return x;
    }

    // A utility function to left rotate subtree rooted with x
    // See the diagram given above.
    public NodeTwo leftRotate(NodeTwo x) {
        NodeTwo y = x.right;
        NodeTwo T2 = y.left;

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

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

        // Return new root
        return y;
    }

    // Get Balance factor of NodeTwo N
    public int getBalance(NodeTwo N) {
        if (N == null)
            return 0;

        return height(N.left) - height(N.right);
    }

    public int insert(int value) {
        root = insert(root, value);
        if (svd != -1) return svd;
        return -1;
    }

    public NodeTwo insert(NodeTwo node, int key) {
        if (node == null)
            return (new NodeTwo(key));

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else {
            node.count += 1;
            if (node.count > (size / 2)) svd = node.key;
            return node;
        }
        /* 2. Update height of this ancestor NodeTwo */
        node.height = 1 + max(height(node.left),
                height(node.right));

        /* 3. Get the balance factor of this ancestor
              NodeTwo to check whether this NodeTwo became
              unbalanced */
        int balance = getBalance(node);

        // If this NodeTwo becomes 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 the (unchanged) NodeTwo pointer */
        return node;
    }
}
package classes;

public class NodeTwo {

    public int key, height;
    public NodeTwo left, right;
    public int count;

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