Hey everyone, I'm having big problems balancing my AVL tree implementation, and I'm needing some serious help. I've gone over my two add() methods (one receives the data, one recursively inserts it) and my balance methods (balance() is to find out which direction to balance, and if it is a double balance or not. Then i have rotateRight() and rotateLeft() methods in place, which can be called either once or twice, depending on the imbalance), and I cannot seem to find any problems whatsoever.
For reference, I have a private Node class inside of the AVLTree implementation presented below. My iterator works just fine using preorder, so feel free to use that for testing purposes.
It would be a huge help to see the light...I've spent hours and hours trying to understand what the problem is, I don't take asking questions on forums lightly. So any help would be greatly appreciated. My full code is attached below.
package s.avl;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
public class AVLTree implements Tree
{
private Node root;
private int size = 0;
private boolean removed = false;
private boolean iterator = false;
private boolean contains = false;
private final int THREE = 3;
private final int TWO = 2;
private final int ONE = 1;
private final int ZERO = 0;
public boolean add(Object e)
{
if(e == null)
throw new IllegalArgumentException();
if(iterator)
return false;
if(contains(e))
return false;
root = add(new Node(e), root);
size++;
return true;
}
private Node add(Node newNode, Node currentNode)
{
if(currentNode == null)
{
currentNode = newNode;
return currentNode;
}
else if( ((Comparable)newNode.element).compareTo( (Comparable)currentNode.element ) < 0 )
{
currentNode.left = add(newNode, currentNode.left);
}
else
{
currentNode.right = add(newNode, currentNode.right);
}
// This could be trying to insert something equal!
currentNode = balance(currentNode);
//currentNode = balance(currentNode);
updateHeight(currentNode);
return currentNode;
}
public boolean contains(Object element)
{
contains = false;
contains(new Node(element), root);
return contains;
}
private void contains(Node lookFor, Node currentNode)
{
if(currentNode == null)
return;
//System.out.println(currentNode.element + " lf: " + lookFor.element);
//System.out.println(((Comparable)lookFor.element).compareTo( (Comparable)currentNode.element ));
if( ((Comparable)currentNode.element).compareTo( (Comparable)lookFor.element ) == 0 )
{
contains = true;
return;
}
else if( ((Comparable)lookFor.element).compareTo( (Comparable)currentNode.element ) < 0 )
{
contains(lookFor, currentNode.left);
}
else
{
contains(lookFor, currentNode.right);
}
return;
}
public boolean remove(Object element)
{
if(element == null)
throw new IllegalArgumentException();
removed = false;
root = remove(new Node(element), root);
size--;
return removed;
}
private Node balance(Node n)
{
int leftHeight = getHeight(n.left);
int rightHeight = getHeight(n.right);
int difference = Math.abs(leftHeight - rightHeight);
if(difference > 1)
{
if(leftHeight > rightHeight)
{
if(getHeight(n.left.left) < getHeight(n.left.right))
{
Node temp = n.left.right;
System.out.println("Double rotate left right");
rotateLeft(n.left);
rotateRight(n);
return temp;
}
else
{
Node temp = n.left;
System.out.println("Single rotate right");
rotateRight(n);
return temp;
}
}
else if(leftHeight < rightHeight)
{
if(getHeight(n.right.right) < getHeight(n.right.left))
{
Node temp = n.right.left;
System.out.println("Double rotate right left");
rotateRight(n.right);
rotateLeft(n);
return temp;
}
else
{
Node temp = n.right;
System.out.println("Single rotate left");
rotateLeft(n);
return temp;
}
}
}
return n;
}
private void rotateRight(Node n)
{
System.out.println("Rotating " + n.element);
Node temp = n.left;
n.left = temp.right;
temp.right = n;
updateHeight(n);
updateHeight(temp);
}
private void rotateLeft(Node n)
{
System.out.println("Rotating " + n.element);
Node tempNode = n.right;
Node temp = n.right;
n.right = temp.left;
temp.left = n;
updateHeight(n);
updateHeight(temp);
}
private void updateHeight(Node n)
{
if(n.left == null && n.right == null)
n.height = 0;
else if(getHeight(n.left) >= getHeight(n.right))
n.height = getHeight(n.left) + 1;
else
n.height = getHeight(n.right) + 1;
}
private Node findMin(Node n)
{
if(n.left != null)
n = findMin(n.left);
return n;
}
private Node findMax(Node n)
{
if(n.right != null)
n = findMin(n.right);
return n;
}
public void clear()
{
root = null;
size = 0;
}
public boolean isEmpty()
{
if(root == null)
return true;
return false;
}
public Iterator iterator()
{
iterator = true;
return new NodeIterator();
}
public int size()
{
return size;
}
public Object[] toArray()
{
NodeIterator i = new NodeIterator();
Object[] elements = new Object[i.size()];
int index = 0;
while(i.hasNext())
elements[index++] = i.next();
return elements;
}
private int getHeight(Node n)
{
if(n == null)
return -1;
return n.height;
}
private class Node implements BinaryTreeNode
{
private Node left = null;
private Node right = null;
private Node parent = null;
private int height = 0;
private Object element;
public Node(Object e)
{
element = e;
}
public Object getData()
{
return this.element;
}
public int getHeight()
{
return this.height;
}
public BinaryTreeNode getLeftChild()
{
return this.left;
}
public BinaryTreeNode getRightChild()
{
return this.right;
}
}
private class NodeIterator implements Iterator<Node>
{
private int numElements = 0;
private int currentIndex = 0;
private List<Node> elements = new LinkedList<Node>();
public NodeIterator()
{
numElements = preorder(root);
}
public boolean hasNext()
{
if(numElements > currentIndex)
return true;
iterator = false;
return false;
}
public Node next()
{
if(hasNext())
return elements.get(currentIndex++);
throw new NoSuchElementException();
}
private int preorder(Node n)
{
numElements++;
elements.add(n);
if(n.left != null)
preorder(n.left);
if(n.right != null)
preorder(n.right);
return numElements;
}
public int size()
{
return numElements;
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
public BinaryTreeNode getRootNode()
{
return (BinaryTreeNode)root;
}