//Throws UnderflowException as warranted

　　template

　　classAvlTree

　　{

　　public:

　　AvlTree( ) : root( NULL ) { }

　　AvlTree( const AvlTree & rhs ) : root(NULL )

　　{

　　*this = rhs;

　　}

　　~AvlTree( )

　　{

　　makeEmpty( );

　　}

　　/**

　　* Find the smallest item in the tree.

　　* Throw UnderflowException if empty.

　　*/

　　const Comparable & findMin( ) const

　　{

　　if( isEmpty( ) )

　　throw UnderflowException( );

　　return findMin( root )->element;

　　}

　　/**

　　* Find the largest item in the tree.

　　* Throw UnderflowException if empty.

　　*/

　　const Comparable & findMax( ) const

　　{

　　if( isEmpty( ) )

　　throw UnderflowException( );

　　return findMax( root )->element;

　　}

　　/**

　　* Returns true if x is found in the tree.

　　*/

　　bool contains( const Comparable & x )const

　　{

　　return contains( x, root );

　　}

　　/**

　　* Test if the tree is logically empty.

　　* Return true if empty, false otherwise.

　　*/

　　bool isEmpty( ) const

　　{

　　return root == NULL;

　　}

　　/**

　　* Print the tree contents in sorted order.

　　*/

　　void printTree( ) const

　　{

　　if( isEmpty( ) )

　　cout << "Emptytree" << endl;

　　else

　　printTree( root );

　　}

　　/**

　　* Make the tree logically empty.

　　*/

　　void makeEmpty( )

　　{

　　makeEmpty( root );

　　}

　　/**

　　* Insert x into the tree; duplicates areignored.

　　*/

　　void insert( const Comparable & x )

　　{

　　insert( x, root );

　　}

　　/**

　　* Remove x from the tree. Nothing is doneif x is not found.

　　*/

　　void remove( const Comparable & x )

　　{

　　cout << "Sorry, removeunimplemented; " << x <<

　　" still present"<< endl;

　　}

　　/**

　　* Deep copy.

　　*/

　　const AvlTree & operator=( constAvlTree & rhs )

　　{

　　if( this != &rhs )

　　{

　　makeEmpty( );

　　root = clone( rhs.root );

　　}

　　return *this;

　　}