Course Home | Course Policies | Homework | Lab Open Hours | Programming | Labs | Schedule & Lecture Notes

Programming Assignment 5
Removing in a BST and AVL tree

Due: Tuesday, November 23, 2010, 11:59pm
Checkpoint: Thursday, Nov.18

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.

Collaboration Policy

For this assignment, you are allowed to work with one other student if you wish (in fact, we STRONGLY 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.


Overview and Task

For this assignment, you must implement the remove method for both the Binary Search Tree and 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. 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!

Debugging Your Program

Write a function called TestAVLTree.cpp which creates both a binary search tree and 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.

Files We Are Providing

All such files can be downloaded here.

Files to Submit

Grading Standards

The assignment is worth 10 points. One point will be awarded for an early checkpoint on next Thursday, Nov. 18, at which point we expect to see (mostly) working code for deleting in the binary search tree, as well as code started for the AVL tree. Your test file will be worth 1 point. The remaining 8 points will be given for working remove code in both tree classes.