Java Reference
In-Depth Information
FIGURE 25-12
(a) Two possible configurations of a root that has one child;
(b) after removing the root
(a)
e
Node
N
e
Node
N
Node
C
Node
C
(b)
Node
C
The algorithm.
The entry to be removed from the tree is the one that matches the object passed to
the method
remove
as its argument. The method returns the removed entry. The following recursive
algorithm describes the method's logic at a high level:
Algorithm
remove(binarySearchTree, entry)
oldEntry =
null
if
(binarySearchTree
is not empty
)
{
if
(entry
matches the entry in the root of
binarySearchTree)
{
oldEntry =
entry in root
removeFromRoot(
root of
binarySearchTree)
}
else if
(entry <
entry in root
)
oldEntry = remove(
left subtree of
binarySearchTree, entry)
else
// entry >
entry in root
oldEntry = remove(
right subtree of
binarySearchTree, entry)
}
return
oldEntry
The method
removeFromRoot
will remove the entry in the root of a given subtree based on how
many children belong to the root.
25.29
The public method
remove
.
We have several details to consider before implementing the previous
algorithm. The public method
remove
should have only one parameter—
entry
—so just as the
method
add
calls the private recursive method
addEntry
,
remove
will call a private recursive
method
removeEntry
.
As we mentioned in Segment 25.8, we will pass the root of the tree, instead of the tree itself, to
removeEntry
. Since the method might remove the root node from the tree, we must be careful to
always retain a reference to the tree's root. As a result, we make
removeEntry
return a reference to the
root of the revised tree, which
remove
can save. But
removeEntry
must also give to
remove
the entry
it removes. A solution is to pass another parameter—
oldEntry
—to
removeEntry
and have the
method change its value to the removed entry. Thus, the header for
removeEntry
will be
private
BinaryNodeInterface<T> removeEntry(BinaryNodeInterface<T> rootNode,
T entry, ReturnObject oldEntry)
