#include "AATree.h"
template <class Comparable>
AATree<Comparable>::
AATree( )
{
nullNode = new Node;
nullNode->left = nullNode->right = nullNode;
nullNode->level = 0;
root = nullNode;
}
template <class Comparable>
AATree<Comparable>::
AATree( const AATree<Comparable> & rhs )
{
nullNode = new Node;
nullNode->left = nullNode->right = nullNode;
nullNode->level = 0;
root = clone( rhs.root );
}
template <class Comparable>
AATree<Comparable>::
~AATree( )
{
makeEmpty( );
delete nullNode;
}
template <class Comparable>
void AATree<Comparable>::
insert( const Comparable & x )
{
insert( x, root );
}
template <class Comparable>
void AATree<Comparable>::
remove( const Comparable & x )
{
remove( x, root );
}
template <class Comparable>
Cref<Comparable> AATree<Comparable>::
findMin( ) const
{
if( isEmpty( ) )
return elementAt( NULL );
Node *ptr = root;
while( ptr->left != nullNode )
ptr = ptr->left;
return elementAt( ptr );
}
template <class Comparable>
Cref<Comparable> AATree<Comparable>::
findMax( ) const
{
if( isEmpty( ) )
return elementAt( NULL );
Node *ptr = root;
while( ptr->right != nullNode )
ptr = ptr->right;
return elementAt( ptr );
}
template <class Comparable>
Cref<Comparable> AATree<Comparable>::
find( const Comparable & x ) const
{
Node *current = root;
nullNode->element = x;
for( ; ; )
{
if( x < current->element )
current = current->left;
else if( current->element < x )
current = current->right;
else if( current != nullNode )
return elementAt( current );
else
return elementAt( NULL );
}
}
template <class Comparable>
void AATree<Comparable>::
makeEmpty( )
{
makeEmpty( root );
}
template <class Comparable>
bool AATree<Comparable>::
isEmpty( ) const
{
return root == nullNode;
}
template <class Comparable>
const AATree<Comparable> &
AATree<Comparable>::
operator=( const AATree<Comparable> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}
template <class Comparable>
Cref<Comparable> AATree<Comparable>::
elementAt( Node *t ) const
{
return t == NULL ? Cref<Comparable>( ) : Cref<Comparable>( t->element );
}
template <class Comparable>
void AATree<Comparable>::
insert( const Comparable & x, Node * & t )
{
if( t == nullNode )
t = new Node( x, nullNode, nullNode );
else if( x < t->element )
insert( x, t->left );
else if( t->element < x )
insert( x, t->right );
else
throw DuplicateItemException( );
skew( t );
split( t );
}
template <class Comparable>
void AATree<Comparable>::
remove( const Comparable & x, Node * & t )
{
static Node *lastNode, *deletedNode = nullNode;
if( t != nullNode )
{
lastNode = t;
if( x < t->element )
remove( x, t->left );
else
{
deletedNode = t;
remove( x, t->right );
}
if( t == lastNode )
{
if( deletedNode == nullNode || x != deletedNode->element )
throw ItemNotFoundException( );
deletedNode->element = t->element;
deletedNode = nullNode;
t = t->right;
delete lastNode;
}
else
if( t->left->level < t->level - 1 ||
t->right->level < t->level - 1 )
{
if( t->right->level > --t->level )
t->right->level = t->level;
skew( t );
skew( t->right );
skew( t->right->right );
split( t );
split( t->right );
}
}
}
template <class Comparable>
void AATree<Comparable>::
makeEmpty( AANode<Comparable> * & t )
{
if( t != nullNode )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
}
t = nullNode;
}
template <class Comparable>
void AATree<Comparable>::
rotateWithLeftChild( Node * & k2 ) const
{
Node *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2 = k1;
}
template <class Comparable>
void AATree<Comparable>::
rotateWithRightChild( Node * & k1 ) const
{
Node *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1 = k2;
}
template <class Comparable>
void AATree<Comparable>::
skew( Node * & t ) const
{
if( t->left->level == t->level )
rotateWithLeftChild( t );
}
template <class Comparable>
void AATree<Comparable>::
split( Node * & t ) const
{
if( t->right->right->level == t->level )
{
rotateWithRightChild( t );
t->level++;
}
}
template <class Comparable>
AANode<Comparable> *
AATree<Comparable>::
clone( Node * t ) const
{
if( t == t->left ) return nullNode;
else
return new Node( t->element, clone( t->left ),
clone( t->right ), t->level );
}