**fig4_55.txt**

/* 1*/	template <class Etype>
/* 2*/	class Splay_Node : public Tree_Node<Etype>
/* 3*/	{
/* 4*/	  protected:
/* 5*/	    Splay_Node *Parent;

/* 6*/	    void Single_Rotate( );
/* 7*/	    void Double_Rotate( );
/* 8*/	    void Zig_Left( Splay_Node * const X );
/* 9*/	    void Zig_Zig_Left( Splay_Node * const X );
/*10*/	    void Zig_Left_Zag_Right( Splay_Node * const X );
/*11*/	    void Zig_Right( Splay_Node * const X );
/*12*/	    void Zig_Zig_Right( Splay_Node * const X );
/*13*/	    void Zig_Right_Zag_Left( Splay_Node * const X );

/*14*/	  protected:
/*15*/	    friend class Splay_Tree<Etype>;

/*16*/	  public:
/*17*/	    Splay_Node( Etype E = 0, Splay_Node *L = NULL,
/*18*/	        Splay_Node *R = NULL, Splay_Node *P = NULL ) :
/*19*/	        Tree_Node<Etype>( E, L, R ), Parent( P ) { }
/*20*/	};

/*21*/	template <class Etype>
/*22*/	class Splay_Tree : public Binary_Search_Tree<Etype>
/*23*/	{
/*24*/	  protected:
/*25*/	    Splay_Node<Etype> *
/*26*/	        Copy( Splay_Node<Etype> *T );
/*27*/	    Splay_Node<Etype> *
/*28*/	        Insert( const Etype & X, Splay_Node<Etype> * & T );
/*29*/	    void Remove( const Etype & X, Splay_Node<Etype> * & T );
/*30*/	    int Splay( Splay_Node<Etype> * const Current );

/*31*/	  public:
/*32*/	    // Constructors.
/*33*/	    Splay_Tree( ) : Binary_Search_Tree<Etype>( ) { }

/*34*/	    // Operator.
/*35*/	    const Splay_Tree & operator = ( const Splay_Tree & Value );

/*36*/	    // Member functions.
/*37*/	    virtual int Find( const Etype & X );

/*38*/	    virtual int Find_Min( )
/*39*/	        { return Splay( ( Splay_Node<Etype> * ) ( Root =
/*40*/	            Last_Find = Binary_Search_Tree<Etype>::
/*41*/	                        Find_Min( Root ) ) ); }

/*42*/	    virtual int Find_Max( )
/*43*/	        { return Splay( ( Splay_Node<Etype> * ) ( Root =
/*44*/	            Last_Find = Binary_Search_Tree<Etype>::
/*45*/	                        Find_Max( Root ) ) ); }

/*46*/	    virtual void Insert( const Etype & X )
/*47*/	        { Splay( ( Splay_Node<Etype> * )
/*48*/	            ( Root = Last_Find = Splay_Tree<Etype>::
/*49*/	            Insert( X, ( Splay_Node<Etype> * )Root ) ) ); }

/*50*/	    virtual void Remove( const Etype & X )
/*51*/	        { Splay_Tree<Etype>::
/*52*/	            Remove( X, ( Splay_Node<Etype> * ) Root ); }
/*53*/	};