Java Reference
In-Depth Information
ReturnObject
is an inner class that has a single data field and simple methods
set
and
get
to
manipulate it. Initially,
oldEntry
's data field is
null
, since
remove
returns
null
when the entry is
not found in the tree.
Thus, the public
remove
has the following implementation:
public
T remove(T entry)
{
ReturnObject oldEntry =
new
ReturnObject(
null
);
BinaryNodeInterface<T> newRoot = removeEntry(getRootNode(), entry,
oldEntry);
setRootNode(newRoot);
return
oldEntry.get();
}
// end remove
25.30
The private method
removeEntry
.
Since
remove
handles the communication with
removeEntry
, most
of the algorithm of Segment 25.28 is left for
removeEntry
. If the entry to be removed is in the root,
removeEntry
calls the yet-to-be-written method
removeFromRoot
to remove it. If the entry is in either of
the root's subtrees,
removeEntry
calls itself recursively. The implementation of
removeEntry
follows:
// Removes an entry from the tree rooted at a given node.
// rootNode is a reference to the root of a tree.
// entry is the object to be removed.
// oldEntry is an object whose data field is null.
// Returns the root node of the resulting tree; if entry matches
// an entry in the tree, oldEntry's data field is the entry
// that was removed from the tree; otherwise it is null.
private
BinaryNodeInterface<T> removeEntry(BinaryNodeInterface<T> rootNode,
T entry, ReturnObject oldEntry)
{
if
(rootNode !=
null
)
{
T rootData = rootNode.getData();
int
comparison = entry.compareTo(rootData);
if
(comparison == 0)
// entry == root entry
{
oldEntry.set(rootData);
rootNode = removeFromRoot(rootNode);
}
else
if
(comparison < 0)
// entry < root entry
{
BinaryNodeInterface<T> leftChild = rootNode.getLeftChild();
BinaryNodeInterface<T> subtreeRoot = removeEntry(leftChild,
entry, oldEntry);
rootNode.setLeftChild(subtreeRoot);
}
else
// entry > root entry
{
BinaryNodeInterface<T> rightChild = rootNode.getRightChild();
rootNode.setRightChild(removeEntry(rightChild, entry, oldEntry));
}
// end if
}
// end if
return
rootNode;
}
// end removeEntry
25.31
The algorithm
removeFromRoot
.
The previous method
removeEntry
removes the entry in the root of
a given subtree by calling the method
removeFromRoot
. In that method, we see whether the root node
has zero, one, or two children and then proceed according to the discussion in Segments 25.20 through
25.27. If the given node has at most one child, we delete the node and its entry. To remove the entry in a
