/**
* 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
相關(guān)推薦：| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |
