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 (and 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 remove method for the AVL Tree class. The general idea was covered in class, and you may refer to lecture notes or the text book for assistance.
The basic structure of remove is the same as in a binary search tree (see programming project 4). To implement remove, you will first use the find function to see if the value is in the list. If it is, there are several cases to consider.
Say that your value is in node a. If a is a leaf, you can simply delete it (using helper functions from BinaryTree.h). If a has only 1 child, you can delete it and promote that child while maintaining a binary search tree property. However, if it has two children, you need to find the next node in an inorder traveral. Call this node b. If b is a leaf, you swap the value into a's position and then delete the leaf node that contained b. If it is not a leaf, it must have only a right child (since the left child would come first in an inorder traversal), so you can delete b, promote its right child, and still put b's value into a's node.
Now, we have one added difficulty. Deleting either node a or b (depending on the case above) may have unbalanced the heights. So we need to search upward, starting at the node directly above of where a or b was in the tree, and recalculate heights of all the nodes on the path up to the root. As we recalculate for each node on the path, if there is any imbalance, you must perform a rotation to balance the tree. Note that this part of the code is essentially the same as the rotations in insert - find z, y, and x, and perform pivot operations until the three nodes are in balance.
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. More likely, you will want to use the functions provided in BinaryTree.h, both for the tree and for iterators.
Note: For simplicity, we are assuming that your trees 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!
Write a function called TestAVL.cpp which creates an AVL tree and performs inserts and removes on the tree. You are welcome to use the draw function (inherited from BinaryTree.h) to draw your tree at each step and debug your code.
Again, feel free to write other test functions - such as a function that prints the height of a node, or an inorder traversal of the tree - if that is helpful for your debugging process.
All such files can be downloaded here.
BinaryTree.h and BinarySearchTree.h and AVLTree.h
These are the implementations of the Binary Tree, Binary Search
Tree, and AVL Tree from our work in class.
Note: For the sake of simplicity, we did not bother to separate out the function bodies for the class into a separate cpp files. All the function bodies are embeded directly into the header. You should make your changes directly to the .h file as well.
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 files. Note that you should not need to alter BinaryTree.h or BinarySearchTree.h, so please let me know if you make any changes there (and explain why they are needed) in your readme!
TestAVL.cpp
A sample program that creates a binary search tree and walks through
a set operations, checking that inserting and removing elements works.
"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 an early checkpoint on next Monday, April 25, at which point we expect to see an initial draft of your remove function. Your test file will be worth 1 point. The remaining 8 points will be given for working remove code in AVLTree.h.