class Tree {

private:

// class TNode is private to the Tree class.
// nobody outside this class needs to know what nodes look like.
class TNode {
public: // a very open class...

  int data;  // int to keep life simple
  // . . .  other data could be added here if desired
  int balance; // right height - left height (-1 = left heavy, +1 = right heavy)
  TNode *left, *right;

  TNode (int data, TNode *left, TNode *right, int balance) {
    TNode::data = data;
    TNode::left = left; TNode::right = right;
    TNode::balance = balance;
  }

};

TNode *root;  // root pointer
int size; // number of values in the tree

// deletes all of the nodes in a specfied subtree
void purge (TNode* subroot);

// inserts "data" into the specfied subtree.  returns true if the
// insertion is successful (value not already in tree) and false otherwise.
// updates "heightChanged" to reflect whether or not the insertion changed
// the height of the subtree.
bool subInsert (TNode *&subRoot, int data, bool &heightChanged);

// displays a subtree graphically using specfied prefix strings
void subDisplay (String2002 leftPreString, String2002 midPreString,
                 String2002 rightPreString, TNode *subRoot) const;

// performs an LL rotation at the node (and adjusts all balance factors)
void rotateLL (TNode *&subRoot);

// performs an LR rotation at the node (and adjusts all balance factors)
void rotateLR (TNode *&subRoot);

// performs an RR rotation at the node (and adjusts all balance factors)
void rotateRR (TNode *&subRoot);

// performs an RL rotation at the node (and adjusts all balance factors)
void rotateRL (TNode *&subRoot);

public:

// simple methods are often implemented directly in the header file.
// this goes somewhat against the principle of "hiding" as many implementation
// details as possible in the header file, but does keep things simpler.
Tree () { // default constructor
  root = NULL; size = 0;
}

~Tree();  // destructor

// returns true if insertion successful (data does not already exist)
// and false othewise.
bool insert (int data);

// returns the number of values in the tree (0 if tree empty)
int getSize() const;

// outputs tree graphically to "cout"
void display () const;

};