AVL Tree Rotation Problem

[maikens]

Hi all,

I'm working on a project in my Data Structures course, using Binary Search Trees. As part of the project, we need to balance the tree. I have decided to try and make an AVL tree. I am having a problem with the rotations in particular. Somehow during the rotation of the tree, I am losing a node (I suspect it's a misplaced pointer). I was hoping someone could pick out my problem. Here is my method for balancing the tree, as well as the 4 rotation methods

void BST::BalanceTree(NodePtr &node) // pass in root node
{
	// Balance factor cannot be greater than 1 or less than -1. If so, one or more rotations are required.

	if(node == NULL) // reached leaf - exit recursive function
	{
		return;
	}	

	if( (GetHeight(node->right)) - (GetHeight(node->left)) > 1) // right subtree is longer
	{
		if( (GetHeight(node->right->right)) - (GetHeight(node->right->left)) < 1 ) // left side of subtree is longer
		{
			DoubleLeftRotation(node);
		}
		else // right side is longer
		{
			SingleLeftRotation(node);
		}
	}
	else if ( (GetHeight(node->left)) - (GetHeight(node->right)) > 1) // left subtree is longer
	{
		if( (GetHeight(node->left->right)) - (GetHeight(node->left->left)) < 1) // right side of subtree is longer
		{
			DoubleRightRotation(node);
		}
		else // left side is longer
		{
			SingleRightRotation(node);
		}
	}

	// Set node's height
	// node->height = max(GetHeight(root->left), GetHeight(root->right)) +1;

	// Check recursively from left to right
	BalanceTree(node->left);
	BalanceTree(node->right);
}

NodePtr BST::SingleLeftRotation(NodePtr &node)
{
	// Create node to facilitate rotation of subtree
    NodePtr pivot = NULL;

	// Switch around pointers so the passed in node is rotated 
    pivot = node->right;
    node->right = pivot->left;
    pivot->left = node;

    // Update heights of passed in node and returned node
    node->height = max(GetHeight(pivot->left),GetHeight(pivot->right))+1;
	pivot->height = max(node->height, GetHeight(pivot->right)) +1;

	// In case method is being called inside DoubleLeftRotation, return pivot
    return pivot;
}

NodePtr BST::SingleRightRotation(NodePtr &node)
{
    NodePtr pivot = NULL;

    pivot = node->left;
    node->left = pivot->right;
    pivot->right = node;

    node->height = max(GetHeight(node->left), GetHeight(node->right)) +1;
    pivot->height = max(node->height, GetHeight(pivot->left)) +1;

    return pivot;
}

void BST::DoubleLeftRotation(NodePtr &node)
{
    // Do a right rotation on right subtree
    node = SingleRightRotation(node->right);
    // Then use single left rotation to finish balancing tree
    node = SingleLeftRotation(node);
}

void BST::DoubleRightRotation(NodePtr &node)
{
    node = SingleLeftRotation(node->left);
    node = SingleRightRotation(node);
}

I am fairly certain the problem is in the single rotation functions.

Thanks!