SRL Archive - General

http://pastebin.com/UZ4e1LaH


That is the code.

This is the out put

"C:\Program Files\Java\jdk1.7.0_11\bin\java" -Didea.launcher.port=7534 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 12.0.2\bin" -Dfile.encoding=UTF-8 -classpath "C:\Users\JPHamlett\Desktop\workspace\CompSci\bin;C:\Program Files\Java\jdk1.7.0_11\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\jce.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\jfxrt.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\resources.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\rt.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.7.0_11\jre\lib\ext\zipfs.jar;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 12.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain BTN.BST
Building binary search tree with known values
        --
    2
            --
        5
                9
            15
                --
17
        25
    34
        55
Removed value 2
Deleting 2
Found it
Right node is there, left isnt
        --
    2
            --
        5
                9
            15
                --
17
        25
    34
        55

Process finished with exit code 0

As you can see 2 was not removed, I cannot figure out why :(

I think you might want to try to reduce the multiple conditional if thens to if elses in the removal method. (also consider the 3 possibilities when deleting from binary nodes)

~Lj

From: JPHamlett

As you can see 2 was not removed, I cannot figure out why :(

How unfortunate that Java references caught you off guard (if I'm correct). This looks similar to the Wikipedia code posted in C++ except this is Java?

Unfortunately for you, it seems you're operating on temporary nodes and changes on those have no effect on the original..

Post your node class so we can see what "Data" really is. Your node class might need a remove method or something.

        if (current.getLeft() != null && current.getRight() == null){
            System.out.println("Left node is there, right isnt");
           tempNode = root;
           root = root.getRight();  //Does nothing to the original. Only the temporary.
        }

Above code does nothing because root is a temporary node referring to the parameter that is passed to the function.. these lines are redundant because as soon as the function scope is finished, the nodes created within or passed as parameters die. All changes done to them do not affect the original unless through accessor/mutator functions.

Java does not "Pass by reference". It "passes by value reference". Meaning a copy of the reference is passed such that anything done to that copy does not affect the original (other than using the set/mutators of the passed object). In other words, you can set that copy to null and the original will still be alive but messing with that copy through a set/mutator WILL affect the original.


At least that is all I can tell by just looking at the code. In other words, I'm not 100% sure if I'm 100% right ;)

From: Brandon
How unfortunate that Java references caught you off guard (if I'm correct). This looks similar to the Wikipedia code posted in C++ except this is Java?

Java does not "Pass by reference". It "passes by value reference". Meaning a copy of the reference is passed such that anything done to that copy does not affect the original (other than using the set/mutators of the passed object). In other words, you can set that copy to null and the original will still be alive but messing with that copy through a set/mutator WILL affect the original.


At least that is all I can tell by just looking at the code. In other words, I'm not 100% sure if I'm 100% right ;)

http://pastebin.com/QTNfxfnb // BTNode class

So, instead of

tempNode = null;

Do

TempNode.setData(null);

Also this where I got the pseudo-code
http://www.cecs.csulb.edu/~ebert/teaching/spring2002/cecs328/lectures/bst.pdf

From: JPHamlett
http://pastebin.com/QTNfxfnb // BTNode class

So, instead of

tempNode = null;

Do

TempNode.setData(null);

Also this where I got the pseudo-code
http://www.cecs.csulb.edu/~ebert/teaching/spring2002/cecs328/lectures/bst.pdf

Uhh something of the sort.. Assuming your setLeft and setRight are fine, the following should work. I can't check all the code right now since I'm a bit busy.

  private boolean found = false;

  private BSTNode<T> Remove(BSTNode<T> tree, T element)
  {
    if (tree == null)
      found = false;
    else if (element.compareTo(tree.getData()) < 0)
      tree.setLeft(Remove(element, tree.getLeft()));
    else if (element.compareTo(tree.getData()) > 0)
      tree.setRight(Remove(element, tree.getRight()));
    else  
    {
      tree = removeNode(tree);
      found = true;
	 }
    return tree;
  }

  public boolean remove (T element)
  {
    root = Remove(element, root);
    return found;
  }

From: Brandon
Uhh something of the sort.. Assuming your setLeft and setRight are fine, the following should work. I can't check all the code right now since I'm a bit busy.

  private boolean found = false;

  private BSTNode<T> Remove(BSTNode<T> tree, T element)
  {
    if (tree == null)
      found = false;
    else if (element.compareTo(tree.getData()) < 0)
      tree.setLeft(Remove(element, tree.getLeft()));
    else if (element.compareTo(tree.getData()) > 0)
      tree.setRight(Remove(element, tree.getRight()));
    else  
    {
      tree = removeNode(tree);
      found = true;
	 }
    return tree;
  }

  public boolean remove (T element)
  {
    root = Remove(element, root);
    return found;
  }

And romoveNode sets the value to null via a mutator method?

From: JPHamlett
And romoveNode sets the value to null via a mutator method?

Oops.. Sorry forgot to post the rest:

private T getPredecessor(BSTNode<T> tree)
{
    while (tree.getRight() != null)
      tree = tree.getRight();
    return tree.getData();
}
 
private BSTNode<T> removeNode(BSTNode<T> tree)
{
    T data;
    if (tree.getLeft() == null)
      return tree.getRight();
    else if (tree.getRight() == null) 
      return tree.getLeft();
    else
    {
      data = getPredecessor(tree.getLeft());
      tree.setData(data);
      tree.setLeft(Remove(tree.getLeft(), data));  
      return tree;
    }
}