Java Reference
In-Depth Information
private
BinaryNodeInterface<T> findLargest(BinaryNodeInterface<T> rootNode)
{
if
(rootNode.hasRightChild())
rootNode = findLargest(rootNode.getRightChild());
return
rootNode;
}
// end findLargest
25.34
The private method
removeLargest
.
To remove the node with the largest entry, we cannot simply
call
findLargest
and then remove the returned node. We cannot remove a node from a tree know-
ing only its reference. We must have a reference to its parent as well. The following recursive
method removes the node with the largest entry—that is, the rightmost node—but unfortunately it
must repeat the search that
findLargest
just performed.
// Removes the node containing the largest entry in a given tree.
// rootNode is the root node of the tree.
// Returns the root node of the revised tree.
private
BinaryNodeInterface<T> removeLargest(BinaryNodeInterface<T> rootNode)
{
if
(rootNode.hasRightChild())
{
BinaryNodeInterface<T> rightChild = rootNode.getRightChild();
BinaryNodeInterface<T> root = removeLargest(rightChild);
rootNode.setRightChild(root);
}
else
rootNode = rootNode.getLeftChild();
return
rootNode;
}
// end removeLargest
The method begins much like
findLargest
. To remove the rightmost node from the given tree,
we remove the rightmost node from tree's right subtree. The recursive call returns the root of the
revised subtree. This root must become the right child of the original tree's root.
When a tree's root has no right child, the left child is returned, effectively deleting the root.
Notice that this recursive method does not explicitly keep track of the parent of the current right
child. Rather, a reference to this parent is retained in the implicit stack of the recursion.
Note:
The previous recursive approach to removing an entry from a binary search tree is
typical. A language, such as Java, that uses only call-by-value to pass arguments tends to
complicate this recursive implementation by forcing methods to return references to root
nodes. You might find the following iterative approach somewhat easier to understand. Since
it deletes the node containing the inorder predecessor without repeating the search for it, the
iterative
remove
is more efficient than the recursive version.
The algorithm.
Recall that the method
remove
is given an entry that matches the entry to be
removed from the tree. So
remove
's first step is to search the tree. We locate the node whose data
matches the given entry, and we note the node's parent, if any. Whether we delete the node we've
found or another one depends on how many children it has. Although Segment 25.19 listed three
possibilities, we can collapse them into two cases:
1.
The node has two children
2.
The node has at most one child
