private:

　　struct AvlNode

　　{

　　Comparable element;

　　AvlNode *left;

　　AvlNode *right;

　　int height;

　　AvlNode( const Comparable &theElement, AvlNode *lt,

　　AvlNode *rt, int h = 0 )

　　: element( theElement ), left( lt ),right( rt ), height( h ) { }

　　};

　　AvlNode *root;

　　/**

　　* Internal method to insert into asubtree.

　　* x is the item to insert.

　　* t is the node that roots the subtree.

　　* Set the new root of the subtree.

　　*/

　　void insert( const Comparable & x,AvlNode * & t )

　　{

　　if( t == NULL )

　　t = new AvlNode( x, NULL, NULL );

　　else if( x < t->element )

　　{

　　insert( x, t->left );

　　if( height( t->left ) - height(t->right ) == 2 )

　　if( x left->element )

　　rotateWithLeftChild( t );

　　else

　　doubleWithLeftChild( t );

　　}

　　else if( t->element < x )

　　{

　　insert( x, t->right );

　　if( height( t->right ) - height(t->left ) == 2 )

　　if( t->right->element< x )

　　rotateWithRightChild( t );

　　else

　　doubleWithRightChild( t );

　　}

　　t->height = max( height( t->left), height( t->right ) ) + 1;

　　}

　　/**

　　* Internal method to find the smallestitem in a subtree t.

　　* Return node containing the smallestitem.

　　*/

　　AvlNode * findMin( AvlNode *t ) const

　　{

　　if( t == NULL )

　　return NULL;

　　if( t->left == NULL )

　　return t;

　　return findMin( t->left );

　　}

　　/**

　　* Internal method to find the largest itemin a subtree t.

　　* Return node containing the largest item.

　　*/

　　AvlNode * findMax( AvlNode *t ) const

　　{

　　if( t != NULL )

　　while( t->right != NULL )

　　t = t->right;

　　return t;

　　}

　　/**

　　* Internal method to test if an item is ina subtree.

　　* x is item to search for.

　　* t is the node that roots the tree.

　　*/

　　bool contains( const Comparable & x,AvlNode *t ) const

　　{

　　if( t == NULL )

　　return false;

　　else if( x < t->element )

　　return contains( x, t->left );

　　else if( t->element < x )

　　return contains( x, t->right );

　　else

　　return true; // Match

　　}

　　/****** NONRECURSIVEVERSION*************************

　　bool contains( const Comparable & x,AvlNode *t ) const

　　{

　　while( t != NULL )

　　if( x < t->element )

　　t = t->left;

　　else if( t->element < x )

　　t = t->right;

　　else

　　return true; // Match

　　return false; // No match

　　}

　　*****************************************************/