CS 367 - Assignment 4 Assignment 4 Due Wednesday, July 20 at 9:00 AM Be sure you are acquainted with my collaboration policy and my late policy, both found on the main course webpage. If you are working with a partner, be sure to include both of your names. Introduction In this assignment, you will finish an implementation of an AVL tree. Specifically, you will write a method to balance the tree and a method to perform an in-order traversal of the tree--the rest, I've implemented for you. In order to complete this assignment, you'll need these files: AVLTree.java is the Java file that you'll be editing and handing in. AVLNode.java is my implementation of the a node in an AVL tree, and is used by AVLTree.java. You will use this file, but will not need to edit it or turn it in. You will need to create your own tests to check your code. Make sure to test for all possible balancing cases, null pointers, edge cases, etc. Acquaint Yourself with the Code The file AVLTree.java already contains quite a bit of code. Read through it and familiarize yourself with what it is doing. It contains the following methods: AVLTree() - constructs empty tree balance() - balances a tree with a given root. YOU WILL IMPLEMENT THIS. delete() x 2 - public/helper pair. Deletes a node with given key. Uses balance(), but otherwise basically the same algorithm we saw in class. height() - returns the height of a given tree or sub-tree. Same as node.getHeight() except accounts for trees with height of -1. Very useful for avoiding NullPointerExceptions. inOrder() - returns a string representing an in-order traversal of the tree. YOU WILL IMPLEMENT THIS. insert() x 2 - public/helper pair. Inserts a given key->value pair. Note: overwrites old value if key already exists in tree. levelOrder() - returns a string representing a level-order traversal of the tree. Uses a queue! Effectively prints out the tree level by level. Useful for debugging. lookup() x 2 - public/helper pair. Retrieves the data associated with a given key. Basically the same algorithm we saw in class. smallest() - retrieves the smallest key in a given tree. Basically the same method we saw in class. toString() - uses the inOrder() method to override Object.toString(). Useful for debugging. Most of this code is just implementing algorithms we've already talked about in class. Though you will only need to implement a couple of methods, make sure you understand everything that is going on. Implementing the balance() and inOrder() Methods Your job for this assignment is to implement these two methods. For the balance() method, you are given a node and must check for the four cases of unbalance that we talked about in class (LL, LR, RL, RR). Once you have rearranged the pointers appropriately, you should return the new tree. If the tree is already balanced, you should of course return its root unchanged. Note: make sure to pay attention to heights! For the inOrder() method, you will perform an in-order traversal of the tree to create a string representation of it. This is used by the overridden toString() method. A node should be represented by the string representations of its key and value, separated by "->" and surrounded by curly-braces ("{" and "}"). For example, if you have a tree mapping the Integers from 1 to 5 with their written out strings, the toString() method of your tree should return: "[ { 1 -> one } { 2 -> two } { 3 -> three } { 4 -> four } { 5 -> five } ]" Note: all Objects have the toString() method implemented, and you are encouraged to use this to get the string representations of your keys and values. Turning in your work To hand in your program, copy AVLTree.java and any other files needed to create AVLTree.class (not including the files with which I provided you) to the following directory: /p/course/cs367-ealexand/handin/login-name/P2 Use your actual CS login name (not your UW NetID!) in place of login-name. Be sure that a comment at the top of the AVLTree.java file gives the name(s) of the author(s) of the code. If you worked with a partner, then only one of you should turn in the program files as specified above. It doesn't matter which partner hands in the program files. Do not copy any ".class" files, and do not create any subdirectories in your handin directory. Note that for this assignment, you should test your program thoroughly, but you do not need to hand in your test data. You will be graded on program correctness, error checking, and general style. Solution Assignment 4 Solution
