AVL Tree

    Node* rotateR(Node* n) {
        n->left->right = n;
        Node* temp = n->left;
        n->left = NULL;
        return temp;
    }

    Node* rotateL(Node* n) {
        n->right->left = n;
        Node* temp = n->right;
        n->right = NULL;
        return temp;
    }

    Node* balance(Node* n)
    {
        if(!n) return n;
        int factor = setHeight(n->left)-setHeight(n->right);
        if(factor < -1) {
            int subfactor = setHeight(n->right->left)-setHeight(n->right->right);
            if(subfactor<=0) return rotateL(n);
            else if(subfactor==1) {
                n->right = rotateR(n->right);
                return rotateL(n);
            }
        }
        else if (factor > 1) {
            int subfactor = setHeight(n->left->left)-setHeight(n->left->right);
            if(subfactor>=0) n = rotateR(n);
            else if(subfactor==-1) {
                n->left = rotateL(n->left);
                return rotateR(n);
            }
        }
        checkHeights(root);
        return n;
    }

    void insert(ItemType item)
    {
        root = insert(root, item);
        cout << "After setting root:  " << endl; print(cout);
    }

    Node* insert(Node* t, const ItemType& item)
    {
        checkHeights(t);
        if(t==NULL)
        {
            Node* newNode = new Node(item);
            if(size==0)
            {
                root = newNode;
                cout << "Root was successfully set." << endl;
            }
            size++;
            return newNode;
        }
        else if (item< t->item)
        {
            t->left = insert(t->left, item);
        }
        else if (item> t->item)
        {
            t->right = insert(t->right, item);
        }
        cout << "Before balancing: " << endl; print(cout);
        t = balance(t);
        checkHeights(t);
        return t;
    }