CSC 365- Programming project 3 --(Due November 11, 2004)

• AVL Tree class used in the Tree class is only partially completed. Your task for this project could be to complete its remove method.

• remove the concept "BF" from the AVL; rewrite the insert and develop remove so they they both maintain the tree as a AVL; but, use the levels() method in determining what action needs to be made. For example, if we insert an element into the right subtree; and now find that the number of levels in that subtree is different from the number of levels in the left subtree by more than one; we have established that we need to balance the tree. So, there is no BF to maintain in this approach to implementing the AVL tree; nor, is there any need for reporting that a subtree has gotten shorter or taller for remove or insert, respectively. But, you do have to rewrite other parts of the AVL class that make references to BF as well as the Tree class that does the same. For example, the Tree class in the Validate() method has the instructions if (!root_.BFisOK()) return false;. Obviously, it doesn't make sense to have or call a method called BFisOK() if you don't maintain a Balance factors when validating a tree as an AVL.

The test program test2 was written to test the Tree class. It is already designed to test remove, so it should be used to validate and verify that you wrote your AVL version correctly and completely; regardless of the option you chose for this assignment. However, you probably should start with simple test programs like test1 to create the verity of circumstances that arise when doing insertion/deletion. You must make sure that your code rotates the tree correctly when needed. If you are adding the remove() with the BFs, you want to make sure that the balance factors are changed appropriately and so on.

I will only need the new version of the AVL class sent to me.