#ifndef _AA_TREE_H_
#define _AA_TREE_H_
#include "Except.h"
#include "Wrapper.h"
#include <stdlib.h>
template <class Comparable>
class AATree;
template <class Comparable>
class AANode
{
Comparable element;
AANode *left;
AANode *right;
int level;
AANode( ) : left( NULL ), right( NULL ), level( 1 ) { }
AANode( const Comparable & e, AANode *lt, AANode *rt, int lv = 1 )
: element( e ), left( lt ), right( rt ), level( lv ) { }
friend class AATree<Comparable>;
};
template <class Comparable>
class AATree
{
public:
AATree( );
AATree( const AATree & rhs );
~AATree( );
Cref<Comparable> findMin( ) const;
Cref<Comparable> findMax( ) const;
Cref<Comparable> find( const Comparable & x ) const;
bool isEmpty( ) const;
void makeEmpty( );
void insert( const Comparable & x );
void remove( const Comparable & x );
const AATree & operator=( const AATree & rhs );
typedef AANode<Comparable> Node;
private:
Node *root;
Node *nullNode;
Cref<Comparable> elementAt( Node *t ) const;
void insert( const Comparable & x, Node * & t );
void remove( const Comparable & x, Node * & t );
void makeEmpty( Node * & t );
void skew( Node * & t ) const;
void split( Node * & t ) const;
void rotateWithLeftChild( Node * & t ) const;
void rotateWithRightChild( Node * & t ) const;
AANode<Comparable> * clone( Node * t ) const;
};
#include "AATree.cpp"
#endif