Abstract

In this lab, you will start with some code that implements a binary search tree and add functionality to ensure that the tree is balanced, using the AVL property.

This lab consists of three components:

a pre-lab, which you will prepare and submit through Gradescope;
a coding component, which you will complete and submit via your Bitbucket repository;
a post-lab writeup, which you will prepare and submit through Gradescope.

The pre-lab and post-lab are two separate assignments, due on different days. They should be prepared following the guidelines in the eHomework Guide.

Pre-Lab Component (20%)

The pre-lab is intended to be completed before the coding component; it will help ensure that you understand the code and can work out an implementation strategy. For this reason, the pre-lab is due earlier than the other two components of the lab.

To succeed at the pre-lab, you need to read the provided code described below and be able to answer basic questions about its methods. These questions are given in the pre-lab document.

What to Turn In (READ CAREFULLY)

Prepare a brief PDF document that answers each of the questions asked in the pre-lab, following the eHomework guidelines. Submit your document to the "Lab 11 Pre-Lab" assignment via Gradescope by its due date.

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 10;
compute the balance at the root of a subtree (which is the height of the root's right subtree minus that of its left subtree);
implement the AVL rebalancing operation, along with the supporting rotation operations;
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.
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 pretty much as expected for 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.

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'll have to 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 the stored subtree height information.
rebalance() rebalances a tree whose balance factor is +2 or -2, using rotations (see below) 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.

Testing Your Implementation

We have provided you with two JUnit test files to check that your AVL tree is behaving as intended: TestBalancedTreeInsert tests all operations except remove(), and TestBalancedTree tests all operations including remove() . As always, passing the unit test does not guarantee that your table is correct -- you are ultimately responsible for correctness -- but failing it does indicate that there is a problem you need to fix.

Some of the tests build trees that 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 delete) unless your tree is properly balanced.

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:

Make sure your code passes the JUnit tests as we originally gave them to you. Our lab autograder script will use the output of these unit tests as part of the assessment of your code's correctness when grading.
Make sure you eliminate or disable any print statements or other extraneous code, other than what is needed to implement the table, 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.
Make sure you do a Team/Pull on your repository before attempting to push your code. Remember, pull before push!
You must both commit and push all of your code to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.

Please check that your code was pushed by logging into bitbucket.org, clicking on your repository, and viewing the source code to verify that it's the most up-to-date version.

Code that is not pushed to Bitbucket will not be graded, and you will not receive credit for it, even if your local copy is correct. Unless you have an unpushed commit with a timestamp prior to the due date, we will not accept it later, as we have no way to verify that the code was completed prior to the deadline.

Post-Lab Writeup Component (30%)

The post-lab writeup asks you to reflect on your implementation and to think about possible extensions.

What to Turn In (READ CAREFULLY)

Prepare a PDF document that answers each of the questions asked in the post-lab, following the eHomework guidelines. Submit your writeup via Gradescope by its due date.