/**
 * Balance the tree, takes O(n) time
 */
template <class T, typename Compare, typename Distance>
void AvlTree<T,Compare, Distance>::balanceTree(AvlNode<T,Compare, Distance>* &node)
{
	if ( node )
	{
		// First see what the balance factor for this node is
		//
		int balFactor = node->balanceFactor();

		if ( balFactor < -1 )
		{
			// See if we're heavy left of the left
			//
			if(  node->left->balanceFactor() < 0 )
			{
				rotateWithLeftChild( node );
			}
			else // if (node->left->balanceFactor() > 0 )
			{
				// We're heavy on the right of the left
				//
				doubleWithLeftChild( node );
			}
		}
		else if ( balFactor > 1 )
		{
			// See if it we're heavy right of the right
			//
			if( node->right->balanceFactor() > 0 )
			{
				rotateWithRightChild( node );
			}
			else // if ( node->right->balanceFactor() < 0 )
			{
				// The element goes on the left of the right
				//
				doubleWithRightChild( node );
			}
		}
		else // if ( balFactor >= -1 && balFactor <= 1)
		{
			// We're balanced here, but are our children balanced?
			//
			balanceTree(node->left);
			balanceTree(node->right);
		}
	}
}