Deleting from a binary tree

[taylor.mitchell.353]

I have been working on this method for six days without any luck. I should have talked to you earlier. This method is from the book, but it only is deleting California. I cannot figure out why. I tried a couple different methods(recursive and others) and none of them worked. It is moving through a tree of state objects which are String objects. current.myState is the String of the State object. leftChild and rightChild are also State objects.

public boolean delete(String key) // delete node with given key
      {                           // (assumes non-empty list)
      State current = root;
      State parent = root;
      boolean isLeftChild = true;

      while(!current.myState.equals(key))        
         {
         parent = current;
         if(!key.equals(current.myState))         
            {
            isLeftChild = true;
            current = current.leftChild;
            }
         else                            
            {
            isLeftChild = false;
            current = current.rightChild;
            }
         if(current == null)             
            return false;                
         }  // end while
      // found node to delete
      // if no children, simply delete it
      if(current.leftChild==null && current.rightChild==null)
         {
         if(current == root)             
            root = null;                 
         else if(isLeftChild)
            parent.leftChild = null;     
         else                            
            parent.rightChild = null;
         }
      // if no right child, replace with left subtree
      else if( key.compareTo( current.myState ) < 0 )
         if(current == root)
            root = current.leftChild;
         else if(isLeftChild)
            parent.leftChild = current.leftChild;
         else
            parent.rightChild = current.leftChild;
      // if no left child, replace with right subtree
      else if( key.compareTo( current.myState ) > 0 )
         if(current == root)
            root = current.rightChild;
         else if(isLeftChild)
            parent.leftChild = current.rightChild;
         else
            parent.rightChild = current.rightChild;
      else  // two children, so replace with inorder successor
         {
         // get successor of node to delete (current)
         State successor = getSuccessor(current);
         // connect parent of current to successor instead
         if(current == root)
            root = successor;
         else if(isLeftChild)
            parent.leftChild = successor;
         else
            parent.rightChild = successor;
         // connect successor to current's left child
         successor.leftChild = current.leftChild;
         }  // end else two children
      return true;                               
      }  // end delete()

//------------------------------------------------------------------------------
   private State getSuccessor(State delNode)
      {
      State successorParent = delNode;
      State successor = delNode;
      State current = delNode.rightChild;   
      while(current != null)              
         {                                
         successorParent = successor;
         successor = current;
         current = current.leftChild;      
         }
      if(successor != delNode.rightChild)  
         {                                 
         successorParent.leftChild = successor.rightChild;
         successor.rightChild = delNode.rightChild;
         }
      return successor;
      }//end getSuccessor

For my Deletes I have. These are also supposed to start out with a new tree each time. I thought about deleting and inserting back, but that doesn't seem very efficient to me.

public void deleteStates()
    {

        System.out.println("\n\nAfter deleting nodes with zero children:");
        delete("Maryland");
        inOrder();
        System.out.println("\n\nAfter deleting nodes with one child:");
        delete("California");
        delete("Massachusetts");
        inOrder();
        System.out.println("\n\nAfter deleting nodes with two children:\n");
        delete("Vermont");
        delete("New_York");
        inOrder();
    }//end deleteStates()

My output

After deleting nodes with zero children:
California
Colorado
Connecticut
Delaware
Maine
Maryland <--should be deleted
Massachusetts
New_Hampshire
New_Jersey
New_York
Pennsylvania
Rhode_Island
Vermont
Virginia
West_Virginia


After deleting nodes with one child:
Colorado
Connecticut
Delaware
Maine
Maryland
Massachusetts  <--Should be deleted, but it deleted California
New_Hampshire
New_Jersey
New_York
Pennsylvania
Rhode_Island
Vermont
Virginia
West_Virginia


After deleting nodes with two children:

Colorado
Connecticut
Delaware
Maine
Maryland
Massachusetts
New_Hampshire
New_Jersey
New_York  <--Should be Deleted
Pennsylvania
Rhode_Island
Vermont  <-- Should be Deleted
Virginia
West_Virginia

[NormR1]

Can you post a small, complete program that compiles, executes and can be used for testing?

[taylor.mitchell.353]

I can only post a complete file because it wouldn't work as a smaller file.

It reads froma txt file called Tree.States

Maine
New_Hampshire
Vermont
Rhode_Island
Connecticut
Massachusetts
New_York
Pennsylvania
New_Jersey
West_Virginia
Virginia
Maryland
California
Delaware
Colorado

The main class is

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package project4mitchell;

import java.io.IOException;

/**
 *
 * @author TaylorMitchell
 */
public class Main 
{

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException 
    {
        // create an array of individual state objects to hold 50 items
        State_Controller myStateController;
        myStateController = new State_Controller();

        myStateController.loadData();
        myStateController.insertStates();
        myStateController.displayTree();
        myStateController.deleteStates();
    }//end main
}//end Main

I have an IO class called FileInterface

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package project4mitchell;

import java.io.*;
import java.util.*;
/**
 *
 * @author TaylorMitchell
 */
public class FileInterface 
{
    private int numStates = 0;
    private ArrayList<State> myStates = new ArrayList<State>();

    public int loadData(ArrayList myStates) throws IOException 
    {
    FileInputStream fis1 = new FileInputStream("Tree.States.txt"); 
    //obtains file statearray.txt
    BufferedReader br1 = new BufferedReader(new InputStreamReader(fis1)); 
    //reads statearray.txt
    String inputString, name;
    inputString = br1.readLine();

    while (inputString != null) 
        //while loop to continually create state objects
    {
        name = inputString; //parses the file for name
        myStates.add(name);
        numStates++; //increases state count
        inputString = br1.readLine();
    } // end while (inputString != null) 
    br1.close();
    return numStates;
    }//end loadData(String filename) throws IOException
}

My State class is essentially the node class for the tree

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package project4mitchell;

/**
 *
 * @author TaylorMitchell
 */
public class State 
{
    String myState;     // reference to a State object name
    State leftChild;        // this node’s left child
    State rightChild;       // this node’s right child.
    /**
     * Shows compiler what a States object is
     *
     * @param name: String
     * @returns States object
     */
    public State() 
    {

    }// end State()

//------------------------------------------------------------------------------
    /**
     * Makes String of states.
     *
     * @param str: String
     * @param stateName: String
     *
     * @return str: String
     */
    @Override
    public String toString() 
    {
        String s = String.format("%15s", myState);
        return s;
    }// end toSTring()
}// end State() constructor

It then is all places within a State_Controller class which creates the tree(not by making a State_Controller object. I already tried that)

package project4mitchell;

import java.io.*;
import java.util.*;
/**
 *
 * @author TaylorMitchell
 */
public class State_Controller 
{
    FileInterface IO = new FileInterface();
    private ArrayList<String> myStates = new ArrayList<String>();
    private FileInterface data;
    int numStates;
    State root;
    State newState;

    /**
     *
     */
    public State_Controller()
    {
        root = null;
    }//end State_Controller
    /**
     * Creates a new state object
     *
     * @param none 
     * @return void
     */
    public void loadData() throws IOException 
    {
        numStates=IO.loadData(myStates);
    } // end stateController()
//------------------------------------------------------------------------------    
    /**
     * Routine for displaying state objects.
     * 
     * @param none
     * @return void
     */
    public void displayStates() 
    {
        int index; //index is a local variable for state objects

        for (index = 0;
                index < myStates.size();
                index++) //for loop to continue making state objects stopping at numStates(50)
        {
            System.out.println(myStates.get(index)); //displays state objects(unsorted)
        }//end for loop    
    }//end displayStates()
//------------------------------------------------------------------------------
    /**
     *
     * @param nState: String
     * @return void
     */
    public void insert(String nState)
      {       
      State newNode = new State();    
      newNode.myState = nState;  

      if(root==null)                
                root = newNode;         
      else                                     
       {                
         State current = root;         
         State parent;              
         while(true)                    
         {
            parent = current;
            if (nState.compareTo(current.myState) < 0)  
            {
                    current = current.leftChild;  
                    if(current == null)         
                     {
                        parent.leftChild = newNode;    
                        return;             
                     }//end if
            }//end if
              else                
               {
                     current = current.rightChild;
                     if(current == null)   
                     {      
                        parent.rightChild = newNode;    
                        return;     
                     }//end if 
                } //end else
         }//end while
        }//end else
       }//end insert()
// -------------------------------------------------------------
    /**
     *
     * @param key
     * @return
     */
    public boolean delete(String key) // delete node with given key
      {                           // (assumes non-empty list)
      State current = root;
      State parent = root;
      boolean isLeftChild = true;

      while(!current.myState.equals(key))        // search for node
         {
         parent = current;
         if(!key.equals(current.myState))         // go left?
            {
            isLeftChild = true;
            current = current.leftChild;
            }//end if
         else                            // or go right?
            {
            isLeftChild = false;
            current = current.rightChild;
            }//end else
         if(current == null)             // end of the line,
             System.out.println("not found");
            return false;                // didn't find it
         }  // end while
      // found node to delete
      // if no children, simply delete it
      if(current.leftChild==null && current.rightChild==null)
         {
         if(current == root)             // if root,
            root = null;                 // tree is empty
         else if(isLeftChild)
            parent.leftChild = null;     // disconnect
         else                            // from parent
            parent.rightChild = null;
         }//end if
      // if no right child, replace with left subtree
      else if( key.compareTo( current.myState ) < 0 )
         if(current == root)
            root = current.leftChild;
         else if(isLeftChild)
            parent.leftChild = current.leftChild;
         else
            parent.rightChild = current.leftChild;
      // if no left child, replace with right subtree
      else if( key.compareTo( current.myState ) > 0 )
         if(current == root)
            root = current.rightChild;
         else if(isLeftChild)
            parent.leftChild = current.rightChild;
         else
            parent.rightChild = current.rightChild;
      else  // two children, so replace with inorder successor
         {
         // get successor of node to delete (current)
         State successor = getSuccessor(current);
         // connect parent of current to successor instead
         if(current == root)
            root = successor;
         else if(isLeftChild)
            parent.leftChild = successor;
         else
            parent.rightChild = successor;
         // connect successor to current's left child
         successor.leftChild = current.leftChild;
         }  // end else two children
      // (successor cannot have a left child)
      return true;                                // success
      }  // end delete()
//------------------------------------------------------------------------------
   /**
     *
     * @param delNode
     */
    private State getSuccessor(State delNode)
      {
      State successorParent = delNode;
      State successor = delNode;
      State current = delNode.rightChild;   // go to right child
      while(current != null)               // until no more
         {                                 // left children,
         successorParent = successor;
         successor = current;
         current = current.leftChild;      // go to left child
         }//end while
                                           // if successor not
      if(successor != delNode.rightChild)  // right child,
         {                                 // make connections
         successorParent.leftChild = successor.rightChild;
         successor.rightChild = delNode.rightChild;
         }//end if
      return successor;
      }//end getSuccessor
//------------------------------------------------------------------------------
    /**
     *
     * @param root: State 
     * @return void
     */
    public void inOrderRec(State root)
    {
        if (root != null)
        {
                inOrderRec (root.leftChild);
                System.out.println(root.myState);
                inOrderRec (root.rightChild);
        }// end if
    }//end inOrderRec
//------------------------------------------------------------------------------         
    /** Recursively traverses the binary tree in post-order
     *
     * @param root: State
     * @return void
     */
    public void postOrderRec(State root)
    {
        if (root != null)
        {
                postOrderRec (root.leftChild);
                postOrderRec (root.rightChild);
                System.out.println(root.myState);              
        }// end if
    }//end postOrderRec
//------------------------------------------------------------------------------         
    /** Recursively traverses the binary tree in pre-order
     *
     * @param root:State
     * @return void
     */
    private void preOrderRec(State root)
    {
        if (root != null)
        {
                System.out.println(root.myState);
                preOrderRec (root.leftChild);
                preOrderRec (root.rightChild);              
        }// end if
    }//end preOrderRec    
//------------------------------------------------------------------------------
   /** Iteratively traverses the binary tree in pre-order
    * 
    * @param none
    * @return void
    * 
    */
    private void preOrder() 
    {
        if (root == null) 
        {
            return;
        }//end if

        Stack<State> stack = new Stack<State>();
        stack.push(root);

        while (!stack.isEmpty()) 
        {
            State current = stack.pop();
            if (current.rightChild != null) 
            {
                stack.push(current.rightChild);
            }//end if
            if (current.leftChild != null) 
            {
                stack.push(current.leftChild);
            }//end if
            System.out.println(current.myState);
        }//end while
    }//end preOrder()
//------------------------------------------------------------------------------ 
    /** Iteratively traverses the binary tree in in-order 
     * 
     * @param none
     * @return void
     */ 

    public void inOrder() 
    {
        State node = root;
        Stack<State> stack = new Stack<State>();
        while (!stack.isEmpty() || node != null) 
        {
            if (node != null) 
            {
                stack.push(node);
                node = node.leftChild;
            } //end if
            else 
            {
                node = stack.pop();
                System.out.println(node.myState);
                node = node.rightChild;
            } //end else
        }//end while
    }//end inOrder()
//------------------------------------------------------------------------------ 
/** Iteratively traverses the binary tree in post-order
 * 
 * @param none
 * @return void
 */ 
    public void postOrder() 
    {
        if (root == null) 
        {
            return;
        }//end if

        Stack<State> stack = new Stack<State>();
        State current = root;

        while (true) 
        {
            if (current != null) 
            {
                if (current.rightChild != null) 
                {
                    stack.push(current.rightChild);
                }//end if
                stack.push(current);
                current = current.leftChild;
                continue;
            }//end if

            if (stack.isEmpty()) 
            {
                return;
            }//end if
            current = stack.pop();

            if (current.rightChild != null && !stack.isEmpty()
                    && current.rightChild == stack.peek()) 
            {
                stack.pop();
                stack.push(current);
                current = current.rightChild;
            } //end if
            else 
            {
                System.out.println(current.myState);
                current = null;
            } //end if
        }//end while
    }// end postOrder()
//------------------------------------------------------------------------------        
    /**
     *
     */
    public void insertStates()
   {
       int index;
       for (index = 0;
                index < myStates.size();
                index++)
       {
       insert(myStates.get(index));
       }//end for
   }//end insertStates()
//------------------------------------------------------------------------------   
    /**
     *
     */
    public void displayTree()
    {
        System.out.println("\n\nIterative NLR Scan\nState Name\n"
                + "-----------------");
        preOrder();
        System.out.println("\n\nIterative LNR Scan\nState Name\n"
                + "-----------------");
        inOrder();
        System.out.println("\n\nIterative LRN Scan\nState Name\n"
                + "-----------------");
        postOrder();
        System.out.println("\n\nNLR format – recursive scan"
                + "\nState Name\n-----------------");
        preOrderRec(root);
        System.out.println("\n\nLNR format – recursive scan"
                + "\nState Name\n-----------------");
        inOrderRec(root);
        System.out.println("\n\nLRN format - recursive scan"
                + "\nState Name\n-----------------");
        postOrderRec(root);
    }//end displayTree()
//------------------------------------------------------------------------------
    /**
     *
     */
    public void deleteStates()
    {

        System.out.println("\n\nAfter deleting nodes with zero children:");
        delete("Maryland");
        delete("Colorado");
        inOrder();
        System.out.println("\n\nAfter deleting nodes with one child:");
        delete("California");
        delete("Massachusetts");
        inOrder();
        System.out.println("\n\nAfter deleting nodes with two children:\n");
        delete("Vermont");
        delete("New_York");
        inOrder();
    }//end deleteStates()
}//end State_Controller class

That is the smallest I can make it.

[NormR1]

How have you tried debugging the code to see what it is doing? I normally add lots of println statements to show the logic flow and to show the values of variables the are used to control logic. I don't see any debugging printlns in the code.

[taylor.mitchell.353]

I figured it out. I was using .equals instead of compareTo. It works perfectly now. Any idea what would be a good idea to make the tree refresh before each run?

Currently I have it doing this(below), but my teacher says that we can do it this way, but there is a better method. I've been looking around how to do this. Any suggestions?

 /**
     *
     */
    public void deleteStates()
    {

        System.out.println("\n\nAfter deleting nodes with zero children:");
        delete("Maryland");
        inOrder();
        insert("Maryland");
        System.out.println("\n\nAfter deleting nodes with one child:");
        delete("California");
        delete("Massachusetts");
        inOrder();
        insert("California");
        insert("Massachusetts");
        System.out.println("\n\nAfter deleting nodes with two children:\n");
        delete("Vermont");
        delete("New_York");
        inOrder();
    }//end deleteStates()

My updated method for delete if needed

    /** Deletes a State from the tree
     *
     * @param key: String
     * @return boolean
     */
    public boolean delete(String key) // delete node with given key
      {                           // (assumes non-empty list)
      State current = root;
      State parent = root;
      boolean isLeftChild = true;

      while(current.myState.compareTo(key)!=0)        // search for node
         {
         parent = current;
         if(key.compareTo(current.myState)<0)         // go left?
            {
            isLeftChild = true;
            current = current.leftChild;
            }//end if
         else                            // or go right?
            {
            isLeftChild = false;
            current = current.rightChild;
            }//end else
         if(current == null)             // end of the line,
            return false;                // didn't find it
         }  // end while
      // found node to delete
      // if no children, simply delete it
      if(current.leftChild==null && current.rightChild==null)
         {
         if(current == root)             // if root,
            root = null;                 // tree is empty
         else if(isLeftChild)
            parent.leftChild = null;     // disconnect
         else                            // from parent
            parent.rightChild = null;
         }//end if
      // if no right child, replace with left subtree
      else if(current.rightChild == null)
         if(current == root)
            root = current.leftChild;
         else if(isLeftChild)
            parent.leftChild = current.leftChild;
         else
            parent.rightChild = current.leftChild;
      // if no left child, replace with right subtree
      else if(current.leftChild == null)
         if(current == null)
            root = current.rightChild;
         else if(isLeftChild)
            parent.leftChild = current.rightChild;
         else
            parent.rightChild = current.rightChild;
      else  // two children, so replace with inorder successor
         {
         // get successor of node to delete (current)
         State successor = getSuccessor(current);
         // connect parent of current to successor instead
         if(current == root)
            root = successor;
         else if(isLeftChild)
            parent.leftChild = successor;
         else
            parent.rightChild = successor;
         // connect successor to current's left child
         successor.leftChild = current.leftChild;
         }  // end else two children
      // (successor cannot have a left child)
      return true;                                // success
      }  // end delete()
//------------------------------------------------------------------------------
   /** Obtains successor node for two children
     *
     * @param delNode:State
     * @return State
     */
    private State getSuccessor(State delNode)
      {
      State successorParent = delNode;
      State successor = delNode;
      State current = delNode.rightChild;   // go to right child
      while(current != null)               // until no more
         {                                 // left children,
            successorParent = successor;
            successor = current;
            current = current.leftChild;      // go to left child
         }//end while
                                           // if successor not
      if(successor != delNode.rightChild)  // right child,
         {                                 // make connections
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
         }//end if
      return successor;
      }//end getSuccessor

[Taywin]

The reason you need compareTo() because you need to know which branch you are going to work when 1)the key is not found at the current searching node and 2)the direction you will go down the tree (either left or right). The compareTo() will give you all information at once -- the node is found, need to go to the left branch, or need to go to the right branche.

When you ask about other algorithms, you must not dump your code and ask people to figure out what you have done. I don't even know what algorithm of your tree is. Is it a self-balanced tree? Is it an AV-tree? Is it just a simple binary tree? Each type of tree will have an optimised implementation in order to maintain its type.

but my teacher says that we can do it this way, but there is a better method

There may or may not be a better way because it is subjective. You could use recursive to deal with too because the code will be shorter, but it is more complicated and could require more resources when run.

[NormR1]

Some problems I saw in your earlier code:
1)It does not test the value returned by delete.
2)Many of the if/else statements do not use {}s to enclose the following code. You should ALWAYS use {}s with if/else statements.
3) Lack of comments how and what the code was supposed to do. For example why go left or right when traversing the tree based on the equality of the keys. If you had written some comments before the if test saying what the code was to do, they would have reminded you that you wanted to know greater than and less than vs equality.

[taylor.mitchell.353]

Ah sorry it is a simple binary tree.

The if/else statements don't use {} because our teacher doesn't like those when the compiler can interpret them without it. I don't agree with it, but that's how he wants it done

The comments I typically do to finalize the project. I probably should do that before posting it here, but I don't do them until the end because I know how it should go. Our teacher explained to us we need the comments for other people to read our code.

The code works as is I just wanted to try a different method to deal with it. I wasn't asking for code just someone to point me in the right direction. I am officially done with the project but I would like to try other methods. I know there is a recursive method of delete I want to see if I can get working. It's not due for 4 days so this is just for me. I have to make pseudocode for the entire project as well and a UML, but that shouldn't take long.

[NormR1]

Here's an example of what happens if you don't always use {}s. The println was added, pushing the return outside the if, destroying the logic.

         if(current == null)             // end of the line,
             System.out.println("not found");
            return false;                // didn't find it

I try to design the code before I write it. I then copy the design for each section of the code into the code at the place where it describes the code to follow. I can the refer to the comments as I write the code to be sure I am following the logic correctly. The comments are there to help me write correct code. I think that if you add added comments BEFORE writing the code, you would not have used equals() to select the left or right branch.

[taylor.mitchell.353]

ok I will keep that in mind for next time. I am working on a recursive routine for my delete for fun. It seems to be working, but I'm not sure how to implement it for two children.

public State lift(State current, State toRemove)
  {
     if (current.rightChild == null) 
     {
       toRemove = current;
       return current.leftChild;  
     }
     else 
     {
       current.rightChild = lift(current.rightChild,toRemove);
       return current;
     }
  }

    public State delete (State current, String key)
  {
    if (current == null)
    {
      current = current.rightChild;
      }
    else if (current.myState.compareTo(key)==0) 
    {
       if (current.leftChild==null)
       {
         return current.rightChild;
        }
       else if (current.rightChild==null)
       {
         return current.leftChild;
       }
       else
       { 
         current.leftChild = lift(current.leftChild,current);
         return current;
       }
    }
    else if (key.compareTo(current.myState)<0)
    {
        current.leftChild  = delete(current.leftChild,key);
    }
    else
    {
        current.rightChild = delete(current.rightChild,key);
        return current;
    }
    return current;
  }

[NormR1]

Not many comments in the code about what it is supposed to be doing.

It seems to be working,

Looks like it needs some testing. What about lines 17 and 19?