views:

64

answers:

2

Hello All, I have been using a driver to test one of my data structures(Binary Search Tree) and i have come across this issue. -It happens when i insert more than 2 objects into the bst -What I am trying to do: I am inserting 4 objects into the tree, then i am deleting 2 objects, and then printing out my find method so that it displays whether or not it found the objects i request. for instance:

public class Driver5 {

public static void main(String[] args) {
  Integer c1 = new Integer(1);
  Integer c2 = new Integer(2);
  Integer c3 = new Integer(3);
  Integer c4 = new Integer(4);
    Integer c5 = new Integer(5);
    Integer c6 = new Integer(6);
    Integer c7 = new Integer(7);
    Integer c8 = new Integer(8);
    Integer c9 = new Integer(9);
    Integer c10 = new Integer(10);
    Integer c11 = new Integer(11);
    Integer c12 = new Integer(23);
    Integer c13 = new Integer(65);
    Integer c14 = new Integer(45);
    Integer c15 = new Integer(18);
    Integer c16 = new Integer(33);
    Integer c17 = new Integer(54);

  DataStructure1<Integer> theData = new DataStructure1<Integer>();
    System.out.println("DS1");    
     long start = System.currentTimeMillis();  
   theData.insert(c1);
  theData.insert(c2);
  theData.insert(c3);
  theData.insert(c4);
    theData.insert(c5);
    theData.insert(c6);
    theData.insert(c7);
    theData.insert(c8);
    theData.insert(c9);
    theData.insert(c10);
    theData.insert(c11);
    theData.insert(c12);
    theData.insert(c13);
    theData.insert(c14);
    theData.insert(c15);
    theData.insert(c16);
    theData.insert(c17);
    theData.delete(c2);
    theData.delete(c4);
    System.out.println(theData.find(c1));
    System.out.println(theData.find(c2));
    System.out.println(theData.find(c3));
    System.out.println(theData.find(c4));
    theData.delete(c2);
    theData.insert(c3);
    System.out.println(theData.find(c2));
    System.out.println(theData.find(c3));
    System.out.println(theData.find(c4));
    System.out.println(theData.find(c5));
    System.out.println(theData.find(c6));
    System.out.println(theData.find(c7));
    System.out.println(theData.find(c8));
    System.out.println(theData.find(c9));
    System.out.println(theData.find(c10));
    System.out.println(theData.find(c11));
    System.out.println(theData.find(c12));
    System.out.println(theData.find(c13));
    System.out.println(theData.find(c14));
    System.out.println(theData.find(c15));
    System.out.println(theData.find(c16));
    System.out.println(theData.find(c17));

    long elapsed = System.currentTimeMillis() - start;
    System.out.println("The time elapsed was: " + elapsed + " ms.");
    System.out.println();

BinarySearchTree<Integer> theData1 = new BinarySearchTree<Integer>();
     System.out.println("BST");    
    long start1 = System.currentTimeMillis();  
   theData1.insert(c1);
  theData1.insert(c2);
  theData1.insert(c3);
  theData1.insert(c4);
    theData1.insert(c5);
    theData1.insert(c6);
    theData1.insert(c7);
    theData1.insert(c8);
    theData1.insert(c9);
    theData1.insert(c10);
    theData1.insert(c11);
    theData1.insert(c12);
    theData1.insert(c13);
    theData1.insert(c14);
    theData1.insert(c15);
    theData1.insert(c16);
    theData1.insert(c17); 
    theData1.delete(c2);
    theData1.delete(c4);
    System.out.println(theData1.find(c1));
    System.out.println(theData1.find(c2));
    System.out.println(theData1.find(c3));
    System.out.println(theData1.find(c4));
    theData1.delete(c2);
    theData1.insert(c3);
    System.out.println(theData1.find(c2));
    System.out.println(theData1.find(c3));
    System.out.println(theData1.find(c4));
    System.out.println(theData1.find(c5));
    System.out.println(theData1.find(c6));
    System.out.println(theData1.find(c7));
    System.out.println(theData1.find(c8));
    System.out.println(theData1.find(c9));
    System.out.println(theData1.find(c10));
    System.out.println(theData1.find(c11));
    System.out.println(theData1.find(c12));
    System.out.println(theData1.find(c13));
    System.out.println(theData1.find(c14));
    System.out.println(theData1.find(c15));
    System.out.println(theData1.find(c16));
    System.out.println(theData1.find(c17)); 

    long elapsed1 = System.currentTimeMillis() - start1;
    System.out.println("The time elapsed was: " + elapsed1 + " ms.");




}


} 

I get an error in bst at:

if( nd.getLeft() == null && nd.getRight() == null)
        {

            nd = null;
        }

whole delete is:

public void delete(E item) {

        TreeNode<E> nd = root;

        while(nd != null && nd.getItem().compareTo(item) != 0)
        {
            if(nd.getItem().compareTo(item) < 0)
                nd = nd.getRight();

            else
                 nd = nd.getLeft();
        }

        if( nd.getLeft() == null && nd.getRight() == null)
        {

            nd = null;
        }

        else if(nd.getLeft() != null && nd.getRight() == null)

        {
            nd.setItem((E)nd.getLeft().getItem());

        }
        else if(nd.getLeft() == null && nd.getRight() != null)
        {    
            nd.setItem((E)nd.getRight().getItem());

        }

        else if(nd.getLeft() != null && nd.getRight() != null)
        {

            nd.setItem((E)findsucc(nd));
        }    


}
A: 

nd must be null for some reason. Check it before calling getLeft() or getRight() on it.

Colin Hebert
Learned something new i should have known a long long time ago, thanks a lot peeps appreciate your help
@user450267 if an answer has worked for you, mark it as accepted (tick below the vote counter)
Bozho
+2  A: 

if nd is null, then you can't call getLeft() on it. So make your check

if (nd != null && nd.getLeft() == null && nd.getRight() == null)

See all causes of a NullPointerException, so that next time you encounter it, you know what to do immediately.

Bozho