Due Date: approximately March 4th(more later)

We are to implement an AVL tree using C++ classes. You are to structure your main program to accept and interpret file input with the following format. The following commands will be used:
[A or a] [integer]  Add (insert) the integer value into the AVL tree and perform any necessary rebalancing
[D or d] [integer]   Delete the integer from the AVL tree and perform any necessary rebalancing
[S or s] [integer]   Search the AVL tree for the integer key
[P or p]                     Preorder Traversal and the node weight.
[I or i]                      Inorder Traversal and the node weight.
[R or r]                      Postorder Traversal and the node weight.
[B or b]                  a report that gives the number of subtrees that are left heavy, right heavy and balanced (see more explanation below)

File Requirements: You will turn in 7 files to the turn in directory on the ecst server in /user/projects/csci311/p1/[username].
The files are:
avl_node.h avl_node.cpp avl_tree.h avl_tree.cpp main.cpp Makefile Readme
We will discuss what these files contain during lab

Special criteria: The commands may come in any order.  Although additions (insertions) to the tree are relatively straightforward, deletions of parent nodes that have two children may result in ambiguities.  If such a parent node is deleted, it is to be replaced by the shallower (as in depth in the tree) of the inorder predecessor versus the inorder successor.  If the inorder predecessor and the successor are the same depth, use the inorder successor.

For the command "B" in the input file, you will print out a report.  In this report you will consider each node in the tree.  For each node in the tree you will assess whether the the subtree rooted at that node is left heavy, right heavy, or balanced.  Each time the command "B" is issued you will generate a report of how many subtrees total in the current tree are left heavy, right heavy or balanced.  Your instructor will provide numerous examples.

Send your output for this program to a file.  For Inserts (Additions), it is an error to insert a duplicate value into the tree, be sure to notify the user of such an attempt.  Tell the user if an operation is successful, as well.  Be sure to give appropriate 'error' messages back to the user of your program.  For example, if asked to Delete a value from the tree that was not found in the tree, you should reply that the value was not found in the tree and therefore, not deleted.  For the Search operation, if the item that is being sought is found, print out a message that says you found it and what its value is.  If the item is not found, print out a message to that effect.  Of course, output the results of a traversal to this file, as well.

A good strategy for developing your program: Write pseudocode for your program that includes :

1. A complete AVL tree class declaration and any other data structure declarations - this to become your .h file
2. pseudocode for your main program - this to become your avlmain.cpp file
3. pseudocode for each function definition - this to become your documentation for your avl.cpp file

Test Files and Program output

As I discussed in labs I will make test files available to you. Here is an example of what an input file will look like:
A 60
A 30
A 40
A 70
A 10
A 15
A 15
I
D 11
R
S 100
P
B