Preliminaries Download the template class and the driver The template class has
ID: 664801 • Letter: P
Question
Preliminaries
Download the template class and the driver
The template class has some useful functions for printing out your tree, so you should not modify these.
As usual, do not modify the driver.
Description
As we will discuss in class, binary search trees are not optimal structures. In the worst case, a degenerate BST degrades to a linked list. Here we will be taking the first steps to implementing a self-balancing BST.
Objective
Create a class AvlTree. You AVL tree class should be a generic class containingComparable items. In addition, AvlTree should have an internal class privateAvlNode, also a generic container of Comparable items.
The internal AvlNode should have the following:
Member variables:
left - The left child of this node.
right - The right child of this node.
parent - The parent of this node.
val - The (Comparable, generic) value that this node holds
Constructors - A constructor that sets val and parent
AvlTree should have the following:
Member variables:
root - The (AvlNode) root of the tree.
size - The number of nodes contained in the tree.
Constructors - A default constructor that sets the root to null and the size to 0
Methods:size
return - The number of nodes in the tree.
insert - Inserts an element into the binary tree.param
elem - The element to insert in the tree (element, NOT a node)
lookup - Finds if an element is contained in the BSTparam
elem - The element to lookup
return - The element found within the tree. If the element is not found, return null
private rotateLeft - Performs a left rotation with the given node as the root.param
node - The node at which to perform the left rotation.
private rotateRight - Performs a right rotation with the given node as the root.param
node - The node at which to perform the right rotation.
The methods nthBitSet and printAscii included within the template.
Hint
Here is a diagram of left/right rotations (taken from Wikipedia):
In the diagram, a right rotation is performed with Q as the root, while a left rotation is performed with P as the root.
The image was taken from this article, which you may find useful.
If you have trouble debugging your code, you may use the method "printAscii" included within the template. This will print an ASCII drawing of your tree.
Template Class:
Driver:
Example Dialog
Explanation / Answer
class AvlTree{
private AvlNode root;
private int size;
public AvlTree(){
root=null;
}
public int getSize(){
return size;
}
public void insert(int elem){
root = insert(root, elem);
}
public int lookup(int elem){
return lookup(root, elem);
}
public rotateLeft(Node n2){
Node n1 = n2.left;
n2.left = n1.right;
n1.right = n2;
return n1;
}
public rotateLeft(Node n1){
Node n2 = n1.right;
n1.right = n2.left;
n2.left = n1;
return n2;
}
private class AvlNode{
Node left;
Node right;
Node parent;
int val;
AlvNode(){
val=0;
parent=null;
}
}