Description
AVL
You are to code an AVL, which is a special type of binary search tree. It must follow the same rules as
binary search trees: each node has 0-2 children, all data in the node’s left subtree is less than the parent
node’s data, and all data in the node’s right subtree is greater than the parent node’s data. However,
an AVL differs from a BST with its self-balancing rotations, which you must implement.
All methods in the AVL that are not O(1) must be implemented completely recursively. This
includes all helper methods. For methods that change the structure of the tree in some way, we highly
recommend you use a technique taught in class called pointer reinforcement.
The AVL will have two constructors: a no-argument constructor (which should initialize an empty tree),
and a constructor that takes in a collection of data to be added to the tree, and initializes the tree with
this collection of data.
Balancing
Each node has two additional instance variables, height and balanceFactor. The height variable
should represent the height of the node. If you recall, a node’s height is max(left node’s height,
right node’s height) + 1 where the height of a null is -1. The balance factor of a node should be
equal to its left child’s height minus its right child’s height. Since we’ve stored this information in each
node, you no longer need to recursively compute it.
The tree should rotate appropriately to make sure it’s always balanced. A tree is balanced if every
node’s balance factor is either -1, 0, or 1. Keep in mind that you will have to update the balancing
information stored in the nodes on the way back up the tree after modifying the tree; the variables are
not updated automatically.
Important Notes
Here are a few notes to keep in mind when switching from BST to AVL:
1. For two child remove, use the predecessor, not successor.
2. After every change to the tree, make sure to update height and balance factor fields of all nodes
whose subtrees have been modified.
3. Make sure the height method is O(1).
4
Homework 7: AVL Due: See Canvas
Grading
Here is the grading breakdown for the assignment. There are various deductions not listed that are
incurred when breaking the rules listed in this PDF and in other various circumstances.
Methods:
constructor 4pts
add 19pts
remove 24pts
get 5pts
contains 5pts
height 2pts
clear 2pts
elementsWithinDistance 14pts
Other:
Checkstyle 10pts
Efficiency 15pts
Total: 100pts
Provided
The following file(s) have been provided to you. There are several, but we’ve noted the ones to edit.
1. AVL.java
This is the class in which you will implement the AVL. Feel free to add private helper methods
but do not add any new public methods, inner/nested classes, instance variables, or
static variables.
2. AVLNode.java
This class represents a single node in the tree. It encapsulates the data, the left and right
references, the height, and the balanceFactor. Do not alter this file.
3. AVLStudentTest.java
This is the test class that contains a set of tests covering the basic operations on the AVL class.
It is not intended to be exhaustive and does not guarantee any type of grade. Write your own
tests to ensure you cover all edge cases.
Deliverables
You must submit all of the following file(s). Make sure all file(s) listed below are in each submission, as
only the last submission will be graded. Make sure the filename(s) matches the filename(s) below, and
that only the following file(s) are present. The only exception is that Canvas will automatically append
a -n depending on the submission number to the file name(s). This is expected and will be handled by
the TAs when grading as long as the file name(s) before this add-on matches what is shown below. If
you resubmit, be sure only one copy of each file is present in the submission. If there are multiple files,
do not zip up the files before submitting; submit them all as separate files.
Once submitted, double check that it has uploaded properly on Canvas. To do this, download your
uploaded file(s) to a new folder, copy over the support file(s), recompile, and run. It is your sole responsibility to re-test your submission and discover editing oddities, upload issues, etc.
5
Homework 7: AVL Due: See Canvas
1. AVL.java
6
