AVL Tree balance problem

[reignreborn1335]

Hello I'm new here and I need a little help. I have written and AVL tree class and I think my logic is wrong for balancing the tree after insert or deletion. I think it only computes the height and balance factors for the root and its immediate children instead of the entire tree. Can someone help me? I can provide the full class if needed.

//-------------INSERT NODE----------------//

template<class Ktype, class Vtype> //done
void AVLTree<Ktype, Vtype>::insertNode(Ktype key, Vtype value){
    AVLNode *p = root, *parent = 0;
	while(p!=0) {
		parent = p;
		if (key < p->key){
			p = p->left;
		}
		else {
			p = p->right;
		}
	}

	if (root == 0){
		root = new AVLNode(key, value);
	}
	else if (key < parent->key) {
		parent->left = new AVLNode(key, value);
		parent->left->height = 0;
        findBalance(root);
	}
	else {
		parent->right = new AVLNode(key, value);
		parent->right->height = 0;
	}
	findBalance(root);
	balanceTree(root);
};

//--------------DELETE NODE-----------------//

template<class Ktype, class Vtype> // done?
void AVLTree<Ktype, Vtype>::findAndDelete(Ktype key){
	AVLNode *node = root, *parent = 0;
	while (node != 0) {
		if (node->key == key) {
			break;
		}
		parent = node;
		if (key < node->key) {
			node = node->left;
		}
		else {
			node = node->right;
		}
	}
	if (node != 0 && node->key == key) {
		if (node == root) {
			deleteNode(root);
			cout << "Deleted Key: " << key << endl;
		}
		else if (parent->left == node) {
			deleteNode(parent->left);
			cout << "Deleted Key: " << key << endl;
		}
		else {
			deleteNode(parent->right);
			cout << "Deleted Key: " << key << endl;
		}
	}
	else if (root != 0) {
		cout << "Key not found!" << endl;
	}
	else {
		cout << "Tree is empty." << endl;
	}
};

template<class Ktype, class Vtype> // done?
void AVLTree<Ktype, Vtype>::deleteNode(AVLNode*& node){
	AVLNode *parent, *tmpNode = node;
	if (node->right == 0) {
		node = node->left;
	}
	else if (node->left == 0) {
		node = node->right;
	}
	else {
		tmpNode = node->left;
		parent = node;
		while (tmpNode->right != 0) {
			parent = tmpNode;
			tmpNode = tmpNode->right;
		}
		node->key = tmpNode->key;
		if (parent == node) {
			parent->left = tmpNode->left;
		}
		else {
			parent->right = tmpNode->left;
		}
	}
	delete tmpNode;
        findBalance(root);
        balanceTree(root);
};

//----------------BALANCING--------------------//

template<class Ktype, class Vtype> //done
void AVLTree<Ktype, Vtype>::findBalance(AVLNode* node){
    int leftHeight, rightHeight;	
    if (node) {
		if (node->left){
			leftHeight = node->left->height;
		}
		else {
			leftHeight = 0;
		}
		if (node->right) {
			rightHeight = node->right->height;
		}
		else {
			rightHeight = 0;
		}
	}

	if (leftHeight > rightHeight){
		node->height = 1 + leftHeight;
	}
	else {
		node->height = 1 + rightHeight;
	}

	node->bfactor = rightHeight - leftHeight;
};

template<class Ktype, class Vtype> //done
void AVLTree<Ktype, Vtype>::balanceTree(AVLNode*& node){
	if (node->bfactor > 1){
		rightBalance(node);
	}
	else if (node->bfactor < -1){
		leftBalance(node);
	}
};

template<class Ktype, class Vtype> // done
void AVLTree<Ktype, Vtype>::rightBalance(AVLNode*& node){
	if (node->right)
	{
		if (node->right->bfactor > 0) leftRotate(node);
		else if (node->right->bfactor < 0)
		{
			rightRotate(node->right);
			leftRotate(node);
		}
	}
};

template<class Ktype, class Vtype> // done
void AVLTree<Ktype, Vtype>::leftBalance(AVLNode*& node){
	if (node->left)
	{
		if (node->right->bfactor > 0) rightRotate(node);
		else if (node->right->bfactor < 0)
		{
			leftRotate(node->right);
			rightRotate(node);
		}
	}
};

template<class Ktype, class Vtype>
void AVLTree<Ktype, Vtype>::leftRotate(AVLNode*& node){
	AVLNode *tmpNode = node;
	node = node->left;
	tmpNode->left = node->right;
	node->right = tmpNode;
	findBalance(node->left);
	findBalance(node->right);
	findBalance(node);
};

template<class Ktype, class Vtype>
void AVLTree<Ktype, Vtype>::rightRotate(AVLNode*& node)
{
	AVLNode* tmpNode = node;
	node = node->left;
	tmpNode->left = node->right;
	node->right = tmpNode;

	findBalance(node->left);
	findBalance(node->right);
	findBalance(node);
};

[WingedPanther]

I'm a little bit confused: what does key represent? When dealing with an AVLTree, I would only have one template parameter for the value to be stored. (I know, I need to get my AVLTree tutorial completed, but I'm lazy.)

Your problem is that you aren't remeasuring the heights after an insert/delete. You may want to create a linked list of nodes as you perform an insert/delete so that you can work back up the path you took to remeasure the heights and determine if you need to rebalance at a node (possibly not root for deletes).