Java – delete method binary search tree
I'm trying to implement a remove method for the BST structure I've been studying The following code contains the find, insert and remove methods:
public class BST { BSTNode root = new BSTNode("root"); public void insert(BSTNode root,String title){ if(root.title!=null){ if(title==root.title){ //return already in the catalog } else if(title.compareTo(root.title)<0){ if(root.leftChild==null){ root.leftChild = new BSTNode(title); } else{ insert(root.leftChild,title); } } else if(title.compareTo(root.title)>0){ if(root.rightChild==null){ root.rightChild = new BSTNode(title); } else{ insert(root.rightChild,title); } } } } public void find(BSTNode root,String title){ if(root!= null){ if(title==root.title){ //return(true); } else if(title.compareTo(root.title)<0){ find(root.leftChild,title); } else{ find(root.rightChild,title); } } else{ //return false; } } public void remove(BSTNode root,String title){ if(root==null){ return false; } if(title==root.title){ if(root.leftChild==null){ root = root.rightChild; } else if(root.rightChild==null){ root = root.leftChild; } else{ //code if 2 chlidren remove } } else if(title.compareTo(root.title)<0){ remove(root.leftChild,title); } else{ remove(root.rightChild,title); } } }
I was told that I could use the insert method to help me use the remove method, but I just didn't see how I grabbed the minimum / maximum element, then replaced the element I wanted to delete with the value, and then recursively deleted the node i got the replacement value, while still maintaining the O (logn) complexity Does anyone have any ideas or blatant loopholes I missed, or anything else useful because I have a headache about this problem?
Editor: I used the idea of the answer to put forward this. I believe it will work, but I got an error. My method (not just delete) must return a string. Here is what the code looks like. I think this is a return statement??
public String remove(BSTNode root,String title){ if(root==null){ return("empty root"); } if(title==root.title){ if(root.leftChild==null){ if(root.rightChild==null){ root.title = null; return(title+ "was removed"); } else{ root = root.rightChild; return(title+ "was removed"); } } else if(root.rightChild==null){ root = root.leftChild; return(title+ "was removed"); } else{ String minTitle = minTitle(root); root.title = minTitle; remove(root.leftChild,minTitle); return(title+ "was removed"); } } else if(title.compareTo(root.title)<0){ remove(root.leftChild,title); } else{ remove(root.rightChild,title); } }
Solution
public void remove (String key,BSTNode pos)
public void remove (String key,BSTNode pos) { if (pos == null) return; if (key.compareTo(pos.key)<0) remove (key,pos.leftChild); else if (key.compareTo(pos.key)>0) remove (key,pos.rightChild); else { if (pos.leftChild != null && pos.rightChild != null) { /* pos has two children */ BSTNode maxFromLeft = findMax (pos.leftChild); //need to make a findMax helper //"Replacing " pos.key " with " maxFromLeft.key pos.key = maxFromLeft.key; remove (maxFromLeft.key,pos.leftChild); } else if(pos.leftChild != null) { /* node pointed by pos has at most one child */ BSTNode trash = pos; //"Promoting " pos.leftChild.key " to replace " pos.key pos = pos.leftChild; trash = null; } else if(pos.rightChild != null) { /* node pointed by pos has at most one child */ BSTNode trash = pos; /* "Promoting " pos.rightChild.key" to replace " pos.key */ pos = pos.rightChild; trash = null; } else { pos = null; } } }