Here is the pseudo-code for TreeNode.remove and TreeNode.findNext
that was discussed in class.
This solution differs slightly from the framework that was posted (as
was discussed in class).
TreeNode findNext( TreeNode target) // note, here target is a TreeNode
, not general Object
// precondition: target is in this subtree
// postcondition: return value is next TreeNode in the tree else
it is null
case:
this == target : // next could be in the right
subtree
if right == null then return null // means "next"
not in this subtree
else return right.getMinNode() endif;
target.item < item: temp = left.findNext( target);
if temp == null then return this // target was last
node in my left subtree
else return temp endif;
target.item > item: return right.findNext();
endcase;
/*************************************************************************
//an instance of class RemoveEvent will be used to return the information
//that a TreeNode was removed,
//so that the size can be decremented
class RemoveEvent
{ boolean removed = false;} <<<default is "false"
TreeNode remove( Object target, RemoveEvent e)
// here target is an Object
, so it can be called by MySortedSet.remove(o)
pre: e.removed == false
post: return value is the (possibly) modified subtree
and e.removed == true
if a node was removed
case: target == item : //
this is the node to be removed
set removed;
case: no_children : return null; // left node
removed
no_right_child: return left; // internal node removed
no_left_child: return right; // internal node removed
has_both : // internal node replaced
replace item with left.getMax().item,
left.remove( left.getMax(), new RemoveEvent)
endcase;
target<item : if no_left then return
this; // nothing to remove
else left = left.remove( target, e); return this; //
let the left child do it
item < target: // by symmetry
note: be sure to decrement size in the calling method in
case e.removed was set to true.