**fig4_36.txt**

/* 1*/	template <class Etype>
/* 2*/	class Avl_Node : public Tree_Node<Etype>
/* 3*/	{
/* 4*/	  private:
/* 5*/	    int Height;

/* 6*/	    friend int Node_Ht( Avl_Node *P )
/* 7*/	        { return P ? P->Height : -1; }
/* 8*/	    friend int Node_Ht( Tree_Node<Etype> *P )
/* 9*/	        { return Node_Ht( ( Avl_Node<Etype> * ) P ); }

/*10*/	    friend void Calculate_Height( Avl_Node *P )
/*11*/	        { P->Height = 1 +
/*12*/	             Max( Node_Ht( P->Left ), Node_Ht( P->Right ) ); }

/*13*/	    friend void S_Rotate_Left( Avl_Node * & k2 );
/*14*/	    friend void D_Rotate_Left( Avl_Node * & k3 );
/*15*/	    friend void S_Rotate_Right( Avl_Node * & k1 );
/*16*/	    friend void D_Rotate_Right( Avl_Node * & k3 );

/*17*/	  protected:
/*18*/	    friend class Avl_Tree<Etype>;

/*19*/	  public:
/*20*/	    Avl_Node( Etype E = 0, Avl_Node *L = NULL,
/*21*/	        Avl_Node *R = NULL, int H = 0 ) :
/*22*/	        Tree_Node<Etype>( E, L, R ), Height( H ) { }
/*23*/	};

/*24*/	template <class Etype>
/*25*/	class Avl_Tree : public Binary_Search_Tree<Etype>
/*26*/	{
/*27*/	  protected:
/*28*/	    Avl_Node<Etype> * Copy( const Avl_Node<Etype> *T );
/*29*/	    void Insert( const Etype & X, Avl_Node<Etype> * & T );
/*30*/	    void Remove( const Etype & X, Avl_Node<Etype> * & T );
/*31*/	  public:
/*32*/	    Avl_Tree( ) : Binary_Search_Tree<Etype>( ) { }

/*33*/	    const Avl_Tree & operator = ( const Avl_Tree & Value );
/*34*/	    virtual void Insert( const Etype & X )
/*35*/	        { Insert( X, ( Avl_Node<Etype> * & ) Root ); }
/*36*/	    virtual void Remove( const Etype & X )
/*37*/	        { Remove( X, ( Avl_Node<Etype> * & ) Root ); }
/*38*/	};