CSE326 AVL Trees
Spring 2002

Due: Friday, May 3, 2002
  Electronic turn-in due by 5:30 PM

Programming

1. Get projects/avl.tar.gz from the course directory.

2. Implement AVL tree insertion and deletion as described in chapter 7.1 in the textbook. When necessary, deleted nodes should be replaced by their inorder predecessor (this is opposite from the remove assignment).

3. In the README file you include with your turnin, describe any design decisions you made and any interesting implementation issues that came up. You don't need to recapitulate the algorithms described in the textbook or in class.

4. Remember to read the turnin info page before submitting your assignment.

5. Extra-Credit: Implement an AVL tree as a template (see note below).

Notes

• You will probably have to add members and methods to the class AVLTree, defined in avl.h. Don't change any of the existing members or methods, as the driver (the command line stuff) depends on them.

• You also may want to make more .C files than the ones I've given you; if you do, update the OBJS definition in the makefile. This time the makefile is a little more complicated this time, because it's also compiling the driver code.

• Read through avl.h and main.C. Exactly what you need to do is documented in the code. The class is much like the TreeNode class from the remove assignment, but there are some interface differences, because an AVL tree does a lot more restructuring on inserts and deletes. In particular, the Remove() and Insert() functions are slightly different.

  Remove() is called from the root of the tree, rather than the node to be removed. This is different from the previous assignment. The reason for this is that you need to work back up the path from the root to the removed node to rebalance the tree. Insert() now returns the new subtree rooted where the previous one was, as rotations may have changed the root.

  Read the code for the precise differences.

• In order to help with visualizing, we've provided a program rotate in the course bin/ directory, which works much like tree. In addition to the BST operations, rotate lets you rotate nodes, and compute AVL balances. help gives all the details.

  Note that rotate does not implement an AVL tree; your program should not work the same way.

• Extra-Credit: As you've already done the difficult algorithmics for the main part of the assignment, this is an exercise in software engineering rather than algorithm implementation. I'm assuming you already know something about templates; here is a good on-line template reference.

  Create the template class as a separate project, not as part of your regular program. I suggest the following. Make a new directory, and make a new makefile, perhaps using the samples from the make tutorial. Copy avl.h, avl.C, and your source files to the new directory. Remove all the graphics server stuff from avl.h and avl.C, and convert to a template class.

  Make a driver program (i.e. a main function) that implements your template with the STL string class. At a minimum, you should insert and remove some strings into your tree, printing out the state of the tree at interesting times, demonstrating rotations and AVL balancing. For more extra-credit, have the driver read in a file that specifies a sequence of insertions, deletions and tree print-outs.

  In addition to your code, make a second README file, in your extra-credit directory, explaining how your driver works (including the format for the file read in, if your driver can read in a file), and also any problems you had doing the conversion to a template class. Also, how easy was it to strip out the graphics stuff from the AVL class I gave you? Should I have written it a different way?

  This is a very open-ended extra-credit. To get the minimum extra-credit, you should have a working driver implementing an AVL tree with strings.