I need help with my remove method on a BST
// If the key exists, remove the key/value mapping from the collection and
// return true. If the key is not found return false and leave the
// collection
// in the same state.Precondition: K implements Comparable.
publicboolean remove(K keyOfelementToRemove){
boolean result =false;
if (root ==null)
result =false;
else{
MapNode curr = root;
MapNode prev = root;
while (prev.left.key != keyOfelementToRemove
|| prev.right.key != keyOfelementToRemove){
curr = prev;
if (keyOfelementToRemove.compareTo(prev.key) < 0)
prev = prev.left;
if (keyOfelementToRemove.compareTo(prev.key) > 0)
prev = prev.right;
}
if (prev.left.key.compareTo(keyOfelementToRemove) == 0)
curr = prev.left;
else
curr = prev.right;
if (curr ==null)
return result;
elseif (curr == root && root.left ==null)
root = root.right;
elseif (prev.left ==null){
if (curr.key == prev.left.key)
prev.left = curr.right;
else
prev.right = curr.right;
}elseif (curr.left !=null){
}
}
return result;
}
I have to implement this algorithm
private boolean remove( BinaryTreeNode t, Comparable elementToRemove )
{
Set result to false
Traverse the tree t until elementToRemove is found. Use curr and prev to find the element
leaving curr referring the node you want to remove. It may be the case that curr is null indicating
that elementToRemove was not found. Now there are four cases to consider :
Case 1: Not found
return result (false)
Case 2: The root is to be removed, but it has no left child.
root = root's right subtree (assuming root refers the the root node in your BST)
Case 3: The node is further down tree with no left child. Now must adjust one of the parent's links
if curr is on the left side of prev,
move parent's left link down to down to curr's right child
else
curr is on the right side of prev, so move parent's right down to down to curr's right child
Case 4: curr has a left child.
We can no longer ignore the left subtree. So find the maximum in the left subtree and
move that object to the node referenced by curr . Then eliminate the maximum in the
left subtree, which is now being reference from the original node to remove.
}
Is this right?
