Page 156 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

{ Notes
if( t == NULL )
return NULL;
if( t->left == NULL )
return t;
return findMin( t->left );
}

/**
* Internal method to find the largest item in 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 in a subtree.
* x is item to search for.
* t is the node that roots the tree.
*/
bool contains( const Comparable & x, AvlNode *t, int &comps ) const
{
if( t == NULL )
return false;
else if( x < t->element )
return contains( x, t->left, ++comps);
else if( t->element < x )
return contains( x, t->right, ++comps);
else
return true; // Match
}
/****** NONRECURSIVE VERSION*************************
bool contains( const Comparable & x, AvlNode *t ) const
{
while( t != NULL )

LOVELY PROFESSIONAL UNIVERSITY 151