Requirements:

In this project, you will implement:

1. AVL tree: Search_tree

A skeleton header files are provided. You should modify the header file(s) for the project, though you must add your own comments. Do not copy text from the specifications.

You are required to submit within your gzipped tar file the following header files:

• Search_tree.h

The command is:

$ tar -cvf uwuserid_p3.tar Search_tree.h
$ gzip uwuserid_p3.tar

Be sure to read the instructions on the Projects page with regard to the submission of projects.

Runtime

The run time of each member function is specified in parentheses at the end of the description.

Comments

You are expected to comment your code. At least 20% of your source code must be in the form of valid and informative comments. As you will use this class in future projects, it is advisable to comment it appropriately. You are also expected to comment the provided bare header files.

Testing

With each project, two drivers are provided, one using the type int, the other using the type double. Please note, in Dev-C++, it is not possible to include both drivers in the same project, as both will have a main function. You must either:

• Rename main to _main in one of the two driver files, or
• Include only one, implement it appropriately, and then proceed to test it on Unix using both drivers.