- #1
- 2,076
- 140
So I'm trying to construct an AVLTree and something crazy seems to be happening in my code.
AVL Tree Class. This includes only the insert and delete methods, soon to be a find method as well :
Now as for the real problem, here's my AVLTreeNode Class. I'm focusing mainly on the insertion portion right now :
Crazy things seem to happen when i try to create a tree by inserting 5, 3 and then 1. The 3 and 1 nodes disapear into nowhere and only the 5 node is left surviving ( which is absolutely incorrect ).
What should happen is that since 5 is my root, 3 is a left child and 1 is a left left child; I should see a re-arrangement of my tree to 3 1 5 where 3 is now the root, 1 is the left child and 5 is the right child.
For some reason this does not seem to be happening? If anyone can spot the kink please let me know as I've been at this for 3 days now and it's getting quite tiresome.
EDIT : Here's a picture of my gui and what's going on.
Picture of inserting 5 and then 3 : http://gyazo.com/6cf46d74404d5e49650a096b721f8b2a
Picture of inserting 1 right after : http://gyazo.com/2b04ee63e66991fbc93cc201fa981159
AVL Tree Class. This includes only the insert and delete methods, soon to be a find method as well :
Code:
package comp2402TreeEditor;
public class AVLTree extends BSTree {
public AVLTree() {}
public void insert(String dataString){
Data data = new Data(dataString);
AVLTreeNode newChildNode = new AVLTreeNode(data);
if(isEmpty()) {
setRoot(newChildNode);
newChildNode.setLocation(getOwner().getDefaultRootLocation());
}
else
getRoot().insertNode(newChildNode);
}
public void remove(String aKeyString){
if(isEmpty()) return;
if(size()==1){
Data temp = new Data(aKeyString);
if(root().getData().compare(temp) == 0)
setRoot(null);
return;
}
getRoot().remove(aKeyString);
}
}
Now as for the real problem, here's my AVLTreeNode Class. I'm focusing mainly on the insertion portion right now :
Code:
package comp2402TreeEditor;
import java.awt.Point;
public class AVLTreeNode extends BSTreeNode{
int balance;
public AVLTreeNode() {}
public AVLTreeNode(Point aPoint) {
super(aPoint);
balance = 0;
}
public AVLTreeNode(Data data) {
super(data);
balance = 0;
}
public void insertNode(TreeNode aNode) {
if(!(aNode instanceof AVLTreeNode)) return;
System.out.println(this);
System.out.println(aNode);
System.out.println(leftChild);
System.out.println(rightChild);
if(aNode.getData().compare(getData()) < 0) {
if(leftChild == null) {
leftChild = (AVLTreeNode) aNode;
aNode.setParent(this);
recursiveBalance(this);
aNode.setLocation(this.getLocation()); //starting location for animation
}
else{
leftChild.insertNode(aNode);
}
}
else{
if(rightChild == null) {
rightChild = (AVLTreeNode) aNode;
aNode.setParent(this);
recursiveBalance(this);
aNode.setLocation(this.getLocation()); //starting location for animation
}
else {
rightChild.insertNode(aNode);
}
}
}
public void remove(String aDataString){
Data temp = new Data(aDataString);
int comparision = temp.compare(this.getData());
if(comparision < 0 && leftChild != null) {
leftChild.remove(aDataString);
}
else if(comparision > 0 && rightChild != null) {
rightChild.remove(aDataString);
}
else if(comparision == 0){
//found a node to remove so remove this node
if(isLeaf())
getParent().removeChildNode(this);
else if(isRoot() && rightChild == null) {
//hijack the leftChild as the new root of the tree
setData(leftChild.getData());
leftChild.setParent(null);
rightChild = (AVLTreeNode) leftChild.rightChild();
if(rightChild != null)
rightChild.setParent(this);
leftChild = (AVLTreeNode) leftChild.leftChild();
if(leftChild != null)
leftChild.setParent(this);
}
else if(isRoot() && leftChild == null) {
//hijack the right as the new root of the tree
setData(rightChild.getData());
rightChild.setParent(null);
leftChild = (AVLTreeNode) rightChild.leftChild();
if(leftChild != null)
leftChild.setParent(this);
rightChild = (AVLTreeNode) rightChild.rightChild();
if(rightChild != null)
rightChild.setParent(this);
}
else if(leftChild == null && rightChild != null) {
//promote rightchild as new child of parent
((AVLTreeNode) getParent()).replaceChildNode(this, rightChild);
}
else if(rightChild == null && leftChild != null) {
//promote left child as new child of parent
((AVLTreeNode) getParent()).replaceChildNode(this, leftChild);
}
else{
//we need to remove an internal node with two current children
//find the smallest next node via the right subtree and use it as a
//replacement for this node
TreeNode smallest = ((AVLTreeNode) rightChild).findSmallestNode();
this.setData(smallest.getData()); //steel the data object of the smallest node
smallest.remove(smallest.key());
//System.out.println("BSTreeNode::remove: smallest to remove= " + smallest.key());
}
}
}
public void recursiveBalance(AVLTreeNode current) {
setBalance(current);
int tBalance = current.balance;
System.out.println(current + " " + this);
System.out.println(tBalance);
if(tBalance == -2) {
if(height((AVLTreeNode)current.leftChild.leftChild) >= height((AVLTreeNode)current.leftChild.rightChild))
current = rotateRight(current);
else
current = doubleRotateLeftRight(current);
}
if(tBalance == 2) {
if(height((AVLTreeNode)current.rightChild.rightChild) >= height((AVLTreeNode)current.rightChild.leftChild))
current = rotateLeft(current);
else
current = doubleRotateRightLeft(current);
}
if(current.getParent() != null) {
recursiveBalance((AVLTreeNode)current.getParent());
}
else {
//Need to somehow set the root to be current RIGHT HERE!
System.out.println("Balancing Complete!");
}
}
public AVLTreeNode rotateLeft(AVLTreeNode n) {
AVLTreeNode v = (AVLTreeNode)n.rightChild;
v.setParent(n.getParent());
n.rightChild = v.leftChild;
if(n.rightChild != null)
n.rightChild.setParent(n);
v.leftChild = n;
n.setParent(v);
if(v.getParent() != null) {
if(((AVLTreeNode)v.getParent()).rightChild == n)
((AVLTreeNode)v.getParent()).rightChild = v;
else if( ((AVLTreeNode)v.getParent()).leftChild == n)
((AVLTreeNode)v.getParent()).leftChild = v;
}
setBalance(n);
setBalance(v);
return v;
}
public AVLTreeNode rotateRight(AVLTreeNode n) {
AVLTreeNode v = (AVLTreeNode)n.leftChild; //(3)
v.setParent(n.getParent()); //(null)
n.leftChild = v.rightChild; //(null)
if(n.leftChild!=null)
n.leftChild.setParent(n);
v.rightChild = n;
n.setParent(v);
if(v.getParent() != null) {
if(((AVLTreeNode)v.getParent()).rightChild == n)
((AVLTreeNode)v.getParent()).rightChild = v;
else if( ((AVLTreeNode)v.getParent()).leftChild == n)
((AVLTreeNode)v.getParent()).leftChild = v;
}
setBalance(n);
setBalance(v);
return v;
}
public AVLTreeNode doubleRotateLeftRight(AVLTreeNode u) {
u.leftChild = rotateLeft((AVLTreeNode)u.leftChild);
return rotateRight(u);
}
public AVLTreeNode doubleRotateRightLeft(AVLTreeNode u) {
u.rightChild = rotateRight((AVLTreeNode)u.rightChild);
return rotateLeft(u);
}
public AVLTreeNode successor(AVLTreeNode q) {
if(q.rightChild != null) {
AVLTreeNode r = (AVLTreeNode)q.rightChild;
while(r.leftChild != null)
r = (AVLTreeNode)r.leftChild;
return r;
}
else {
AVLTreeNode p = (AVLTreeNode)q.getParent();
while(p != null && q == p.rightChild) {
q = p;
p = (AVLTreeNode)q.getParent();
}
return p;
}
}
private int height(AVLTreeNode current) {
if(current == null)
return -1;
if(current.leftChild == null && current.rightChild == null)
return 0;
else if(current.leftChild == null)
return 1+height((AVLTreeNode)current.rightChild);
else if(current.rightChild == null)
return 1+height((AVLTreeNode)current.leftChild);
else
return 1+maximum(height((AVLTreeNode)current.leftChild),height((AVLTreeNode)current.rightChild));
}
private int maximum(int a, int b) {
return (a>=b) ? a : b;
}
private void setBalance(AVLTreeNode current) {
current.balance = height((AVLTreeNode)current.rightChild) - height((AVLTreeNode)current.leftChild);
}
private void replaceChildNode(TreeNode currentChild, TreeNode newChild){
//replace the currentChild of this node with the newChild node
if(leftChild == currentChild){
removeChildNode(currentChild);
leftChild = (AVLTreeNode) newChild;
newChild.setParent(this);
}
else if(rightChild == currentChild){
removeChildNode(currentChild);
rightChild = (AVLTreeNode) newChild;
newChild.setParent(this);
}
}
private TreeNode findSmallestNode(){
//find the smallest node searching from this node along the left subtrees
//in a binary search tree the node with the smallest key will be found by
//going left as far as possible.
if(leftChild == null) return this;
else return ((AVLTreeNode) leftChild).findSmallestNode();
}
}
Crazy things seem to happen when i try to create a tree by inserting 5, 3 and then 1. The 3 and 1 nodes disapear into nowhere and only the 5 node is left surviving ( which is absolutely incorrect ).
What should happen is that since 5 is my root, 3 is a left child and 1 is a left left child; I should see a re-arrangement of my tree to 3 1 5 where 3 is now the root, 1 is the left child and 5 is the right child.
For some reason this does not seem to be happening? If anyone can spot the kink please let me know as I've been at this for 3 days now and it's getting quite tiresome.
EDIT : Here's a picture of my gui and what's going on.
Picture of inserting 5 and then 3 : http://gyazo.com/6cf46d74404d5e49650a096b721f8b2a
Picture of inserting 1 right after : http://gyazo.com/2b04ee63e66991fbc93cc201fa981159