Before continuing on, make sure you’re caught up on the lectures through 7/8. Also make sure to pull the starter code.
In this assignment your task is to complete a series of algorithms
involving a Self-Balancing Binary Search Trees, AVL
Trees. The method signatures and their explanations that you
need to implement are provided in the SelfBalancingBST
Interface. We have provided the implementation for an
EmptyBST
, and it is your job to provide the outstanding
implementation for a non-empty BST in the NonEmptyBST
class. The methods left for you to complete have a “TODO” comment above
them. We have provided getHeight
, getRight
,
getLeft
, getElement
, and
isEmpty
.
You can test your implemention in the Main
class.
The entire AVL Tree programming task has been broken up into two
smaller exercises, with the methods required by the
SelfBalancingBST
interface being divided up between
ex11
and ex12
.
For ex11
, we are expecting you to complete
findMin
, rotateLeft
, rotateRight
,
and insert
. Note that rotateLeft
and
rotateRight
are not part of the
SelfBalancingBST
interface, but are private methods that
you will need to use in your implementation of insert and remove.
The remove
, findMax
, and
contains
methods will count as part of ex12
,
but feel free to work ahead.
We have provided the fields, constructor, size
,
height
, getRight
, getLeft
,
isEmpty
and getValue
. The constructor takes no
arguments and creates an empty AVLTree. You can either use a null
element value to indicate that a tree is empty or explicitly keep track
of whether a tree is empty with a boolean field (you would have to add
this field).
Inserting and removing elements to a self-balancing tree may result is a different root object after the insertion or removal because of self-balancing operations. This is why these methods as declared in the interface return the potentially different post-operation root of the tree. In your AVLTree implementation, this means you will need to recapture the result whenever you recursively do something to a child.
Self balancing trees are one of the more difficult Data Structures to implement so we highly recommend making use of the debugger to help with any issues you may run into. Here is a tutorial on how to get started with the dubugger in IntelliJ: https://www.jetbrains.com/help/idea/debugging-your-first-java-application.html. The TAs also went over this during the review on 7/7. The recording is posted to the course webpage. We are happy to help you with this in office hours, too. As always you should be writing your own JUnits to test your code instead of only relying on the autograder.
Hints and Notes
It may be helpful to write some additional helper methods beyond the basic rotation methods. Some ideas might be:
updateHeightAndSize
: a void method that updates the
_size
and _height
fields of the AVL tree. This
would be called after a rotation, or after an insertion or
deletion.
fixIfImbalanced
: a void method that checks if the
tree is imbalanced. If so, perform the necessary rotations. This would
be called after an insertion or deletion.
These are just two ideas, feel free to structure your code however you think makes sense!
“Push” your work up to GitHub for backup. By creating “commits”, which you can think of as versioned checkpoints in your workspace, you are not at risk of losing your work. It’s easy to revert back to an old version or to restore your entire workspace on a different computer.
main
branch, and needs to
be pushed to your remote backup.USERNAME
with your GitHub
username:
https://github.com/summer-210/summer210-workspace-USERNAME
All that’s left now is to hand-in your work on Gradescope for grading.
Before doing so, you need to know that before an assignment’s deadline you can resubmit work as many times as you need to without penalty. Portions of assignments are autograded and will provide near-immediate feedback. We want you to resubmit as many times as it takes you in order to earn full autograding credit!
Login to Gradescope and select the assignment named “EX11 - AVL Trees Part 1” You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to IntelliJ.
Along the bottom of your window, you should see an option to open a terminal integrated into IntelliJ.
Type the following command (all on a single line):
./submit.sh ex11
In the file explorer pane, look to find the zip file named “ex11_submission.zip”. The script will call it an ex11 submission since that is the package we zipped. If you right click on this file “Open in -> Finder” on Mac, the zip file’s location on your computer will open. Upload this file to Gradescope to submit your work for this exercise.
We are working on rewriting the script to work for Windows! Until
then, please navigate to your course workspace in a File Explorer
window. Then right click on the src
folder in your
exercises directory and compress the directory into a zip folder. You
can name it “ex11_submission.zip”
When you upload it to Gradescope, please delete any files that showed
up in the src/
folder that were not actually part of
ex11
.