Lab 6 Instructions

Lab6Instructions.md

Lab 6 instructions

Setup

• Download the zip file from Moodle. Unzip the file in your downloads directory. You should now be seeing a project directory named "AVLTreeAssignment". The other directory, _MACOSX, can be ignored.
• Copy the AVLTreeAssignment directory and paste it into your IDEA projects directory, or simply move the AVLTreeAssignment directory into your IDEA projects directory.
• Start IntelliJ IDEA and Close your current project if you have one open. You should be seeing the IDEA welcome screen.
• Choose "Create New Project". Make sure Java is selected, and click on Next twice to get to the screen that prompts for a project name. Use the file popup to the right of the "project location" line to select the AVLTreeAssignment directory from inside your IDEA projects directory. Then click Finish to complete the Project creation process.
• Go to the File->Project Structure menu, and select the Modules tab on the sidebar. You should be seeing the src and test folders in the middle area of the window. They should be blue and green respectively. If they are not, click on them and choose the appropriate icon from the "Mark As" line. If you have done this correctly, the right side of the window should be showing you a Source Folders area with the "src" under it, and a TestFolders area with the "test" under it. Click OK.
• From the project structure on the left, navigate into the test -> avl -> AVLTreeTest class, double-click to open it. You should be seeing a lot of red marks, indicating that the JUnit framework hasn't been included. Select one of the red junit occurences in the import section of the file, and activate the "Intentions" menu by typing Alt-Enter on Windows or Option-Return on Mac. One of the options should be to add JUnit 4 to the classpath, select it.
• Right-click the AVLTreeTest file on the structure tree on the left, and choose "Run AVLTreeTest". This will run the tests in this file, and you should see 13 out of 14 failing tests. Your assignment will be to fix the code in the NonEmptyNode class so that these tests pass.
• Whenever you want to focus your tests on a single test method, rather than running all the tests, you can simply right-click that method's name and activate the "Run ..." option from the method's context menu.

Overall Structure

The project consists of 4 source files, 3 of which are already completed for you.

• There is a Node interface, which represents the kinds of things we can do with nodes. Take a look at it now to see the methods that it provides.

• This interface is implemented by the EmptyNode class, which represents the empty node and contains the suitable trivial implementations of the Node interface methods. Take a look at it now to make sure the implementations make sense.

• The NonEmptyNode class also implements the Node interface and represents non-empty nodes. These nodes hold a value, a left node reference and a right node reference. We will walk through the details of this class in the next section.

• Finally, the AVLTree class represents AVL trees. It contains a root node reference and provides its functionality by simply calling on methods on that root node. Note however the implementations, for example the implementation of insert, which is: root = root.insert(value); As many operations will change the shape of the tree, most of the node methods return the value that the node should now have (e.g. the balancing methods may create a new root node). The assignment root = root.... lets the AVLTree class allow the root node to change at the end of the method.

  The tree class also contains a main method that you will be able to run once all the other methods are implemented. This method will shuffle a number of integers, then insert them one at a time into an empty tree and show you the evolution of the tree. It will then reshuffle the integers and remove them one at a time, again showing you the evolution of the tree.

  Finally, the tree class contains three factory methods for nodes, which are used extensively in the tests to create nodes:

  • empty() returns an empty node. For efficiency, there is only one empty node and this method returns it.
  • leaf(v) returns a non-empty node that is a leaf, namely contains a value and no children.
  • node(v, left, right) returns a non-empty node with value v and children left and right. It is simply a shortcut for new NonEmptyNode(v, left, right).

  You can see examples of these constructions near the bottom of the test file, where 5 example graphs are defined: balanced, zigzig, zigzag, zagzig and zagzag. You should look at these now and draw them out on a piece of paper. (If the indenting makes the code hard to read, you can attempt to "fix" it using the menu option "Code -> Reformat Code".

NonEmptyNode class implementation

We will now implement the essential methods of the NonEmptyNode class. You will find a // TODO entry in each method that you need to implement. The instructions below will help you. You should follow the order presented here.

NOTE: Throughout this assignment all nodes/trees are assumed to be binary search trees. You can assume this to be the case and you must maintain that property.

• First off you should implement the contains(v) method. The corresponding test for it is called searchingForValueWorks. As usual, you have to compare the value to the node's value and act accordingly. The simple recursive solution is about 3 lines. Remember that this is a search tree, you should not traverse both subtrees.

• Now implement the min() method. This is meant to return the smallest value, which can be found at the leftmost node. You can check if a node is the empty node using the node's isEmpty method. The test for this method is called computingMinimumCorrectly. This can be done in one line with a use of the ternary operator (a ? b : c).

• Similarly, implement the max() method, which looks for the largest value, located at the rightmost node.

• The next method computes the height of a node. The empty node has height -1. Your implementation for non-empty nodes can simply use a divide-and-conquer algorithm based on the heights of the children. The test method for this is called nodeHeightComputedCorrectly.

• The method balanceFactor is provided for you, and it simply computes the difference between the heights of the children (left minus right).

• The method satisfiesAVL is the first larger method you need to implement. You need to check that your node's balance factor does not exceed the -1, 0, 1 range and also recursively check that your children satisfy the AVL condition. The test for this method is treeSatisfiesAVLCondition. The answer can easily fit in 1-3 lines.

• Your next method isSearchTree checks to make sure that the tree is a search tree. This means four things (and can be written as a && combination of these four):

  • Both children must be search trees themselves
  • The left child must be either empty or have a maximum value no more than the node's value.
  • The right child must be either empty or have a minimum value no less than the node's value.

  You may use your implementation of min and max from earlier. Make sure you understand WHY it is actually OK to use these even though they assumed that the tree in question was a search tree.

  The test for this method is called checkingForSearchTreePropertyWorks. The reference solution is 3-4 lines.

• The next method is provided for you, and it is called balance. It is meant to balance an arbitrary tree in the AVL sense, by recursively balancing the children and then calling balanceThisNode.

• The balanceThisNode method is also provided for you, but it is important to understand what it does. It assumes that the left and right children are already AVL trees and aims to remedy the current node, if that is needed. To that end, it computes the node's balance factor:

  • If the factor is more than 1, then this means that the tree is unbalanced towards the left, and we distinguish two cases:
    • If the left child's factor is at least 0, this means that we must rebalance using the left child of the left child (the left-left grandchild). We call this a zigzig and we call a suitable method to do the rotation.
    • If the left child's factor is less than 0, this means that we must rebalance using the left-right grandchild. We call this a zigzag, and call a suitable method.
  • If the factor is less than -1, then the tree is unbalanced towards the right, and we similarly distinguish two cases, respectively called zagzig and zagzag.
  • Lastly if the factor is within the +/- 1 bounds, then the tree is balanced and we can simply return it.

  Make sure you understand the four pictures that accompany the 4 unbalanced cases, and demonstrated by the 4 sample trees near the bottom of the test file.

• Now for your part in all this. The zigzig case involves what we would call a right rotation, which must be implemented in the rotateRight method. This is the case where the left child is promoted to its parent place, the parent becomes its right child, and various grandchildren are allocated accordingly. This is one of the two trickiest parts of the assignment. What you will need to do is the following:

  • Use a cast to cast the left child down to a NonEmptyNode instance called leftNode. This is necessary because we need to reach into the children of this left node, and it can only have children if it is in fact a non-empty node, and not an empty node. (We know that it is a non-empty node because we could not otherwise achieve the balance factor that brought us here).
  • Now you should return a new node, by calling the node method, to build the suitably rotated node:
    • The new value at the top should be the left child's value
    • The new left child would be original left-left grandchild
    • The new right child will be non-empty node produced via a call to the node method, with value the current node's value, left child equal to the old left-right grandchild, and right child equal the current node's right child

  Reasonably spaced out, the solution takes 4-6 lines.

  If you have implemented this correctly, the balanceMethodFollowsAVLRules test should be failing on the line assertBalancing_Produces(zigzag, balanced); and not earlier.

• You now need to do the same for the rotateLeft method, which handles the zagzag case of working with the right-right grandchild. After you have done this, the balanceMethodFollowsAVLRules test should be passing.

• The case of a zigzag is handled automatically as follows: We perform a left rotation on the left child, which effectively turns it into a zigzig case, and then we do a right rotation. This is carried out in the method balanceZigZag.

• The next method you need to write is insert. It naturally inserts a value at an appropriate spot (you can assume the value is not already in the array). Note that the method is supposed to return the new node, and your implementation must make use of that feature as well as preserve it. For example the implementation for the empty node (which is done in the EmptyNode class) returns a leaf(v) node. What you will need to do in your NonEmptyNode class is basically this:

  • If the value should go to the left child, then replace the left child with the value returned by inserting into the left child. Otherwise do the same for the right child.
  • Then you must return the result of calling balanceThisNode, as your node might now be unbalanced (the children are already balanced from the recursive call).

  The test for this method is called insertingPreservesAVLRules.

• The next method is deleteMax. This is meant to delete the max element. The rules for that are as follows:

  • If the right child is empty, then the node is the max, so just return the left child, which effectively removes the current node.
  • Otherwise, replace the right child with the value returned from calling deleteMax on the right child, and return the result of balanceThisNode.

  The corresponding test is called deletingMaxPreservesAVLRules.

• Lastly we come to the hardest tree operation, that of deleting an arbitrary value. The idea is as follows: We locate the maximum value on the left child; this is the next smallest value. We then perform deleteMax to remove that value, place the value in the current node, then rebalance. Here is the logic more precisely:

  • If the value on the node is the same as the one we are trying to delete, then:
    • If there is no left child, then we are at the minimum and we can simply return the right child in order to delete the node.
    • Otherwise we must find the max value of the left child, and place it in the current node, then replace the left child with the result of deleting the max of the left child, then let the flow of control continue.
  • Otherwise, if the value on the node is not the same as the one we are trying to delete, then delete from the appropriate child and replace the child with that, then let the flow of control continue.
  • In any case, return the result of calling balanceThisNode on the current node, as the deletion might have disrupted the AVL rules.

  The main test for this method is called deletingPreservesAVLRules. But once you implement this correctly all your tests should pass.

The AVLTree main method

Now you can reap the benefits of your work! In the AVLTree class you will find a main method. It constructs a list of numbers 1 through size (you can determine the size), then shuffles them and inserts them into an AVL tree. It then reshuffles them and deletes them one at a time from the tree, and shows you the evolution of the tree after each step. It's pretty sweet, check it out!

Submission

You should upload to Moodle your src/avl/NonEmptyNode file, for Lab 6 submission. Make sure you have removed all the TODO comments and written the code as simply as possible, making use of provided helper functions.