CISC220 F2014 Lab6

NOTE: The lab due date has been changed to Monday, October 27. This is a 4-day extension.

The AVL starter code below has been updated from the original. It corrects some bugs in rotate_right() and rotate_left(), and adds a function setAllBalanceFactors() which traverses the entire tree and writes a new value in balanceFactor at each node. This function is called automatically after rotations

Lab #6

I have provided a partial implementation of AVL trees here (UPDATED VERSION). The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written. The executable is called "avl" and it expects the name of an input file on the command line. Try running it on a few files before you start to program. It will print out information about the (unbalanced) BST that has been constructed.

For this lab your job is to fill in as much of the updateBalanceFactors() function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced.. This function is called automatically at the end of each insert().

1. C++ programming exercises

• (2 points) Update the balanceFactor values as necessary in each AVLNode of the tree. Note that as the textbook's pseudocode indicates, this only has to happen along the path from the inserted node to the root (Note: it appears that the pseudocode is only in the 4th edition of the textbook. There is a scan of it in Piazza here). The print_level_and_pretty() function prints the keys of each level's nodes in level order, followed in square brackets by their (a) recursively computed balance factor and (b) balanceFactor variable. (a) is done for you; you are just computing (b) a different way. You will know you are correct when (a) and (b) are the same. It also pretty prints a pseudo-graphical representation of the tree (using only the first character of each key string, and without lines showing the connections) so that you can get a visual sense of its balance.
• (1.5 points) Take care of the "single rotation" case to rebalance the tree. This should work for both the +2/+1 case and the -2/-1 case. Rotation functions have already been written: rotate_right(t) performs a right rotation at node t, and rotate_left(t) performs a left rotation at node t. You just need to do the correct rotation in the correct place.
• (1.5 points) Take care of the "double rotation" case to rebalance the tree. This should work for both the +2/-1 case and the -2/+1 case.

2. Submission

• Include a PDF file <Your Name>_README.pdf which contains the inputs and outputs of your program, etc. You should (a) list the input files you tested, (b) show the output of calling print_level_and_pretty() on the final tree WITH AND WITHOUT calling updateBalanceFactors() if the tree height is <= 8, and (c) show the "statistics" (from the driver() function in main.cpp) for all input files regardless of size, again with and without calling updateBalanceFactors(). Test on at least 3inarow.txt, 5words_doi.txt, partial_alphabet.txt, firstline_wap.txt, and the three cleaned files from Project #1.
• Create a single tar/zip/rar file out of the top-level and all subdirectories. This archive file should be named <Your Last Name>_Lab6.tar (or .zip or .rar, etc.).
• Submit it in Sakai by midnight at the end of Thursday, October 23