Tree node deletion problem

[sirlink99]

I am having a problem deleting nodes from my Binary search tree. What I have so far does part of what it is supposed to do. I read in an input (paragraph of text) to create the tree (organized via ASCII character values). I make it, then print out all the elements. Then I need to delete the ones that begin with a vowel. MY algorithm deletes most of the ones that start with a vowel, but I believe that as it replaces values with other ones some of the words slip through. Here is my class. it is quite a bit of code, but the deletion part is from lines 43-81

package assign2;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.regex.Pattern;



public class Main {



    public static void main(String[] args) {
        Node binRoot = null, avlRoot = null;
        try {
            Scanner s = new Scanner (new File("Files/input.txt"));
            s.useDelimiter("\\W");
            while (s.hasNext()){
                String st = s.next();

                binRoot = addbin(binRoot, st);
                avlRoot = insertavl(st, avlRoot);
            }

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        System.out.print("BST: ");
        printInOrder(binRoot);
        System.out.println("\n");
        System.out.print("AVL: ");
        printInOrder(avlRoot);
        System.out.println("\n");
        System.out.print("DBST ");
        binRoot = delete(binRoot);
        printInOrder(binRoot);
        //System.out.println(avlRoot.getPayload());
        //printTree(root);
    }


    public static Node delete(Node n){
        if (n == null)
            return n;

        if (("" + n.getPayload().charAt(0)).matches("[aeiouAEIOU]")){
            if (n.goLeft() != null && n.goRight() != null){
                n.takeOver(successor(n));
                n.setRight(delete(n.goRight()));
            }
            else
                if(n.goLeft() != null)
                    n = n.goLeft();
                else 
                    n = n.goRight();
        }
            try{
                n.setLeft(delete(n.goLeft()));
            }catch(NullPointerException e){}
            try{
                n.setRight(delete(n.goRight()));
            }catch(NullPointerException e){}

        return n;
    }


    private static Node successor(Node n) {
        if (n.goRight() != null){
            n = n.goRight();
            while (n.goLeft() != null){
                n = n.goLeft();
            }
            return n;
        }
        if (n.goLeft() != null)
            return n.goLeft();

        return null;
    }


    // Creates the avl tree
    public static Node insertavl(String cont, Node n){
        if (cont.length() != 0){
            if (n == null){
                n = new Node(null, cont, null);
            }
            else if (n.getPayload().compareTo(cont) > 0){
                n.setLeft(insertavl(cont, n.goLeft()));
                if (height(n.goLeft()) - height(n.goRight()) == 2){
                    if (n.getPayload().compareTo(cont) > 0){
                        // outside insert
                        n = sRotateToRight(n);
                    }
                    else{
                        // inside insert
                        n = dRotateToRight(n);
                    }
                }else{
                    n.height = 1 + Math.max(height(n.goLeft()), height(n.goRight()));
                }
            }
            else if (n.getPayload().compareTo(cont) < 0){
                // right subtree
                n.setRight(insertavl(cont, n.goRight()));
                if (height(n.goLeft()) - height(n.goRight()) == 2){
                    if (n.getPayload().compareTo(cont) > 0){
                        // outside insert
                        n = sRotateToLeft(n);
                    }
                    else{
                        // inside insert
                        n = dRotateToLeft(n);
                    }
                }else{
                    n.height = 1 + Math.max(height(n.goLeft()), height(n.goRight()));
                }

            }
            else
                n.incrementCounter();
            return n;
        }
        return n;
    }



    private static Node dRotateToRight(Node n) {

        n.setLeft(sRotateToLeft(n));
        n = sRotateToRight(n);
        return n;
    }

    private static Node dRotateToLeft(Node n){
        n.setRight(sRotateToRight(n));
        n = sRotateToLeft(n);
        return n;
    }

    private static Node sRotateToRight(Node n) {

        Node k1;
        k1 = n.goLeft();
        n.setLeft(k1.goRight());
        k1.setRight(n);
        n.height = 1 + Math.max(height(n.goLeft()), height(n.goRight()));
        k1.height = 1 + Math.max(height(k1.goLeft()), k1.height);
        n = k1;
        return n;
    }
    private static Node sRotateToLeft(Node n){
        Node k1;
        k1 = n.goRight();
        n.setRight(k1.goLeft());
        k1.setLeft(n);
        n.height = 1 + Math.max(height(n.goLeft()), height(n.goRight()));
        k1.height = 1 + Math.max(height(k1.goLeft()), k1.height);
        return n;
    }

    private static int height(Node h) {

        if (h == null)
            return -1;
        return h.height;
    }

    /*
     * BST
     */
    private static Node addbin(Node binRoot, String st) {

        if (binRoot == null)
            binRoot = new Node(null, removePunc(st), null);
        else {
            String stt = removePunc(st);
            if (stt.length() != 0)
                insertBST(binRoot, stt);
        }
        return binRoot;
    }

    private static void insertBST(Node n, String w) {
        if (w.compareTo(n.getPayload()) < 0){
            if (n.goLeft() == null){
                n.setLeft(new Node(null, w, null));
                return;
            }
            insertBST(n.goLeft(), w);
        }
        else if (w.compareTo(n.getPayload()) > 0){
            if (n.goRight() == null){
                n.setRight(new Node(null, w, null));
                return;
            }
            insertBST(n.goRight(), w);
        }
        else
            n.incrementCounter();
    }

    // remove special characters
    private static String removePunc(String next) {
        next = next.replaceAll(("\\W"), "");
        return next;
    }
    /*
     * Print trees in different ways
     * 
     */

    private static void printTree(Node tree) {
        String s = "Current: " + tree.getPayload();
        try{
            if (tree.goLeft() != null)
                s += "\tChildren: " + tree.goLeft().getPayload();
            else
                s += "\tChildren: null";
            if (tree.goRight() != null)
                s += ", " + tree.goRight().getPayload();
            else
                s += ", null";
            System.out.println(s);
            printTree(tree.goLeft());
            printTree(tree.goRight());
        }catch(NullPointerException e){}
    }

    private static void printInOrder(Node tree){
        try{
            if (tree.goLeft() != null)
                printInOrder(tree.goLeft());
            System.out.print (tree.getPayload() + " (" + tree.getCount() + "), ");
            if (tree.goRight() != null)
                printInOrder(tree.goRight());
        }catch(NullPointerException e){}
    }

}

Here is the node class

package assign2;

public class Node {

    private int counter = 0;
    private String s;
    private Node l, r;
    public int height = 1;

    public Node (Node left, String word, Node right){
        counter = 1;
        s = word;
        l = left;
        r = right;

        System.out.println("New Node: " + word);
    }

    public int getCount(){
        return counter;
    }

    public String getPayload(){
        return s;
    }

    public Node goLeft(){
        return l;
    }

    public Node goRight(){
        return r;
    }

    public void incrementCounter(){
        counter++;
    }
    public void setLeft(Node left){
        l = left;
    }

    public void setRight(Node right){
        r = right;
    }

    public void takeOver (Node n){
        s = n.getPayload();
        counter = n.counter;
    }

}

and Here is the input text that I am using

Objective
You are going to compare the relative efficiency of storing a BST in AVL format over a standard BST configuration. You will effectively write 2 programs in parallel so the 2 systems can be compared.
The Assignment
Implement a BST which has a String element and thus represents the Key as well; add an integer variable C which will represent the number of occurrences of the element. Your BST should support the following operations. Insert, Delete, Find, InOrder and IntPathLength. Each of the preceding operations should be implemented recursively where appropriate. The function IntPathLength should recursively calculate the internal path length of the tree. In the event of like elements you are to increment the count C field.
Repeat the above implementation for a BST-AVL tree. Each operation where appropriate is recursive, the Find, InOrder and IntPathLength operations you implemented for the standard BST should work for the BST-AVL tree. The deletion process for both trees should be removal of the node from the tree. When printing during the traversal: when a word only appears once then just print the word followed by a space, if there are multiple occurrences, succeed the output with the count in brackets, e.g. Implement (??). Consider using multiple words per line to conserve paper.

Here is the output my code produces

<not important stuff. Prints when a new node was created>

BST: 2 (2), AVL (3), Assignment (1), BST (7), C (2), Consider (1), Delete (1), Each (2), Find (2), Implement (2), In (1), InOrder (2), Insert (1), IntPathLength (3), Key (1), Objective (1), Repeat (1), String (1), The (3), When (1), You (2), Your (1), a (7), above (1), add (1), an (1), and (3), appears (1), appropriate (2), are (3), as (1), be (3), both (1), brackets (1), by (1), calculate (1), can (1), compare (1), compared (1), configuration (1), conserve (1), count (2), deletion (1), during (1), e (1), effectively (1), efficiency (1), element (2), elements (1), event (1), field (1), followed (1), following (1), for (4), format (1), from (1), function (1), g (1), going (1), has (1), if (1), implementation (1), implemented (2), in (3), increment (1), integer (1), internal (1), is (1), just (1), length (1), like (1), line (1), multiple (2), node (1), number (1), occurrences (2), of (7), once (1), only (1), operation (1), operations (3), output (1), over (1), paper (1), parallel (1), path (1), per (1), preceding (1), print (1), printing (1), process (1), programs (1), recursive (1), recursively (2), relative (1), removal (1), represent (1), represents (1), should (5), so (1), space (1), standard (2), storing (1), succeed (1), support (1), systems (1), the (21), then (1), there (1), thus (1), to (3), traversal (1), tree (4), trees (1), using (1), variable (1), well (1), when (1), where (2), which (2), will (2), with (1), word (2), words (1), work (1), write (1), you (2), 

AVL: 2 (2), AVL (3), Assignment (1), BST (7), C (2), Consider (1), Delete (1), Each (2), Find (2), Implement (2), In (1), InOrder (2), Insert (1), IntPathLength (3), Key (1), Objective (1), Repeat (1), String (1), The (3), When (1), You (2), Your (1), a (7), above (1), add (1), an (1), and (3), appears (1), appropriate (2), are (3), as (1), be (3), both (1), brackets (1), by (1), calculate (1), can (1), compare (1), compared (1), configuration (1), conserve (1), count (2), deletion (1), during (1), e (1), effectively (1), efficiency (1), element (2), elements (1), event (1), field (1), followed (1), following (1), for (4), format (1), from (1), function (1), g (1), going (1), has (1), if (1), implementation (1), implemented (2), in (3), increment (1), integer (1), internal (1), is (1), just (1), length (1), like (1), line (1), multiple (2), node (1), number (1), occurrences (2), of (7), once (1), only (1), operation (1), operations (3), output (1), over (1), paper (1), parallel (1), path (1), per (1), preceding (1), print (1), printing (1), process (1), programs (1), recursive (1), recursively (2), relative (1), removal (1), represent (1), represents (1), should (5), so (1), space (1), standard (2), storing (1), succeed (1), support (1), systems (1), the (21), then (1), there (1), thus (1), to (3), traversal (1), tree (4), trees (1), using (1), variable (1), well (1), when (1), where (2), which (2), will (2), with (1), word (2), words (1), work (1), write (1), you (2), 

DBST 2 (2), Assignment (1), BST (7), C (2), Consider (1), Delete (1), Find (2), In (1), In (1), Key (1), Repeat (1), Repeat (1), String (1), The (3), When (1), You (2), Your (1), an (1), be (3), be (3), both (1), brackets (1), by (1), calculate (1), can (1), compare (1), compared (1), configuration (1), conserve (1), count (2), deletion (1), during (1), field (1), field (1), field (1), followed (1), following (1), for (4), format (1), from (1), function (1), g (1), going (1), has (1), just (1), just (1), length (1), like (1), line (1), multiple (2), node (1), number (1), paper (1), paper (1), paper (1), parallel (1), path (1), per (1), preceding (1), print (1), printing (1), process (1), programs (1), recursive (1), recursively (2), relative (1), removal (1), represent (1), represents (1), should (5), so (1), space (1), standard (2), storing (1), succeed (1), support (1), systems (1), the (21), then (1), there (1), thus (1), to (3), traversal (1), tree (4), trees (1), variable (1), well (1), when (1), where (2), which (2), will (2), with (1), word (2), words (1), work (1), write (1), you (2), 

Like I stated my code deletes a portion but not all.

As you can see this is an assignment, but I have spent at least 5 hours trying to figure out why it doesn't delete correctly.
Any suggestions would be helpful.

Thank you for your time and help.

[somjit{}]

its a lot of code to go through , lets see..

What if you put the elements in a sorted manner inside the BST ? does that comply with your assignment rules ?

if yes , you can use buffered reader , read a line , .split() it , sort the string array , and then put each entry in the order they come in the string. Its not realted to your question perhaps , but i feel having things sorted makes 'em easy.

[somjit{}]

regarding deletion , here are 4 steps to it

Save a link to the node to be deleted in t. (n in your case)
Set x to point to its successor min(t.right).
Set the right link of x (which is supposed to point to the BST containing all the keys larger than x.key) to deleteMin(t.right), the link to the BST containing all the keys that are larger than x.key after the deletion.
Set the left link of x (which was null) to t.left (all the keys that are less than both the deleted key and its successor).

probably you have implemented this , but your delete code looks a bit complicated.

The implementation for the above description is something like this :

    public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x) {
        if (x.left == null)
            return x.right;
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null)
            return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x.left = delete(x.left, key);
        else if (cmp > 0)
            x.right = delete(x.right, key);
        else {
            if (x.right == null)
                return x.left;
            if (x.left == null)
                return x.right;
            Node t = x;
            x = min(t.right); 
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    private Node min(Node x)
    {
        if (x.left == null) return x;
        return min(x.left);
    }

@^^Source

[sirlink99]

Thanks for the reply. I managed to get my deletion working to some degree where now it deletes all the words begninning with a vowel, however now I have run into the problem where words are duplicating. This is the output that I get from my code after I delete

2 (2), BST (7), C (2), Consider , Delete , Find (2), Key , Repeat , Repeat , String , The (3), When , You (2), Your , be (3), be (3), both , brackets , by , calculate , can , compare , compared , configuration , conserve , count (2), deletion , during , field , field , followed , following , for (4), format , from , function , g , going , has , just , just , length , like , line , multiple (2), node , number , paper , paper , parallel , path , per , preceding , print , printing , process , programs , recursive , recursively (2), relative , removal , represent , represents , should (5), so , space , standard (2), storing , succeed , support , systems , the (21), then , there , thus , to (3), traversal , tree (4), trees , variable , well , when , where (2), which (2), will (2), with , word (2), words , work , write , you (2), 

As you can see some words repeat ("Repeat" and "field"). Here is my new delete code

public static Node delete(Node n, String key){
        if (n == null)
            return n;

        if (("" + n.getPayload().charAt(0)).matches("[aeiouAEIOU]") || key.equals(n.getPayload())){
            System.out.println("In if with: " + n.getPayload());
            if (n.goLeft() != null && n.goRight() != null){
                Node s = successor(n);
                n.takeOver(s);
                delete(s,"");
                n.setRight(delete(n.goRight(), n.getPayload()));
                n = delete(n, ""); // verifies that an element starting with a vowel did not replace the node

            }
            else
                if(n.goLeft() != null)
                    n = n.goLeft();
                else 
                    n = n.goRight();
        }
        try{
            n.setLeft(delete(n.goLeft(), n.getPayload()));
        }catch(NullPointerException e){}
        try{
            n.setRight(delete(n.goRight(),n.getPayload()));
        }catch(NullPointerException e){}

        return n;
    }

What I suspect is that after the take over method (which copies the values of the string and count variables in one node to the other node) the algorithm doesn't delete the node that it took over. Any ideas?

Thank you for your time and help.

[somjit{}]

No problem. But can you explain the role of the two argument delete() as compared to the previous one ?

edit : i see that you implemented the pattern somewhat that i posted ,missed it at first. lets see whats happening...

[sirlink99]

the role of the 2 argument delete was an attempt at fixing the problem by passing in the string which was the string of the node that replaces it, and then using it to delete the node which replaced it from the bottom of the tree. It worked once for the word "Key" and one for "field", but it didn't for repeat or the other copy of field and I have no idea why.

[somjit{}]

One thing that i find a bit hard , is that the use of "key" here. Key is generally accompanied by a corresponding value , but your node does not have a key-value pair , only a key. Perhaps you could make that change . Yes it may not directly solve your problem , but it clears things.

also , what is your new version for this : binRoot = delete(binRoot); ?

[sirlink99]

The new code for delete without the key is

public static Node delete(Node n){
        if (n == null)
            return n;

        if (("" + n.getPayload().charAt(0)).matches("[aeiouAEIOU]")){
            //System.out.println("In if with: " + n.getPayload());
            if (n.goLeft() != null && n.goRight() != null){
                Node s = successor(n);
                n.takeOver(s);
                delete(s);
                n.setRight(delete(n.goRight()));
                n = delete(n); // verifies that an element starting with a vowel did not replace the node

            }
            else
                if(n.goLeft() != null)
                    n = n.goLeft();
                else 
                    n = n.goRight();
        }
        try{
            n.setLeft(delete(n.goLeft()));
        }catch(NullPointerException e){}
        try{
            n.setRight(delete(n.goRight()));
        }catch(NullPointerException e){}

        return n;
    }

Which produces the output of

2 (2), BST (7), C (2), Consider , Delete , Find (2), Key , Key , Repeat , Repeat , String , The (3), When , You (2), Your , be (3), be (3), both , brackets , by , calculate , can , compare , compared , configuration , conserve , count (2), deletion , during , field , field , field , followed , following , for (4), format , from , function , g , going , has , just , just , just , length , like , line , multiple (2), node , number , paper , paper , paper , parallel , path , per , preceding , print , printing , process , programs , recursive , recursively (2), relative , removal , represent , represents , should (5), so , space , standard (2), storing , succeed , support , systems , the (21), then , there , thus , to (3), traversal , tree (4), trees , variable , well , when , where (2), which (2), will (2), with , word (2), words , work , write , you (2), 

As you can tell a couple more copies of words have appeared.

Thanks for the help.

[somjit{}]

Your code is very hard to read . Not only are the names of the methods non-descriptive , but also , there aren't any comments for them. Also , your assignment speaks to implement recursion where-ever possible , but i dont see you doing that. Recursion is bad for a lot of things , but it really makes things simple when it comes to trees. As for example , in your printInOder() method , if you implemented that using recursion , here is what it can be changed to :

    public Iterable<Key> keys(){
        Queue<Key> q = new Queue<Key>(); // queue implements iterable , so contract is valid
        inorder(root, q); // call the recursion
        return q
    }

    private void inorder(Node x, Queue<Key> q) {

        if (x == null)
            return; // will signify the end of recursion , all the stacks starts
                    // returning hereonwards

        inorder(x.left, q);

        q.enqueue(x.key); // as stacks start evaluating , nodes will be put into
                            // the queue starting from the left most leaf , ie , the
                            // smallest node , ending with the root

        inorder(x.right, q); // and now enqueue all the nodes to the right
    }

So all you do is call print on keys() and it takes care of all the traversing and printing. Resulting in cleaner , better , lesser (amount of) inspection needed when something goes wrong. like now.

( comments are what i understand of the code , i can be wrong though. )

Also , reagrding your delete mechanism , i have no idea what that all means. Deleting a node in a BST is tricky , and there is recursion to solve it in a well known algorithm known as "Hibbard's Deletion" . you can find the idea here ( i think i gave the link before , but its a loong way up , so posting again just in case).

And the code for that can be something like this :

public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = delete(x.left,  key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else { 
            if (x.right == null) return x.left;
            if (x.left  == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right); // posted this method above
            x.left = t.left;
        } 
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    } 

Try comparing the two. I'm scared to even look at your delete ( i tried being brave last night a lot , but just too complex)

[sirlink99]

Thanks for the help I couldn't manage to get it working correctly. I will try to create my custom tree class that I can test and use without having all the constraints of the assignment to worry about.