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