cs151 - trees

CS 151 - Introduction to Data Structures

This assignment is optional.
If you do this assignment, it will only count if the grade on this assignment is an improvement on your lowest previous homework. It that case, and in that case only, the grade on this assignment will be used instead of the lowest grade.

Balancing trees (almost)

As discussed in class, and in ch 28 of the text, AVL trees are binary trees that maintain extra information with respect to maintaining balance. In this assignment you will extend the LinkedBinaryTree implementation discussed in class to maintain the AVL information. Importantly, you will not(!!!) be writing code to do the actual rotations, just maintaining the information required to determine if rotation is necessary.

Code is available either from the class website or via scp from goldengate. You will need the following files:

    /home/gtowell/Public/151/A09/StackIntf.java
    /home/gtowell/Public/151/A09/ArrayStack.java
    /home/gtowell/Public/151/A09/LinkedBinaryTree.java 
    /home/gtowell/Public/151/A09/TreeInterface.java

(You may edit the LinkedBinaryTree code to remove the use of ArrayStack if you want.)

In addition to extending the LinkedBinaryTree code to maintain AVL information you must also adjust the code so that it does not do either insertions or deletions once the tree is out of balance.

Information about the tree to be built is contained in a csv file with the following form:

Column 1: A single character, either i or d. If i, then insert a new item into the tree, if d, then delete an item from the tree.
Column 2: An integer. This will be the payload. You must use Integers as the payload, not Strings

So, for example if the data file is:

    i,10
    i,5
    i,15
    d,15
    d,12
    i,100

then the resulting tree is

        10
       /   \ 
      5    100

The files will not have poorly formatted data. However, they may include instructions to delete items that are not in the tree. Likewise the data file may include instructions to add or delete items after your code detects an AVL balance problem.

Data files are available via scp from goldengate at

        /home/gtowell/Public/151/A09/d1.csv
        /home/gtowell/Public/151/A09/d2.csv
        /home/gtowell/Public/151/A09/d3.csv

Requirements

Extend the LinkedBinaryTree class to maintain AVL information during both insertion and deletion. Extension may take the form of adding new methods or modifying existing methods. (That said, do not completly replace the existing add and remove methods. Instead modify them as needed to keep AVL information up to date.)
Extend the printPostOrder method to also show the AVL information
When deleting nodes, always use the inorder predecessor. (This is what the supplied code already does.).
Use comments both to explain your changes and to make the sites of all of your code changes easy to find.
Read information about insertion and deletion from a csv file
Accept the name of the csv data file from the command line.
Handle file exceptions gracefully.
Stop processing an input file if (when) the tree is determined to be out of AVL balance.
After finishing processing of an input file, print out the resulting tree using printPostOrder.
Create your own data file that shows your code stopping processing the file because of an AVL balance problem.
In your readme, include a statement about what went out of AVL balance in the tree built from your data file

What to hand in

All code, well commented. Include code files even if you did not change them if they are required for your code to compile.
The usual README file. This should include comments about your data file as in the final requirement above.
A script file showing the output of your program on each of the data files. (From the requirements above, the output must include, but is not limited to, a post order traversal of the final tree.)
Your custom data file

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer.

The following steps for submission assume that you created a project named AssignmentN in the directory /home/YOU/cs151/

For this assignment N=9
Put the README file into the project directory
Go to the directory /home/YOU/cs151
Enter /home/gtowell/bin/submit -c 151 -p N -d AssignmentN

For more on using the submit script click here