binary search tree impelementation and java

Question

Hello I am trying to implement BST algorithm using Cormen's pseudo code yet having issue.

Here is my Code for Node:

public class Node {
    Node left;
    Node right;
    int value;

    Node(int value){
        this.value = value;
        this.left = null;
        this.right = null;  
    }
}

and for the Bstree:

public class Btree {
    Node root;

    Btree(){
        this.root = null;
    }

    public static void inorderWalk(Node n){
        if(n != null){
            inorderWalk(n.left);
            System.out.print(n.value + " ");
            inorderWalk(n.right);
        }
    }

    public static Node getParent(Btree t, Node n){
        Node current = t.root;
        Node parent = null;


        while(true){
            if (current == null)
                return null;

            if( current.value == n.value ){
                break;
            }

            if (current.value > n.value){
                parent = current;
                current = current.left;
            }
            else{ //(current.value < n.value)
                parent = current;
                current = current.right;
            }       
        }
        return parent;
    }


    public static Node search(Node n,int key){
        if(n == null || key == n.value ){
            return n;
        }
        if(key < n.value){
            return search(n.left,key);
        }
        else{
            return search(n.right,key);

        }
    }

    public static Node treeMinimum(Node x){
        if(x == null){
            return null;
        }


        while(x.left != null){
            x = x.left;
        }
        return x;
    }

    public static Node treeMaximum(Node x){
        if(x == null){
            return null;
        }

        while(x.right != null){
            x = x.right;
        }
        return x;   
    }

    public static Node treeSuccessor(Btree t,Node x){
        if (x.right == null){
            return treeMinimum(x.right);
        }
        Node y = getParent(t,x);
        while(y != null && x == y.right){
            x = y;
            y = getParent(t,y);
        }
        return y;   
    }

    public static Btree insert(Btree t,Node z){
        Node y = null;
        Node x = t.root;

        while(x != null){
            y = x;
            if(z.value < x.value)
                x = x.left;
            else
                x = x.right;
        }
        Node tmp = getParent(t,z);
        tmp = y;
        if(y == null){
            t.root = z;
        }
        else if(z.value < y.value)
            y.left = z;
        else
            y.right = z;

        return t;
    }


    public static Btree delete(Btree t,Node z){
        Node y,x;
        if (z.left == null || z.right == null)
            y = z;
        else
            y = treeSuccessor(t,z);

        if (y.left != null)
            x = y.left;
        else
            x = y.right;
        if (x != null){
            Node tmp = getParent(t,x);
            tmp = getParent(t,y);
        }

        if (getParent(t,y) == null ){
            t.root = x;
        }
        else{
            if( y == getParent(t,y).left ){
                getParent(t,y).left = x;
            }
            else{
                getParent(t,y).right = x;

            }
    }
        if(y != z){
            z.value = y.value;
        }
    return t;
}

public static void main(String[] args){
    Btree test = new Btree(); 
    Node n1 = new Node(6);
    Node n2 = new Node(3);
    Node n3 = new Node(9);
    Node n4 = new Node(1);
    Node n5 = new Node(16);
    Node n6 = new Node(4);
    Node n7 = new Node(2);
    Node n8 = new Node(11);
    Node n9 = new Node(13);


    test = insert(test,n1);
    test = insert(test,n2);
    test = insert(test,n3);
    test = insert(test,n4);
    test = insert(test,n5);
    test = insert(test,n6);
    test = insert(test,n7);
    test = insert(test,n8);
    test = insert(test,n9);
    inorderWalk(test.root);
    System.out.println();
    test = delete(test,n8);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n5);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n2);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n1);
    inorderWalk(test.root);




}

}

The main problem is with the remove part, sometimes it is working as intended, sometimes removing wrongly and sometimes null pointer exception. What can be the issue ?

Ps: this is NOT a homework

Answer 1

...what is up with your delete code? It doesn't make a lot of sense. I would consider rewriting it in a more logical way. Without the meaningless single-letter variable names. And add comments!

One possible algorithm is:

Get the parent of the node to delete
Get the right-most node of the left subtree, or the leftmost node of the right subtree
Remove the node to delete and replace it with the node you found
Rebalance the tree

...or, if you want to hack up this stuff so it's right, I'd start looking at the

if (x != null){
    Node tmp = getParent(t,x);
    tmp = getParent(t,y);
}

part, because that's clearly wrong.

Answer 2

I'll have to side with Anon and go for the rewrite. The null pointers come from your getParent function (which explicitly returns nulls along other things). So I would start there and fix the function(s) so that they return one thing and one thing only at the end of the function.

Answer 3

Some immediate problems with your code: your treeSuccessor starts with

    if (x.right == null){
        return treeMinimum(x.right);
    }

which should be if (x.right != null), of course.

Your insert code has the lines

    Node tmp = getParent(t,z);
    tmp = y;

where you assign to tmp and immediately assign to it again. It doesn't seem to me that you need these lines at all, since you don't use tmp further on. At this moment, you have y being the node to whose child z gets inserted, so just delete these lines.

Again, in delete, you have the lines

    if (x != null){
        Node tmp = getParent(t,x);
        tmp = getParent(t,y);
    }

where you don't actually do anything, since tmp is not visible outside this snippet. And further on, in delete, you repeat the expression getParent(t,y), which can be an expensive operation, so you should compute it only once and assign it to some variable.

But in general, your code, though it seems correct (probably apart from delete, which I did not understand completely but which looks suspicious), does not much resemble typical binary tree code. You don't really need the getParent and treeSuccessor methods to implement search, insert, and delete. The basic structure that you have for search works for the others too, with the following modifications:

• with insert, when you get to a null link, instead of returning null, insert the element to that point
• with delete, when you find the element, if it has only one (or no) child, replace it with that child, and if it has two children, replace it with either the maximum of the left child tree or the minimum of the right child tree

Both of these require in addition that you keep track of the parent node while descending into the tree, but that's the only modification you need to make to search. In particular, there is never any need to go upwards in the tree (which treeSuccessor will do).

Answer 4

First of all, your implementation got nothing to do with object orientation (except using objects). The insert and delete operations for example should operate ON the Tree.

Besides, I would recommend to implement the Node class as a static member of the Tree class.

public class Tree {
    private Node root = null;

    // remainder omitted

    public boolean insert(int element) {
        if (isEmpty()) {
            root = new Node(element);

            return true; // empty tree, Node could be inserted, return true
        }

         Node current = root; // start at root
         Node parent;         // the current Node's parent

         do {
             parent = current;

             if (element < current.element) {
                 current = current.left; // go to left
             } else if (element > current.element) {
                 current = current.right; // go to right
             } else {
                 return false;  // duplicates are NOT allowed, element could not be inserted -> return false

         } while (current != null);

         Node node = new Node(element);

         if (element < current.element) {
             parent.left = node;
         } else {
             parent.right = node;
         }

         return true; // node successfully inserted
    }

    public boolean isEmpty() {
        return root == null;
    }

    private static class Node { // static member class
        Node left  = null;
        Node right = null;
        final int element;

        Node(int element) {
            this.element = element;
        }
    }
}