CSC220 Project Lab No. 2
Due: 11:59PM, Friday, December 3
The goal of this lab is to write a code for an AVL tree.
The textbook offers one implementation that uses series of
interfaces and classes, but here we want to build a code using
a single JAVA file.
The idea we will use here is an internal Node class that holds
a data object from a generic class E, which is comparable,
and has two references to Node objects that represent its
left and right children. In addition, since the tree height
plays an essential role in AVL trees, each node remember the tree
height of itself, the tree height of its left child, and the tree
height of its right child. Here the general rule of
the height of a node = MAX(the height of left child,
the height of right child)+1
applies.
When a new node is created with an object from class E, the
data is stored in the corresponding data field, the left and
right children are set to null, and the height value will be set
to 0 for the node, and -1 for each of the children.
Here is a partially written code for AVL.java
that you can base your code.
The methods necessary for this internal class is the following:
- public boolean rotateRight():
This is a method for executing right rotation.
- public boolean rotateLeft():
This is a method for executing left rotation.
- public boolean isLeftHeavy():
This is a method for testing whether the node is left-heavy.
- public boolean isRightHeavy():
This is a method for testing whether the node is right-heavy.
- public boolean isBalanced():
This is a method for testing whether the node (but not subtree
rooted at the node)is balanced.
- public boolean find(E v):
This is a method for testing whether the subtree has the given
data object v.
- public void add(E v):
This is a method for adding to the subtree rooted at the node
a new data object v, which is guaranteed not to exist in the subtree.
- private E findLeftmost():
This is a method for finding the leftmost node in the subtree.
- private void addToList(List< E> list):
This is a method for executing inorder traversal on the subtree
and append the values encountered during the traversal to the list.
- private void fix():
This is a method for checking whether imbalance exists at the node
and if so fixing it.
- public boolean remove(E v):
This is a method for removing the data object v, which is guaranteed
to exist in the subtree rooted at that node.
- public String neatPrint(int depth):
This is a method for printing the output of the contents of the subtree
with the depth value, where the depth value is used for indentation.
Of these you must write the code for:
rotateRight, rotateLeft,
find, fix, findLeftMost, and remove.
For most of the methods there are detailed instructions as to
how to design the code in the Java file.
Using this Node class you can write an AVL class, which consists
of two data fields: root, which is a Node class object, and numberOfData,
which is an integer that holds the number of data stored in the tree.
It comes with the following methods, all of which are already written.
- public int size()
- public boolean insert(E data)
- public boolean delete(E data)
- public boolean find(E data)
- public List < E &RT toList()
- public Iterator < E > toList()
- public String neatPrint()
- public static void main(String[] args)
The main method here is used to check correctness of the AVL tree.
Here is a sample program, LabAVL.jar.