/**

　　* Internal method to make subtree empty.

　　*/

　　void makeEmpty( AvlNode * & t )

　　{

　　if( t != NULL )

　　{

　　makeEmpty( t->left );

　　makeEmpty( t->right );

　　delete t;

　　}

　　t = NULL;

　　}

　　/**

　　* Internal method to print a subtreerooted at t in sorted order.

　　*/

　　void printTree( AvlNode *t ) const

　　{

　　if( t != NULL )

　　{

　　printTree( t->left );

　　cout << t->element<< endl;

　　printTree( t->right );

　　}

　　}

　　/**

　　* Internal method to clone subtree.

　　*/

　　AvlNode * clone( AvlNode *t ) const

　　{

　　if( t == NULL )

　　return NULL;

　　else

　　return new AvlNode( t->element,clone( t->left ), clone( t->right ), t->height );

　　}

　　// Avl manipulations

　　/**

　　*Return the height of node t or -1 if NULL.

　　*/

　　int height( AvlNode *t ) const

　　{

　　return t == NULL ? -1 : t->height;

　　}

　　int max( int lhs, int rhs ) const

　　{

　　return lhs > rhs ? lhs : rhs;

　　}

　　/**

　　* Rotate binary tree node with left child.

　　* For AVL trees, this is a single rotationfor case 1.

　　* Update heights, then set new root.

　　*/

　　void rotateWithLeftChild( AvlNode * &k2 )

　　{

　　AvlNode *k1 = k2->left;

　　k2->left = k1->right;

　　k1->right = k2;

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

　　k1->height = max( height(k1->left ), k2->height ) + 1;

　　k2 = k1;

　　}

　　/**

　　* Rotate binary tree node with rightchild.

　　* For AVL trees, this is a single rotationfor case 4.

　　* Update heights, then set new root.

　　*/

　　void rotateWithRightChild( AvlNode * &k1 )

　　{

　　AvlNode *k2 = k1->right;

　　k1->right = k2->left;

　　k2->left = k1;

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

　　k2->height = max( height(k2->right ), k1->height ) + 1;

　　k1 = k2;

　　}

　　/**

　　* Double rotate binary tree node: firstleft child.

　　* with its right child; then node k3 withnew left child.

　　* For AVL trees, this is a double rotationfor case 2.

　　* Update heights, then set new root.

　　*/

　　void doubleWithLeftChild( AvlNode * &k3 )

　　{

　　rotateWithRightChild( k3->left );

　　rotateWithLeftChild( k3 );

　　}

　　/**

　　* Double rotate binary tree node: firstright child.

　　* with its left child; then node k1 withnew right child.

　　* For AVL trees, this is a double rotationfor case 3.

　　* Update heights, then set new root.

　　*/

　　void doubleWithRightChild( AvlNode * &k1 )

　　{

　　rotateWithLeftChild( k1->right );

　　rotateWithRightChild( k1 );

　　}

　　};

　　#endif