******** fig4.37 **********

	SEARCH_TREE
	insert( element_type x, SEARCH_TREE T )
	{
		return insert1( x, T, NULL );
	}

	SEARCH_TREE
	insert1( element_type x, SEARCH_TREE T, avl_ptr parent )
	{
		avl_ptr rotated_tree;

		if( T == NULL )
		{	/* Create and return a one-node tree */
			T = (SEARCH_TREE) malloc ( sizeof (struct avl_node) );
			if( T == NULL )
				fatal_error("Out of space!!!");
			else
			{
				T->element = x; T->height = 0;
				T->left = T->right = NULL;
			}
		}
		else
		{
			if( x < T->element )
			{
				T->left = insert1( x, T->left, T );
				if( (height( T->left ) - height( T->right )) == 2 )
				{
					if( x < T->left->element )
						rotated_tree = s_rotate_left( T );
					else
						rotated_tree = d_rotate_left( T );
					if( parent->left == T )
						parent->left = rotated_tree;
					else
						parent->right = rotated_tree;
				}
				else
					T->height=max(height(T->left),height(T->right))+1;
			}
			else
				/* Symmetric Case for right subtree */;
			/* Else x is in the tree already. We'll do nothing */
		}
	
		return T;
	}