Please see the general programming webpage for details about the programming environment for this course, guidelines for programming style, and details on electronic submission of assignments.
The files you may need for this assignment can be downloaded here.
For this assignment, you are allowed to work with one other student if you wish (in fact, we suggest that you do so). If any student wishes to have a partner but has not been able to locate one, please let the instructor know so that we can match up partners.
Please make sure you adhere to the policies on academic integrity in this regard.
For this assignment, you must implement the insert method for an AVL Tree class. The general idea was covered in class, and you may refer to lecture notes or the text book for assistance.
For this assignment, you are welcome to implement any helper functions you need - just be careful to put them in a protected or private setting if they are not something an end user should have access to. For example, to implement the find function, our code uses a recursive function called finder which is protected, since it manipulates node pointers directly. The book also has other suggestions of useful helper functions, including functions to recalculate heights and to perform a single rotate.
The file TestAVLTree.h contains a function which inserts many elements and echoes the tree and its height at various places. Correct answers are in comments above each command so that you may check your answer.
Note: For simplicity, we are assuming that your AVL tree will only store distinct elements. So if a value is inserted twice, you do not need to have it represented twice in your tree. You DO need to handle this case without crashing, however!
There is a set of tests included in the TestAVLTree.cpp file in order for you to check some aspects of your insert function. However, I will also require you to do an exhaustive check of all posible rotate operations. To this end, you must modify the file TestAVLTree.cpp to test for other situations and check that the search tree and height are maintained correctly.
Feel free to write other test functions - such as a function that prints the height of every node in an inorder fashion - if that is helpful for your debugging process.
All such files can be downloaded here.
AVLTree.h
This is the implementation of the an AVL Tree, based on our binary tree code and our discussion of AVL trees in class. For this tree class, I decided to store the height explicitly in the AVLNode struct, since that value is essential for insertions and deletions. Remember that all leaves will have height 1, and for all other nodes the height is the maximum of the two children's heights plus 1.
Note: For the sake of simplicity, we did not bother to separate out the function bodies for the class into a separate "AVLTree.cpp" file. All the function bodies are embeded directly into the header. You should make your changes directly to the .h file as well.
TestAVLTree.cpp
A sample program that walks through a set of inserts. You will need to modify and submit
this file to perform additional tests.
makefile
This makefile should allow you to rebuild your project by
simply typing 'make' rather than in invoking the compiler
directly.
Source Code
Submit your revised AVLTree.h file.
Test File
Submit your revised TestAVLTree.cpp file.
"readme" file
Discuss the dynamics of your partnership, an overview of your
final product, and any further comments you
wish to make to the grader.
The assignment is worth 10 points. One point will be awarded for your test program, and .5 for your readme (including any discussion of implementation or helper functions), and 8.5 for your insert code and helper functions.
For extra credit, you may implement the remove function. This should take an object and if there is a node with that object in the tree, it should delete the node and perform any rotations that are necessary to restore the height-balance property.