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 from the schedule page.

Collaboration Policy

For this assignment, you may work with 1 partner (and in fact are encouraged to do so).

Please make sure you adhere to the policies on academic integrity in this regard.

Contents:

• Overview
• Debugging Your Program
• Files We Are Providing
• Files to Submit
  • Source Code
  • Readme File
• Grading Standards
• Extra Credit

Overview and Task

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 come talk to me with questions.

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 testAVL.cpp which creates a binary search 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 from the schedule page, except the makefile, which is available here

• BinaryTree.h and BinarySearchTree.h and AVLTree.h
  These are the implementations of the Binary Tree, Binary Search Tree, and AVL trees 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.

Files to Submit

• 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 in your readme if you make any changes there (and explain why they are needed).

• testAVL.cpp
  A sample program that creates an AVL tree and walks through a set operations, checking that inserting and removing elements works for any possible setup of the tree.

• "readme" file
  Discuss an overview of your final product, and any further comments you wish to make to the grader, including known bugs, design decisions, or extra functions that you implemented (and why).

Grading Standards

The assignment is worth 10 points. Your test file will be worth 3 points; please be sure to comment and document which test cases cover which structural situations, as this is a key part of testing in this class. Your readme and discussion is worth .5 points. The remaining points will be given for working remove code in the AVL Tree class.