AVL balancing factors

[melissak0421]

Ok, so I have an assignment to modify a previous assignment (binary tree) to now include balancing at each node. I understand what balancing is as far as if right side minus left side equals balancing factor of that node, and if the balancing factor of the node is < -1 and > 1 one or two rotations need to take place. But I'm not sure how to implement it. Any insight is much appreciated!

[melissak0421]

here's what I have so far for getting the balancing factors, but I' not sure how to implement the rotations inside the final if statement.

template <typename T>
void BSearch <T> ::BFactors (Node <T> *& r)
{
	Node <T> front = r;
	Node <T> temp = r;
	int rHeight;
	int lHeight;

	while ( temp -> right != NULL)
	{
			rHeight ++;
			temp = temp->right;
	}

	temp = front;

	while (temp->left != NULL)
	{
		lHeight ++;
		temp = temp -> left;
	}

	if (( rHeight - lHeight) > 1 || (rHeight - lHeight) < -1)
	{
		
		



	}

	BSearch (r->left);
	BSearch (r->right);
}

[ne555]

int rHeight; //you need to initialise the variable
while ( temp -> right != NULL)
{
	rHeight ++;
	temp = temp->right; //only to the rigth. Is that correct?
}

http://en.wikipedia.org/wiki/Tree_rotation#Detailed_Illustration