**fig4_38.txt**

/* 1*/	template <class Etype>
/* 2*/	void
/* 3*/	Avl_Tree<Etype>::
/* 4*/	Insert( const Etype & X, Avl_Node<Etype> * & T )
/* 5*/	{
/* 6*/	    if( T == NULL )	// Create a one node tree.
/* 7*/	    {
/* 8*/	        T = new Avl_Node<Etype>( X );
/* 9*/	        if( T == NULL )
/*10*/	            Error( "Out of space" );
/*11*/	        return;
/*12*/	    }

/*13*/	    if( X < T->Element )
/*14*/	    {
/*15*/	        Insert( X, ( Avl_Node<Etype> * & ) T->Left );
/*16*/	        if( Node_Ht( T->Left ) - Node_Ht( T->Right ) == 2 )
/*17*/	            if( X < ( ( Avl_Node<Etype> * ) T->Left )->Element )
/*18*/	                S_Rotate_Left( T );
/*19*/	            else
/*20*/	                D_Rotate_Left( T );
/*21*/	        else
/*22*/	            Calculate_Height( T );
/*23*/	    }
/*24*/	    else
/*25*/	    if( X > T->Element )
/*26*/	    {
/*27*/	        Insert( X, ( Avl_Node<Etype> * & ) T->Right );
/*28*/	        if( Node_Ht( T->Right ) - Node_Ht( T->Left ) == 2 )
/*29*/	            if( X > ( ( Avl_Node<Etype> * ) T->Right )->Element )
/*30*/	                S_Rotate_Right( T );
/*31*/	            else
/*32*/	                D_Rotate_Right( T );
/*33*/	        else
/*34*/	            Calculate_Height( T );
/*35*/	    }
/*36*/	    // Else x is in the tree already, so we'll do nothing.
/*37*/	}