#include "BinarySearchTree.h"
#include "Except.h"
template <class Comparable>
BinarySearchTree<Comparable>::
BinarySearchTree( ) : root( NULL )
{
}
template <class Comparable>
BinarySearchTree<Comparable>::
BinarySearchTree( const BinarySearchTree<Comparable> & rhs ) : root( NULL )
{
*this = rhs;
}
template <class Comparable>
BinarySearchTree<Comparable>::
~BinarySearchTree( )
{
makeEmpty( );
}
template <class Comparable>
void BinarySearchTree<Comparable>::
insert( const Comparable & x )
{
insert( x, root );
}
template <class Comparable>
void BinarySearchTree<Comparable>::
remove( const Comparable & x )
{
remove( x, root );
}
template <class Comparable>
void BinarySearchTree<Comparable>::
removeMin( )
{
removeMin( root );
}
template <class Comparable>
Cref<Comparable> BinarySearchTree<Comparable>::
findMin( ) const
{
return elementAt( findMin( root ) );
}
template <class Comparable>
Cref<Comparable> BinarySearchTree<Comparable>::
findMax( ) const
{
return elementAt( findMax( root ) );
}
template <class Comparable>
Cref<Comparable> BinarySearchTree<Comparable>::
find( const Comparable & x ) const
{
return elementAt( find( x, root ) );
}
template <class Comparable>
void BinarySearchTree<Comparable>::
makeEmpty( )
{
makeEmpty( root );
}
template <class Comparable>
bool BinarySearchTree<Comparable>::
isEmpty( ) const
{
return root == NULL;
}
template <class Comparable>
const BinarySearchTree<Comparable> &
BinarySearchTree<Comparable>::
operator=( const BinarySearchTree<Comparable> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}
template <class Comparable>
Cref<Comparable> BinarySearchTree<Comparable>::
elementAt( Node *t ) const
{
return t == NULL ? Cref<Comparable>( ) : Cref<Comparable>( t->element );
}
template <class Comparable>
void BinarySearchTree<Comparable>::
insert( const Comparable & x, Node * & t ) const
{
if( t == NULL )
t = new Node( x, NULL, NULL );
else if( x < t->element )
insert( x, t->left );
else if( t->element < x )
insert( x, t->right );
else
throw DuplicateItemException( );
}
template <class Comparable>
void BinarySearchTree<Comparable>::
remove( const Comparable & x, Node * & t ) const
{
if( t == NULL )
throw ItemNotFoundException( );
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != NULL && t->right != NULL ) {
t->element = findMin( t->right )->element;
removeMin( t->right ); }
else
{
BinaryNode<Comparable> *oldNode = t;
t = ( t->left != NULL ) ? t->left : t->right; delete oldNode; }
}
template <class Comparable>
void BinarySearchTree<Comparable>::
removeMin( Node * & t ) const
{
if( t == NULL )
throw UnderflowException( );
else if( t->left != NULL )
removeMin( t->left );
else
{
Node *tmp = t;
t = t->right;
delete tmp;
}
}
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTree<Comparable>::
findMin( Node *t ) const
{
if( t != NULL )
while( t->left != NULL )
t = t->left;
return t;
}
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTree<Comparable>::
findMax( Node *t ) const
{
if( t != NULL )
while( t->right != NULL )
t = t->right;
return t;
}
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTree<Comparable>::
find( const Comparable & x, Node *t ) const
{
while( t != NULL )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return t;
return NULL; }
template <class Comparable>
void BinarySearchTree<Comparable>::
makeEmpty( Node * & t ) const
{
if( t != NULL )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
}
t = NULL;
}
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTree<Comparable>::
clone( Node * t ) const
{
if( t == NULL )
return NULL;
else
return new Node( t->element, clone( t->left ), clone( t->right ), t->size );
}
template <class Comparable>
Cref<Comparable> BinarySearchTreeWithRank<Comparable>::
findKth( int k ) const
{
return elementAt( findKth( k, root ) );
}
template <class Comparable>
void BinarySearchTreeWithRank<Comparable>::
insert( const Comparable & x, Node * & t ) const
{
if( t == NULL )
t = new Node( x, NULL, NULL, 0 );
else if( x < t->element )
insert( x, t->left );
else if( t->element < x )
insert( x, t->right );
else
throw DuplicateItemException( );
t->size++;
}
template <class Comparable>
void BinarySearchTreeWithRank<Comparable>::
remove( const Comparable & x, Node * & t ) const
{
if( t == NULL )
throw ItemNotFoundException( );
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != NULL && t->right != NULL ) {
t->element = findMin( t->right )->element;
removeMin( t->right ); }
else
{
BinaryNode<Comparable> *oldNode = t;
t = ( t->left != NULL ) ? t->left : t->right; delete oldNode; return;
}
t->size--;
}
template <class Comparable>
void BinarySearchTreeWithRank<Comparable>::
removeMin( Node * & t ) const
{
if( t == NULL )
throw UnderflowException( );
else if( t->left != NULL )
removeMin( t->left );
else
{
Node *tmp = t;
t = t->right;
delete tmp;
return;
}
t->size--;
}
template <class Comparable>
BinaryNode<Comparable> *
BinarySearchTreeWithRank<Comparable>::
findKth( int k, Node * t ) const
{
if( t == NULL )
return NULL;
int leftSize = treeSize( t->left );
if( k <= leftSize )
return findKth( k, t->left );
else if( k == leftSize + 1 )
return t;
else
return findKth( k - leftSize - 1, t->right );
}