Search Tree , modifications are not saving

Question

I am currently trying to implement a dictionary using a search tree. (The exercise tells me to use such a structure). My tree is made out of nodes that save 2 strings: abreviere(the abreviation of a phrase) and acronim(the phrase). Here is my implementation so far:

Node Class:

public class Nod {
    String acronim;
    String abreviere;
    Nod st,dr;

    Nod(String acronim,String abreviere){
        this.acronim = acronim;
        this.abreviere = abreviere;
        st = null;
        dr = null;
    }
}

Tree Class:

Constructor and insert:

public class Arbore {

    Nod root;
    Arbore(Nod x){
        root = x;
    }

    public void insert(Nod x,Nod curr){
        if(curr.acronim.compareTo(x.acronim) < 0){
           if(curr.st == null){
               curr.st = new Nod(x.acronim,x.abreviere);
           }
           else insert(x,curr.st);
        }
        else if(curr.dr == null){
                curr.dr = new Nod(x.acronim, x.abreviere);
            }
            else insert(x,curr.dr);
    }
}

I made them to work. I don't understand why I can't have this code instead:

public class Arbore {

Nod root;
Arbore(){

}

public void insert(Nod x,Nod curr){
    if(curr == null) {curr = x; return;}
    if(curr.acronim.compareTo(x.acronim) < 0){
       if(curr.st == null){
           curr.st = new Nod(x.acronim,x.abreviere);
       }
       else insert(x,curr.st);
    }
    else if(curr.dr == null){
            curr.dr = new Nod(x.acronim, x.abreviere);
        }
        else insert(x,curr.dr);
}

This wouldn't save my structure either (I am clearly missing something and seems to be related). The problem I am facing now is deleting a node. I have to search for an abreviation(abreviere) and if I find it I must print the phrase and delete the node. These are the methods that I use to do this:

public void search(String acronim){
        if(root.acronim.compareTo(acronim) == 0) delete(root);

        if(root.acronim.compareTo(acronim) < 0) search(acronim,root.st);
        if(root.acronim.compareTo(acronim) > 0) search(acronim,root.dr);
    }

    private void search(String acronim,Nod curr){
        if(curr == null){System.out.println("Nu exista"); return;}
        if(curr.acronim.compareTo(acronim) == 0) this.delete(curr);

        if(curr.acronim.compareTo(acronim) < 0) this.search(acronim,curr.st);
        if(curr.acronim.compareTo(acronim) > 0) this.search(acronim,curr.dr);
    }

    private void delete(Nod x){
        if(x.st == null && x.dr == null){ x = null; System.out.println("deleting");}
        else if(x.st == null && x.dr != null) {x = x.dr;System.out.println("deleting right");}
        else if(x.st != null && x.dr == null) {x = x.st;System.out.println("deleting left");}
        else{
            System.out.println("Il deletez");
            Nod aux = new Nod(x.acronim,x.abreviere);
            x.abreviere = x.st.abreviere;
            x.acronim = x.st.acronim;

            x.st.abreviere = aux.abreviere;
            x.st.acronim = aux.acronim;

            delete(x.st);    
        }

    }

They seem to do the job(from the printed messages) . However the changes don't save, after I apply the method I am left with the same tree. Here is the printing method that shows me the current tree:

public String inordine(Nod root){
    if(root == null) return "";
    return inordine(root.st) + afis(root) + inordine(root.dr);
}

private String afis(Nod n){
    if(n == null) return "E nula?!";
    return n.abreviere + "->" + n.acronim + "\n";
}

public void afisare(){
    System.out.println(inordine(this.root));
}

What am I doing wrong? Is it the garbage collector or something? I use my class like this:

public static void main(String[] args) throws FileNotFoundException, IOException {
        FileReader fr = new FileReader("Acronime.txt");
        BufferedReader bf = new BufferedReader(fr);

        String line = bf.readLine();
        String[] array = line.split("=>");
        Nod x = new Nod(array[0],array[1]);
        Arbore a = new Arbore(x);

        while((line = bf.readLine()) != null){
            String[] array2 = line.split("=>");
            Nod y = new Nod(array2[0],array2[1]);
            a.insert(y,a.root);
        }

        a.afisare();

        a.search("JSE");
        a.afisare();
    }

The words come like this but this part works .

JSE=>JavaScript Encoding
ESP=>Enhanced Serial Port
MSB=>Most Significant Byte
CDRAM=>Cached Dynamic RAM
EMI=>Electro-Magnetic Interference
CDRAM=>Cached Dynamic RAM
AIFF=>Audio Interface File
BASM=>Built in AsseMbler

After looking at the suggested post I changed 2 rows in the delete method and added 1 more method:

Changed Rows:

else if(x.st == null && x.dr != null) {copy(x,x.dr); x.dr = null; System.out.println("deleting right");}
        else if(x.st != null && x.dr == null) {copy(x,x.st); x.st = null; System.out.println("deleting left");}

This way the changes stick(if you want to know why read the question from the suggested post below).

In the end the question is : "How to delete an instance of a class because you can't do it with x = null;? "

Java uses [_pass-by-value_](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value), so this `public void insert(Nod x,Nod curr){ if(curr == null) {curr = x; return;} ... }` does not work. — Seelenvirtuose, Jul 12 '15 at 13:43
it is there. It is named "delete" and it is called inside "search". I see Seelenvirtuose. Should I say something like curr = new Node(x.lala,x..lala) to fix that ? Would this stick ? — Lucian Tarna, Jul 12 '15 at 13:47
Ah mr Seelenvirtuose I see. I can't do "x = x.dr" . I have to just copy the fields — Lucian Tarna, Jul 12 '15 at 13:58
@Seelenvirtuose I do need to destroy "Nod" somehow.. how do I do that if not with null? — Lucian Tarna, Jul 12 '15 at 14:01

score 0 · Answer 1 · answered Jul 12 '15 at 13:43

0

About the constructor:

In the method you would like to use (with the empty constructor) you need to set the class member root at some point. Something like this should do it:

public void insert(Nod x,Nod curr){
  if(curr == null) {
    this.root = x; 
    return;
  }
  ...

About deletion

I don't understand the case when st and dr is not null. You seem to keep the tree structure intact but switch the payload data (abreviere, acronim) of the st side and then delte the st node. I don't get it yet. I will update my answer when I understand better.

answered Jul 12 '15 at 13:43

luksch

11,497
6
38
53

About the constructor: I do have that condition in the code that DOESN'T work (if(curr == null) {curr = x; return;}) , I don't need it in the code that DOES work because curr will never be null. About deletion: https://en.wikipedia.org/wiki/Binary_search_tree#Deletion – Lucian Tarna Jul 12 '15 at 13:50
okay. I get it now. Please note the ```this.root = x``` assignment of the root node that you do not have in your version. – luksch Jul 12 '15 at 14:02
O no . There were 2 versions. this.root = x from the constructor is the version I am using because the 2nd one doesn't work because of what @Seelenvirtuose said in the comments. Don't bother yourself with that . I posted it because it was the same bugg as the deletion part. In the end the question is how do I delete an instance of a class if not with name = null – Lucian Tarna Jul 12 '15 at 14:05

score 0 · Accepted Answer · edited May 23 '17 at 12:06

You can't destroy an instance of a class in java like I was trying to do in the delete method if(x.st == null && x.dr == null){ x = null;} . To delete the node from the tree you have to find the parent of x and then parent.x = null. This way the reference to x is lost and the garbage collector does his job.
This is because , like @Seelenvirtuose said, java uses pass-by-value which you can read more about in the link that he provided: click!

Search Tree , modifications are not saving

2 Answers2