#include "RedBlackTree.h"
#include "Except.h"
template <class Comparable>
RedBlackTree<Comparable>::
RedBlackTree( const Comparable & negInf )
{
nullNode = new Node;
nullNode->left = nullNode->right = nullNode;
header = new Node( negInf );
header->left = header->right = nullNode;
}
template <class Comparable>
RedBlackTree<Comparable>::
RedBlackTree( const RedBlackTree<Comparable> & rhs )
{
nullNode = new Node;
nullNode->left = nullNode->right = nullNode;
header = new Node( rhs.header->element );
header->left = header->right = nullNode;
*this = rhs;
}
template <class Comparable>
RedBlackTree<Comparable>::
~RedBlackTree( )
{
makeEmpty( );
delete nullNode;
delete header;
}
template <class Comparable>
void RedBlackTree<Comparable>::
insert( const Comparable & x )
{
current = parent = grand = header;
nullNode->element = x;
while( current->element != x )
{
great = grand; grand = parent; parent = current;
current = x < current->element ? current->left : current->right;
if( current->left->color == RED && current->right->color == RED )
handleReorient( x );
}
if( current != nullNode )
throw DuplicateItemException( );
current = new Node( x, nullNode, nullNode );
if( x < parent->element )
parent->left = current;
else
parent->right = current;
handleReorient( x );
}
template <class Comparable>
void RedBlackTree<Comparable>::
remove( const Comparable & x )
{
cout << "Sorry, remove unimplemented; " << x <<
" still present" << endl;
}
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::
findMin( ) const
{
if( isEmpty( ) )
return Cref<Comparable>( );
Node *itr = header->right;
while( itr->left != nullNode )
itr = itr->left;
return Cref<Comparable>( itr->element );
}
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::
findMax( ) const
{
if( isEmpty( ) )
return Cref<Comparable>( );
Node *itr = header->right;
while( itr->right != nullNode )
itr = itr->right;
return Cref<Comparable>( itr->element );
}
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::
find( const Comparable & x ) const
{
nullNode->element = x;
Node *curr = header->right;
for( ; ; )
{
if( x < curr->element )
curr = curr->left;
else if( curr->element < x )
curr = curr->right;
else if( curr != nullNode )
return Cref<Comparable>( curr->element );
else
return Cref<Comparable>( );
}
}
template <class Comparable>
void RedBlackTree<Comparable>::
makeEmpty( )
{
reclaimMemory( header->right );
header->right = nullNode;
}
template <class Comparable>
bool RedBlackTree<Comparable>::
isEmpty( ) const
{
return header->right == nullNode;
}
template <class Comparable>
const RedBlackTree<Comparable> &
RedBlackTree<Comparable>::
operator=( const RedBlackTree<Comparable> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
header->right = clone( rhs.header->right );
}
return *this;
}
template <class Comparable>
RedBlackNode<Comparable> *
RedBlackTree<Comparable>::
clone( Node * t ) const
{
if( t == t->left ) return nullNode;
else
return new RedBlackNode<Comparable>( t->element, clone( t->left ),
clone( t->right ), t->color );
}
template <class Comparable>
void RedBlackTree<Comparable>::
handleReorient( const Comparable & item )
{
current->color = RED;
current->left->color = BLACK;
current->right->color = BLACK;
if( parent->color == RED ) {
grand->color = RED;
if( item < grand->element != item < parent->element )
parent = rotate( item, grand ); current = rotate( item, great );
current->color = BLACK;
}
header->right->color = BLACK; }
template <class Comparable>
RedBlackNode<Comparable> *
RedBlackTree<Comparable>::
rotate( const Comparable & item,
Node *theParent ) const
{
if( item < theParent->element )
{
item < theParent->left->element ?
rotateWithLeftChild( theParent->left ) : rotateWithRightChild( theParent->left ) ; return theParent->left;
}
else
{
item < theParent->right->element ?
rotateWithLeftChild( theParent->right ) : rotateWithRightChild( theParent->right ); return theParent->right;
}
}
template <class Comparable>
void RedBlackTree<Comparable>::
rotateWithLeftChild( Node * & k2 ) const
{
Node *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2 = k1;
}
template <class Comparable>
void RedBlackTree<Comparable>::
rotateWithRightChild( Node * & k1 ) const
{
Node *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1 = k2;
}
template <class Comparable>
void RedBlackTree<Comparable>::
reclaimMemory( Node *t ) const
{
if( t != t->left )
{
reclaimMemory( t->left );
reclaimMemory( t->right );
delete t;
}
}