Preliminaries Download the template class and the driver The template class has
ID: 3764299 • 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 containing Comparable items. In addition, AvlTree should have an internal class private AvlNode, 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.
Example Dialog
Lookup test succeeded.
----------------
Rotation test:
Jose
|- Louie
| |- Nathan
| `- Kiley
`- Jaki
`- Beverly
Left rotation around 'Jose'
Louie
|- Nathan
`- Jose
|- Kiley
`- Jaki
`- Beverly
Right rotation around 'Jose'
Louie
|- Nathan
`- Jaki
|- Jose
| `- Kiley
`- Beverly
Right rotation around 'Louie'
Jaki
|- Louie
| |- Nathan
| `- Jose
| `- Kiley
`- Beverly
----------------
Randomized rotation test:
Random tree:
0
`- 2
|- 4
| `- 3
`- 1
Left rotation around 2
0
`- 4
`- 2
|- 3
`- 1
Right rotation around 1
0
`- 4
`- 2
|- 3
`- 1
Right rotation around 2
0
`- 4
`- 1
`- 2
`- 3
----------------
Explanation / Answer
import java.util.LinkedList;
import java.util.Queue;
public class AVLTree<T extends Comparable<T>> {
Node<T> root;
public AVLTree() {
root = null;
}
private int depth(Node<T> node) {
if (node == null)
return 0;
return node.getDepth();
// 1 + Math.max(depth(node.getLeft()), depth(node.getRight()));
}
public Node<T> insert(T data) {
root = insert(root, data);
switch (balanceNumber(root)) {
case 1:
root = rotateLeft(root);
break;
case -1:
root = rotateRight(root);
break;
default:
break;
}
return root;
}
public Node<T> insert(Node<T> node, T data) {
if (node == null)
return new Node<T>(data);
if (node.getData().compareTo(data) > 0) {
node = new Node<T>(node.getData(), insert(node.getLeft(), data),
node.getRight());
// node.setLeft(insert(node.getLeft(), data));
} else if (node.getData().compareTo(data) < 0) {
// node.setRight(insert(node.getRight(), data));
node = new Node<T>(node.getData(), node.getLeft(), insert(
node.getRight(), data));
}
// After insert the new node, check and rebalance the current node if
// necessary.
switch (balanceNumber(node)) {
case 1:
node = rotateLeft(node);
break;
case -1:
node = rotateRight(node);
break;
default:
return node;
}
return node;
}
private int balanceNumber(Node<T> node) {
int L = depth(node.getLeft());
int R = depth(node.getRight());
if (L - R >= 2)
return -1;
else if (L - R <= -2)
return 1;
return 0;
}
private Node<T> rotateLeft(Node<T> node) {
Node<T> q = node;
Node<T> p = q.getRight();
Node<T> c = q.getLeft();
Node<T> a = p.getLeft();
Node<T> b = p.getRight();
q = new Node<T>(q.getData(), c, a);
p = new Node<T>(p.getData(), q, b);
return p;
}
private Node<T> rotateRight(Node<T> node) {
Node<T> q = node;
Node<T> p = q.getLeft();
Node<T> c = q.getRight();
Node<T> a = p.getLeft();
Node<T> b = p.getRight();
q = new Node<T>(q.getData(), b, c);
p = new Node<T>(p.getData(), a, q);
return p;
}
public boolean search(T data) {
Node<T> local = root;
while (local != null) {
if (local.getData().compareTo(data) == 0)
return true;
else if (local.getData().compareTo(data) > 0)
local = local.getLeft();
else
local = local.getRight();
}
return false;
}
public String toString() {
return root.toString();
}
public void PrintTree() {
root.level = 0;
Queue<Node<T>> queue = new LinkedList<Node<T>>();
queue.add(root);
while (!queue.isEmpty()) {
Node<T> node = queue.poll();
System.out.println(node);
int level = node.level;
Node<T> left = node.getLeft();
Node<T> right = node.getRight();
if (left != null) {
left.level = level + 1;
queue.add(left);
}
if (right != null) {
right.level = level + 1;
queue.add(right);
}
}
}
}
-------------------------------------------------------------------------------------------------------
public class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
private T data;
private Node<T> left;
private Node<T> right;
public int level;
private int depth;
public Node(T data) {
this(data, null, null);
}
public Node(T data, Node<T> left, Node<T> right) {
super();
this.data = data;
this.left = left;
this.right = right;
if (left == null && right == null)
setDepth(1);
else if (left == null)
setDepth(right.getDepth() + 1);
else if (right == null)
setDepth(left.getDepth() + 1);
else
setDepth(Math.max(left.getDepth(), right.getDepth()) + 1);
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
/**
* @return the depth
*/
public int getDepth() {
return depth;
}
/**
* @param depth
* the depth to set
*/
public void setDepth(int depth) {
this.depth = depth;
}
@Override
public int compareTo(Node<T> o) {
return this.data.compareTo(o.data);
}
@Override
public String toString() {
return "Level " + level + ": " + data;
}
}
-----------------------------------------------------------------------------------------------------
Main.java
public class Main {
public static void main(String[] args) {
AVLTree<Integer> tree = new AVLTree<Integer>();
for (int i = 1; i <= 7; i++)
tree.insert(new Integer(i));
tree.PrintTree();
}
}