sbowde4 sbowde4 - 13 days ago 4
Java Question

AVLTree Node Removal

So for class I was tasked with creating an AVLTree that can add/remove nodes and print all the nodes out in a special way. I accomplished this. Eveyrthing works fine on my local computer. However, when I upload the code to the online submission server and test it with a command line input; one of my functions stops working and I was hoping someone could explain why.

Here is my main method on my computer:

AVLTree avl = new AVLTree();
avl.insert(5, "earl");
avl.insert(3, "colin");
avl.insert(6, "fiona");
avl.show();
avl.insert(2, "bonnie");
avl.insert(4, "danielle");
avl.show();
avl.insert(1, "alex");
avl.show();
avl.delete("bonnie");
avl.delete("alex");
avl.show();


Here is the second main method that I am using for command line input

public static void main(String[] args) throws FileNotFoundException{
Scanner input = new Scanner(new File(args[0]));
String name = new String();
int key = 0;
AVLTree avl = new AVLTree();
while (input.hasNext()) {
String opt = input.next().toUpperCase();
switch(opt)
{
case "INSERT":
name = input.next();
key = input.nextInt();
avl.insert(key, name);
break;
case "REMOVE":
name = input.next();
System.out.println("***" + avl.search(name));//this is where the problem is. On the server it returns null, on my computer it returns the correct node
avl.delete(name);
break;
case "SHOW":
avl.show();
break;
}

}
}


}


The main is different on the two, because I am not using the command line on my computer, so I copied the input file on the computer version and manually input everything.

Here is the input file

insert Earl 5
insert Colin 3
insert Fiona 6
show
insert Bonnie 2
insert Danielle 4
show
insert Alex 1
show
remove Bonnie
remove Alex
show


Finally here are the functions necessary for removing a node.

public boolean delete(String name) {
Node target = search(name);
if (target == null) return false;
target = deleteNode(target);
balanceTree(target.parent);
return true;
}

private Node deleteNode(Node target) {
if (isLeaf(target)) { //leaf
if (isLeftChild(target)) {
target.parent.left = null;
} else {
target.parent.right = null;
}
} else if (target.left == null ^ target.right == null) { //exact 1 child
Node nonNullChild = target.left == null ? target.right : target.left;
if (isLeftChild(target)) {
target.parent.setLeftChild(nonNullChild);
} else {
target.parent.setRightChild(nonNullChild);
}
} else {//2 children
Node immediatePredInOrder = immediatePredInOrder(target);
target.value = immediatePredInOrder.value;
target = deleteNode(immediatePredInOrder);
}

reHeight(target.parent);
return target;
}
public Node search(String name) {
return binarySearch(root, name);
}
private Node binarySearch(Node node, String name) {
if (node == null)
return null;
if (name == node.name)
return node;
else {
Node foundNode = binarySearch(node.left, name);
if(foundNode == null) {
foundNode = binarySearch( node.right, name);
}
return foundNode;

}

}


The problem is that the search function can not find the node on the server version and I can not figure out why.

Also, here is the output

Local Version
earl 5
colin 3
fiona 6
earl 5
colin 3
bonnie 2
danielle 4
fiona 6
colin 3
bonnie 2
alex 1
earl 5
danielle 4
fiona 6
***bonnie 2//the println statement for search

earl 5
colin 3

Server Version

Earl 5
Colin 3
Fiona 6
Earl 5
Colin 3
Bonnie 2
Danielle 4
Fiona 6
Colin 3
Bonnie 2
Alex 1
Earl 5
Danielle 4
Fiona 6
***null//search println
***null//search println
Colin 3
Bonnie 2
Alex 1
Earl 5
Danielle 4
Fiona 6

danielle 4
fiona 6

Answer

My professor and I were able to speak on these and we found the issue was because of differences in the version of java.

We simply changed

if (name == node.name)

to

if (name.compareTo(node.name) == 0)

in the binarySearch() method

Comments