Java Reference
In-Depth Information
node having two children, we must find the largest entry in the node's left subtree. We remove the node
containing this largest entry. The largest entry then replaces the entry to be removed.
The following algorithm summarizes these steps:
Algorithm
removeFromRoot(rootNode)
//
Removes the entry in a given root node of a subtree.
if
(rootNode
has two children
)
{
largestNode =
node with the largest entry in the left subtree of
rootNode
Replace the entry in
rootNode
with the entry in
largestNode
Remove
largestNode
from the tree
}
else if
(rootNode
has a right child
)
rootNode = rootNode
's right child
else
rootNode = rootNode
's left child
//
possibly
null
//
Assertion: if
rootNode
was a leaf, it is now
null
return
rootNode
25.32
The private method
removeFromRoot
.
The implementation of the previous algorithm calls the private
methods
findLargest
and
removeLargest
, which we will write shortly. Although
removeFromRoot
is
not recursive, both
findLargest
and
removeLargest
are.
Given the root of a subtree,
removeFromRoot
returns the root of the subtree after a node is removed.
// Removes the entry in a given root node of a subtree.
// rootNode is the root node of the subtree.
// Returns the root node of the revised subtree.
private
BinaryNodeInterface<T> removeFromRoot(BinaryNodeInterface<T> rootNode)
{
// Case 1: rootNode has two children
if
(rootNode.hasLeftChild() && rootNode.hasRightChild())
{
// find node with largest entry in left subtree
BinaryNodeInterface<T> leftSubtreeRoot = rootNode.getLeftChild();
BinaryNodeInterface<T> largestNode = findLargest(leftSubtreeRoot);
// replace entry in root
rootNode.setData(largestNode.getData());
// remove node with largest entry in left subtree
rootNode.setLeftChild(removeLargest(leftSubtreeRoot));
}
// end if
// Case 2: rootNode has at most one child
else if
(rootNode.hasRightChild())
rootNode = rootNode.getRightChild();
else
rootNode = rootNode.getLeftChild();
// Assertion: if rootNode was a leaf, it is now null
return
rootNode;
}
// end removeEntry
25.33
The private method
findLargest
.
The node with the largest entry will occur in the rightmost
node of a binary search tree. Thus, as long as a node has a right child, we search the subtree rooted
at that child. The following recursive method performs this search, given the tree:
// Finds the node containing the largest entry in a given tree.
// rootNode is the root node of the tree.
// Returns the node containing the largest entry in the tree.
