I'm writing an AVL Tree class and my professor has included some tests for our code. I have passed all the tests except three, and the three tests I'm failing seem to indicate that when elements are added to or removed from the tree, the tree doesn't balance itself when necessary. I've been trying to debug it, but I just can't seem to find the error. Could someone please point out what I'm missing?
EDIT: Failed tests: RemoveRoot - removes the root of the AVL tree and replaces it with its successor. AddManySingle - adds several elements and forces single rotation. AddManyDouble - adds several elements and forces double rotation.
private int count, height;
private AVLNode < E > root;
public AVLTree() {
root = null;
count = 0;
height = 0;
}
//the private inner Node class
private class AVLNode < E > {
private int height, bf;
private E data;
private AVLNode < E > left, right;
public AVLNode() {
data = null;
left = right = null;
bf = 0;
height = 0;
}
public AVLNode(E data) {
this.data = data;
left = right = null;
bf = 0;
height = 0;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public AVLNode < E > getLeft() {
return left;
}
public void setLeft(AVLNode < E > left) {
this.left = left;
}
public AVLNode < E > getRight() {
return right;
}
public void setRight(AVLNode < E > right) {
this.right = right;
}
public int getBF() {
return bf;
}
public void setBF() {
if (right == null && left == null) {
bf = 0;
} else if (right == null) {
bf = this.getLeft().getHeight();
} else if (left == null) {
bf = 0 - this.getRight().getHeight();
} else {
this.bf = this.getLeft().getHeight() - this.getRight().getHeight();
}
}
public void setBF(int theBalanceFactor) {
bf = theBalanceFactor;
}
/**
* The getHeight method computes the height of an AVL tree.
* @return The height of the AVL tree.
*/
public int getHeight() {
return this == null ? -1 : this.height;
}
public void setHeight() {
int leftHeight = (left == null) ? -1 : left.getHeight();
int rightHeight = (right == null) ? -1 : right.getHeight();
height = 1 + Math.max(leftHeight, rightHeight);
}
public void setHeight(int theHeight) {
height = theHeight;
}
}
//the private inner Iterator class
private class AVLIterator implements Iterator < E > {
private AVLNode < E > nextNode;
private Stack < AVLNode < E >> stack;
public AVLIterator() {
nextNode = root;
stack = new Stack < AVLNode < E >> ();
while (root != null) {
stack.push(root);
root = root.getLeft();
}
}
//Returns true if the iteration has more datas.
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
//Returns the next data in the iteration.
@Override
public E next() {
if (!hasNext()) {
throw new NoSuchElementException("No next element.");
}
AVLNode < E > node = stack.pop();
E result = node.data;
if (node.right != null) {
node = node.right;
while (node != null) {
stack.push(node);
node = node.left;
}
}
return result;
}
//Removes the last data in the iteration.
@Override
public void remove() {
throw new UnsupportedOperationException("Invalid operation for support list.");
}
}
/**
* Rotate binary tree node that has a right child.
* Update heights, then return new root.
* n1 is the imbalanced node
*/
private AVLNode < E > rotateWithRightChild(AVLNode < E > n1) {
AVLNode < E > n2 = n1.right;
n1.right = n2.left;
n2.left = n1;
return n2;
}
/**
* Rotate binary tree node that has a left child.
* Update heights, then return new root.
*/
private AVLNode < E > rotateWithLeftChild(AVLNode < E > n2) {
AVLNode < E > n1 = n2.left;
n2.left = n1.right;
n1.right = n2;
return n1;
}
/**
* Double rotate binary tree node: first left child
* with its right child; then node n3 with new left child.
* Update heights, then return new root.
*/
private AVLNode < E > doubleWithLeftChild(AVLNode < E > n3) {
n3.left = rotateWithRightChild(n3.left);
return rotateWithLeftChild(n3);
}
/**
* Double rotate binary tree node: first right child
* with its left child; then node n1 with new right child.
* Update heights, then return new root.
*/
private AVLNode < E > doubleWithRightChild(AVLNode < E > n1) {
n1.right = rotateWithLeftChild(n1.right);
return rotateWithRightChild(n1);
}
//updates height and balance factor
private void updateHeightAndBF(AVLNode < E > node) {
int leftHeight, rightHeight, bf = 0, height = 0;
if (node != null) {
if (node.getLeft() == null) {
leftHeight = -1;
} else {
leftHeight = node.left.height;
}
if (node.getRight() == null) {
rightHeight = -1;
} else {
rightHeight = node.right.height;
}
/*if (leftHeight >= rightHeight) {
height = leftHeight + 1;
} else if (rightHeight >= leftHeight) {
height = rightHeight + 1;
}*/
height = Math.max(leftHeight, rightHeight) + 1;
bf = leftHeight - rightHeight;
node.setHeight(height);
node.setBF(bf);
} else {
height = -1;
}
}
/**
* private helper method.
* Balances a node by updating balance
* factor when a node is removed from
* or added to the AVL tree.
*
* @param node the node that is being balanced
*/
private AVLNode < E > balance(AVLNode < E > node) {
int hLeft, hRight;
if (node == null) {
return node;
}
if (node.bf == 2) {
if (node.left.bf == 1) {
node.left = rotateWithLeftChild(node);
} else if (node.left.bf == -1) {
node.left = doubleWithLeftChild(node);
}
} else if (node.bf == -2) {
if (node.right.bf < 0) {
node.right = rotateWithRightChild(node);
} else if (node.right.bf == -1) {
node.right = doubleWithRightChild(node);
}
}
return node;
}
/**
* Adds the item to the tree. Duplicate items and null items should not be added. O(log n)
*
* @param item the item to add
* @return true if item added, false if it was not
*/
@Override
public boolean add(E item) { // TODO
int theSize = size();
if (root == null && item != null) { //null check here for item
root = new AVLNode < E > (item);
count++;
return true;
} else if (item == null) {
return false;
} else {
add(root, item);
root = balance(root);
}
return (count != theSize);
}
/**
* private helper method for the add() method.
* Adds the item to the tree. Duplicate items and null items should not be added.
* Runs in O(log n) expected time, may be linear time in worst case
*
* @param value the item to add
* @return true if item added, false if it was not
*/
private boolean add(AVLNode < E > node, E value) { // TODO
if (value.equals(node.getData()) || value == null) {
//if it's a duplicate or null
return false;
}
if (value.compareTo(node.data) < 0) {
AVLNode < E > left = node.left;
if (left == null) {
node.left = new AVLNode < E > (value);
count++;
updateHeightAndBF(node);
balance(node);
return true;
} else updateHeightAndBF(node);
balance(node);
return add(left, value);
} else if (value.compareTo(node.data) > 0) {
AVLNode < E > right = node.right;
if (right == null) {
node.right = new AVLNode < E > (value);
count++;
updateHeightAndBF(node);
balance(node);
return true;
} else {
updateHeightAndBF(node);
balance(node);
return add(right, value);
}
}
return false;
}
/**
* returns the maximum data held in the tree. null if tree is empty.
* runs in O(log n) expected, may be linear in worst case
*
* @return maximum item or null if empty
*/
@Override
public E max() {
if (isEmpty()) {
return null;
}
return max(root).data;
}
/**
* a private helper method for the max() method.
*
* @return maximum Node or null if empty
*/
private AVLNode < E > max(AVLNode < E > x) {
if (x.getRight() == null) { //the rightmost node from the root
//is larger than the root, which is larger than the leftmost
//node from the root. so, if the rightmost node is null,
// that means the root node is the maximum data in the tree
return x;
} else {
return max(x.getRight());
}
}
/**
* returns the number of items in the tree O(1) with variable
*
* @return the number of items in the tree
*/
@Override
public int size() {
return count;
}
/**
* O(1)
* @return true if tree has no datas, false if tree has anything in it.
*/
@Override
public boolean isEmpty() {
return size() == 0;
}
/**
* runs in O(n) worst case, and O(log n) average case.
* @return the minimum data in the tree or null if empty
*/
@Override
public E min() {
if (isEmpty()) {
return null;
}
return min(root).data;
}
/**
* private helper method for the min() method
*
* @return the minimum Node in the tree or null if empty
*/
private AVLNode < E > min(AVLNode < E > y) {
if (y == null) {
return null;
} else if (y.left == null) { //the leftmost node from the root
//is smaller than the root, which is smaller than the rightmost
//node. so, if the leftmost node is null,
// that means the root node is the minimum data in the tree
return y;
} else {
return min(y.left);
}
}
/**
* Checks for the given item in the tree. O(log n)
*
* @param item the item to look for
* @return true if item is in tree, false otherwise
*/
@Override
public boolean contains(E item) {
return contains(root, item);
}
/**
* private helper method for the contains() methods
* Checks for the given item in the tree.
* runs in O(log n) expected, may be linear in worst case
*
* @param root the starting point
* @param item the item to look for
* @return true if item is in tree, false otherwise
*/
private boolean contains(AVLNode < E > root, E item) {
if (root == null || isEmpty()) {
return false;
}
if (item.compareTo(root.getData()) == 0) { //if item is
//equal to the data in the root Node, return true
return true;
} else {
if (item.compareTo(root.getData()) < 0) { //if item is less than data
AVLNode < E > left = root.getLeft(); //go to the left node
return (contains(left, item)); //call contains() method with the left node
} else if (item.compareTo(root.getData()) > 0) { //if item is more than data
AVLNode < E > right = root.getRight(); //go to the right node
return (contains(right, item)); //call contains() method with the right node
} else {
return true;
}
}
}
/**
* removes the given item from the tree O(log n). if the item is found
* and removed, balance the tree
*
* @param item the item to remove
* @return true if item removed, false if item not found
*/
@Override
public boolean remove(E item) {
int theSize = size();
root = remove(root, item);
return (count != theSize);
}
/**
* private helper method for the remove() method
* removes the given item from the tree
* runs in O(log n) expected, may be linear in worst case
* uses in-order successor
*
* @param node the starting point
* @param item the item to remove
* @return the node if the specified is node in the tree, null otherwise
*/
private AVLNode < E > remove(AVLNode < E > node, E item) { //TODO
if (node == null || item == null) {
return null;
}
if (root == null) {
return root;
}
if (item.compareTo(node.data) < 0) {
updateHeightAndBF(node);
balance(node);
node.left = remove(node.left, item);
} else if (item.compareTo(node.data) > 0) {
updateHeightAndBF(node);
balance(node);
node.right = remove(node.right, item);
} else if (node.left != null && node.right != null) { //two child nodes
AVLNode < E > succ = min(node.right);
node.data = succ.data;
updateHeightAndBF(node);
balance(node);
node.right = remove(node.right, node.data);
} else {
node = (node.left != null) ? node.left : node.right;
count--;
updateHeightAndBF(node);
return balance(node);
}
return node;
}
/**
* Runs in linear time, O(n)
* @return a list of the data in post-order traversal order
*/
@Override
public List < E > getPostOrder() {
List < E > postOrderList = new ArrayList < E > (size());
recPostOrder(root, postOrderList);
return postOrderList;
}
/**
* private helper method for the getPostOrder() method
* Runs in linear time, O(n)
*/
private void recPostOrder(AVLNode < E > theRoot, List < E > theList) {
if (theRoot != null) {
recPostOrder(theRoot.left, theList);
recPostOrder(theRoot.right, theList);
theList.add(theRoot.data);
}
}
/**
* Runs in linear time, O(n)
* @return a list of the data in pre-order traversal order
*/
@Override
public List < E > getPreOrder() {
List < E > preOrderList = new ArrayList < E > (size());
recPreOrder(root, preOrderList);
return preOrderList;
}
/**
* private helper method for the getPreOrder() method
* Runs in linear time, O(n)
*
*/
private void recPreOrder(AVLNode < E > theRoot, List < E > theList) {
if (theRoot != null) {
theList.add(theRoot.getData());
recPreOrder(theRoot.getLeft(), theList);
recPreOrder(theRoot.getRight(), theList);
}
}
/**
* Runs in linear time
* @return a list of the data in pre-order traversal order
*/
public List < E > getInOrder() {
List < E > inOrderList = new ArrayList < E > (size());
recInOrder(root, inOrderList);
return inOrderList;
}
/**
*
* private helper method for the getInOrder() method
* Runs in linear time
*
*/
private void recInOrder(AVLNode < E > theRoot, List < E > theList) {
if (theRoot != null) {
recInOrder(theRoot.left, theList);
theList.add(theRoot.data);
recInOrder(theRoot.right, theList);
}
}
/**
* Runs in linear time, O(n)
* @return a list of the data in level-order traversal order
*/
@Override
public List < E > getLevelOrder() {
List < E > data = new ArrayList < E > ();
Queue < AVLNode < E >> queue = new LinkedList < AVLNode < E >> ();
if (this.isEmpty()) {
return data;
} else {
queue.add(root);
}
while (!queue.isEmpty()) {
AVLNode < E > x = queue.remove();
if (x != null) {
data.add(x.getData());
if (x.getLeft() != null) {
queue.add(x.getLeft());
}
if (x.getRight() != null) {
queue.add(x.getRight());
}
}
}
return data;
}
/**
* O(1) [ignore garbage collection costs]
*
* Removes all the datas from this tree
*/
@Override
public void clear() {
root = null;
count = 0;
}
/**
* returns an iterator over this collection
* iterator is based on an in-order traversal
*/
@Override
public Iterator < E > iterator() {
return new AVLIterator();
}
}