tarlanahad

class Node {

    Node Left, Right, Parent;

    int Key;

    Node(int Key) {
        this.Key = Key;
    }

tarlanahad

public class AVL_Trees<AnyType> {

    private Node Root;
    private int CurrentSize = 0;

    public AVL_Trees() {
    }
}

tarlanahad

private void addHelper(Node parentPosition, Node newNode) {

        if (newNode.Key > parentPosition.Key) {// newNode's key is greater
                                       //than that of parent node go right

            if (parentPosition.Right == null) {//If the node is leaf
                parentPosition.Right = newNode;//append newNode to its Right
                newNode.Parent = parentPosition;//newNode's parent
                CurrentSize++;//increment tree's size
            } else {

tarlanahad

 public void add(int Key) {

        Node newNode = new Node(Key);

        if (Root == null) {
            Root = newNode;
            CurrentSize++;
            return;
        }
        addHelper(Root, newNode);

tarlanahad

private void CheckBalance(Node newNode) {

   if (Math.abs(height(newNode.Left) - height(newNode.Right)) > 1) {//if difference between children's height gre. than 1
            ReBalance(newNode);//rebalance
   }

   if (newNode.Parent == null) return;//if we are on in the root 

   CheckBalance(newNode.Parent);//otherwise, check top levels
}

tarlanahad

 private void ReBalance(Node node) {
        if (height(node.Left) - height(node.Right) > 1) {//if the problem in the left subtree

            if (height(node.Left.Left) > height(node.Left.Right)) //if the problem in the left subtree
                node = RightRotate(node);//do right subtree
            else
                node = LeftRightRotate(node);

        } else {

tarlanahad

private Node LeftRotate(Node grandParentNode) {
    Node temp = grandParentNode.Right;
    grandParentNode.Right = temp.Left;
    temp.Left = grandParentNode;
    return temp;
}

tarlanahad

private Node RightRotate(Node grandParentNode) {
    Node temp = grandParentNode.Left;
    grandParentNode.Left = temp.Right;
    temp.Right = grandParentNode;
    return temp;
}

tarlanahad

private Node RightLeftRotate(Node grandParentNode) {
    grandParentNode.Right = RightRotate(grandParentNode.Right);
    return LeftRotate(grandParentNode);
  }

private Node LeftRightRotate(Node grandParentNode) {
    grandParentNode.Left = LeftRotate(grandParentNode.Left);
    return RightRotate(grandParentNode);
}
    

tarlanahad

   private static int getMax(int arr[]) {
       int max = arr[0];
       for (int num : arr) {
           if (num > max) max = num;
       }
       return max;
   }


   private static void sort(int[] a) {