Trying to implement an AVL tree in C++. I have programmed the single rotation cases for if the tree is left-left heavy and right-right heavy but it is doing multiple rotations because my balance( n ) method is incorrect but I don't know how to solve it any other way

void AVLTree::insert(AVLNode*& n , const string& x){ if (n -> value > x) { if(n -> left == NULL){ AVLNode* node = new AVLNode(); node -> value = x; n -> left = node; balance(n); } else { insert(n -> left , x); balance(n); } }

else if (n -> value < x) { if(n -> right == NULL){ AVLNode* node = new AVLNode(); node -> value = x; n -> right = node; balance(n); } else { insert(n ->right, x); balance(n); } }

balance(n); int diff = height(n -> right) - height(n-> left); cout << n->value << diff << endl;

// if (diff > 1 && n -> left != NULL && x > n -> left -> value) n=rotateRight(n); // if (diff < -1 && n -> right != NULL && x > n -> right -> value)n= rotateRight(n);

}

// balance makes sure that the subtree with root n maintains the AVL tree // property, namely that the balance factor of n is either -1, 0, or 1. void AVLTree::balance(AVLNode*& n) { int diff = height(n -> right) - height(n-> left); if (diff > 1 && height(n -> right) > 0 ) n = rotateLeft(n); else if (diff < -1 && height(n -> left) > 0 ) n = rotateRight(n);

n->height = 1 + max(height(n->left), height(n->right)); }

// rotateLeft performs a single rotation on node n with its right child. AVLNode* AVLTree::rotateLeft(AVLNode*& n) { cout << "rotatee left " << n -> value << endl;

AVLNode * newRoot = n -> right; n -> right = root -> left; newRoot -> left = n;

n->height = max(height(n->left), height(n->right)) +1 ; newRoot -> height = max(height(newRoot -> right), n -> height) +1; return newRoot; }

// rotateRight performs a single rotation on node n with its left child. AVLNode* AVLTree::rotateRight(AVLNode*& n) {

AVLNode * newRoot = n -> left; n -> left = root -> right; newRoot -> right = n; n->height = max(height(n->left), height(n->right)) +1 ; newRoot -> height = max(height(newRoot -> left), n -> height) +1;

return newRoot; }