You will be graded on the correctness of the AVL code, your adherence to the design (required), and your documentation of the code (comments in the code). You must comment each class and each method within each class as to its purpose and implementation (except for trivial accessors and mutators).
Your report must include at a minimum the following sections:
This page must include a title for the paper, your name, person number and user name, as well as the date of submission. It must also include the course number and name and your recitation section. It must also include my name as the person you are submitting the report to. No other information should appear on this page.
The table of contents, which must appear on a page by itself, must list all the sections of the paper (sections and subsections), with their page numbers.
This is a one or two paragraph summary of the paper. Summarize the project that the paper reports, the main points of the project, and the final results and recommendations.
This section gives, in more detail than the executive summary, an overview of the project (its goals, the data structures involved, etc).
This section discusses the implementation of each of the data structures involved. The discussion must include the relationship of the main class to every class with which it has a relationship, the nature of the relationship, the reason for the relationship, etc. Note that you implemented the linear data structures in the previous assignment. An implementation of the Ordered STL list is provided in the PP3.zip for this project. You need only discuss one of the two linear data structures - if you didn't complete PP2 you are not at a disadvantage here.
- Linear data structures (Ordered STL list or Ordered LRS list)
- Non-linear data structure (AVL tree)
You must detail here the correctness testing you undertook to verify that the implementation performs according to specifications. You must also detail any knows bugs or limitations of the implementation.
You must detail here the performance testing you undertook to measure how well each data structure performed. Here you must discuss the nature and amount of data entered into the data structures, the length and composition of the command sequences, etc. You should justify your testing choices. The decision makers at your employer like it when colorful graphs are incorporated into otherwise dull reports. If graphs are not possible, then tables and charts are an acceptable alternative. Explain what tests you ran, and why. It is not acceptable to run only a single test on each data structure. Think of other tests you might want to perform. What, for example, might be a worst-case scenario for an ordered list? What about for the AVL tree? What is a best-case scenario? How do the data structures behave with random command sequences?
State what you expected the outcome to be, given your understanding of the performance of the data structures involved. State also what your empirical testing showed. Explain the data you gathered, as well as any discrepancies you found between the data and your expectations.
State clearly and justify your recommendations to the company.
If you reference any sources, give proper credit here.
Rotations
To implement the AVL tree you need to decide on a represenation for the rotations. It turns out it is relatively straightforward to keep track of rotations while doing insertions. To do an insertion you define a visitor for the BRStruct that (recursively) traverses the tree to the point where the insertion should occur (this will be an empty tree - i.e. a BRStruct whose state is BRSEmptyState).As you unwind the recursive calls, return a rotation object which is appropriate for the path that you've taken. Remember, as you descend the tree recursively you will go either left or right, depending on where the item to be inserted belongs. Set up your rotation objects so that they all fall under a common Rotation type (abstract class) with common methods specified. You need to have subclasses of all the AVL rotations: two single rotations (left-left and right-right) and two double rotations (left-right and right-left). It turns out it is convenient to have a Null rotation and also left and right rotations.
Set up transitions amongst the rotations; one way to do this is to define a goLeft() and a goRight() method for all Rotations. For example, if r is a Null rotation object, r.goLeft() should return a Left rotation object.
An apply(BRStruct tree) method can be defined for all rotations. When called, the apply method performs the rotation about the supplied tree.
AVL trees
Remember that in order to guarantee O(log n) performance (where n is the size of the tree) for its operations an AVL tree implementation must store the height information for each node and not recompute the height. If the tree is to also store a key with an associated value there are three things in total that each BRStruct node must hold: height, key and value. The height information can be stored as an int, and must not be part of the templatization of the AVL tree.Two reasonable choices of representation are a triplet (height-key-value) and a pair containing the height and a pair of key and value. I prefer the latter because it is easier to return a pair of key and value for those methods that require it.
The PP3 directory must include only your source code (declaration and implementation) files as well as your makefile and your runtime report (which must be a postscript or a PDF file). Do NOT submit reports in any other format - they will not be graded.
Your submission must not include object files, executable files
or any files whose filenames begin with `#' or end in `~'. You also
must not include the SunWS_cache directory and its
contents in your submission.
Use the zip utility to create a file named
`PP3.zip'. From the directory containing the `PP3'
directory, issue the command
zip -r PP3 PP3
Submit only the resultant `PP3.zip' file.
Use the submit_cse250 command to submit your work.
This project is due on or before 11:59:59 PM on April 10, 2004.