Self-awareness report

Coding Component (50%)

We've provided you with an implementation of an unbalanced binary search tree. The tree implements an ordered dynamic set over a generic comparable type T. Supported operations include insertion, deletion, min, max, and testing whether a value is in the set (via the exists method). Because it's a set, duplicates are not allowed, and the insert operation will not insert a value if it is already present.

We have implemented the BST operations in a recursive style. For example, inserting a value into a tree recurses down the tree seeking the correct place to add a new leaf. Each recursive call returns the root of the subtree on which it was called, after making any modifications needed to the subtree to perform the insertion. Deletion is implemented similarly.

Your job is to add the functionality needed to keep the tree balanced using the AVL property. In particular, you will need to

· augment the tree to maintain the height of each of its subtrees, as discussed in Studio;

· compute the balance at the root of a subtree (which is the height of the root's left subtree minus that of its right subtree);

· implement the AVL rebalancing operation, along with the supporting rotation operations; and

· call the height maintenance and rebalancing operations at the appropriate times during insertion and deletion.

Code Outline

There are two main source code files you need to consider, both in the avl package:

· TreeNode.java implements a class TreeNode that represents a node of a binary search tree. It holds a value (the key of the node) along with child and parent pointers. It has a height data member that is currently not used for anything. You should not modify this file, but you need to understand its contents.

· AVLTree.java implements an ordered set as a binary search tree made out of TreeNode objects.

The AVLTree class provides an interface that includes element insertion and deletion, as well as an exists() method that tests whether a value is present in the set. It also offers min() and max() methods. These methods all work as given for (unbalanced) BSTs, using the algorithms we discussed in lecture.

To implement the AVL balancing method, you will need to fill in some missing code to maintain the height of each subtree and perform rebalancing. Look for the 'FIXME' tags in AVLTree.java to see which methods you must modify.

Height Maintenance

You'll need to set the height data member each time a new leaf is allocated in the tree. You can then maintain the height as part of insertion or deletion using the incremental updating strategy you worked out in Studio 10, Part C.

The update procedure updateHeight() takes in a node and updates its height using the heights of its two subtrees. It should run in constant time.

You'll need to call updateHeight() wherever it is needed – in insertion, deletion, and perhaps elsewhere.

Rebalancing

You must implement four methods as part of AVL rebalancing:

· getBalance() computes the balance factor of a subtree given its root. It should run in constant time using stored subtree height information.

· rebalance() rebalances a tree whose balance factor is +2 or -2, using rotations according to the AVL rebalancing algorithm.

· rightRotate() performs a right rotation on a subtree.

· leftRotate() performs a left rotation on a subtree.

In addition to implementing these methods, you will need to call the rebalancing algorithm as needed during insertion and deletion.

Tree-printing output

The codebase provides utility functions for printing binary trees in the file avl/util/TreeToStrings.java . Many of the tests provided in the codebase call these utility functions during normal operation and/or error printing, some tests have print calls commented out so you can add them during debugging, and you are encouraged to call the functions in your own tests as well. It is therefore to your great advantage to understand the format in which these functions print a tree.

The most commonly-used print method in the test code, formatVertically , prints a tree in  prefix order  (i.e. parent, then left subtree, then right subtree). One node is printed per line, with the depth of the node equivalent to the number of '|' characters printed before it. For example, if the following values are inserted into an empty BST in order:

2, 1, 3

…then formatVertically will print the following:

Root-2

| L-1

| R-3

As a slightly larger example, if the following values are inserted into an empty BST in order:

7, 4, 10, 3, 5, 8, 17, 15, 20

…then formatVertically` will print the following:

Root-7

| L-4

| | L-3

| | R-5

| R-10

| | L-8

| | R-17

| | | L-15

| | | R-20

, represeting the tree: 

Unit tests

The following unit tests are provided in the avl.test package in your repository:

1. TestSmall: contains a variety of tests for insertion and deletion, some of which require no rebalancing and some of which require rebalancing due to all four unbalanced AVL cases. These tests should be a great help in debugging your code, so it is to your advantage to be familiar with all of them before debugging.

2. TestFull: tests full functionality on large trees. Some of trees built by this test are quite large (100,000 elements or more). These large tests may fail to finish in a reasonable amount of time or may cause Java to crash with a stack overflow (due to very deep recursion in insert or delete) unless your tree is properly balanced.

3. TestCustom: Three empty function stubs that you can fill in with your own tests as you see fit.

The autograder will run the tests in TestSmall.java and TestFull.java as given to determine your coding grade (TestSmall: 75% of coding credit, TestFull: 25% of coding credit).

All tests should finish within a few seconds, and the autograder will time out and record zero credit after 20 seconds.

As always, passing the unit test does not guarantee that your code is correct – you are ultimately responsible for correctness – but failing it does indicate that there is a problem you need to fix.

If you want to check your understanding of how AVL trees work or see what tree you should get for a small input, you might find  this AVL tree visualizer  helpful.

What to Turn In (READ CAREFULLY)

To complete this portion of the lab, you must do the following:

1. Make sure you have not modified any files besides AVLTree.java.

2. Make sure your code passes the JUnit tests as given in your repository.

3. Make sure you eliminate or disable any print statements or other extraneous code that you may have used for debugging. Extraneous code may slow down your implementation to the point that our autograder will fail it for taking too long to run.

4. Make sure you do a Team/Pull on your repository before attempting to push your code. Remember,  pull before push!

5. You must both commit and push all of your code to your repository AND submit it to Gradescope. It's best to commit from the top-most level of your repository, which bears your name and student ID. If you do not push your code to your GitHub repository, Gradescope will not be using the latest version of your code for testing.