Java Reference
In-Depth Information
SUBROOT
10
5
20
9
5
Figure5.16
An example of deleting the node with minimum value. In this tree,
the node with minimum value, 5, is the left child of the root.
Thus, the root's
left
pointer is changed to point to 5's right child.
Removing a node with given key value R from the BST requires that we first
find R and then remove it from the tree. So, the first part of the remove operation
is a search to find R. Once R is found, there are several possibilities. If R has no
children, then R's parent has its pointer set to
null
. If R has one child, then R's
parent has its pointer set to R's child (similar to
deletemin
). The problem comes
if R has two children. One simple approach, though expensive, is to set R's parent
to point to one of R's subtrees, and then reinsert the remaining subtree's nodes one
at a time. A better alternative is to find a value in one of the subtrees that can
replace the value in R.
Thus, the question becomes: Which value can substitute for the one being re-
moved? It cannot be any arbitrary value, because we must preserve the BST prop-
erty without making major changes to the structure of the tree. Which value is
most like the one being removed? The answer is the least key value greater than
(or equal to) the one being removed, or else the greatest key value less than the one
being removed. If either of these values replace the one being removed, then the
BST property is maintained.
Example5.7
Assume that we wish to remove the value 37 from the BST
of Figure 5.13(a). Instead of removing the root node, we remove the node
with the least value in the right subtree (using the
deletemin
operation).
This value can then replace the value in the root. In this example we first
remove the node with value 40, because it contains the least value in the
right subtree. We then substitute 40 as the new value for the root node.
Figure 5.17 illustrates this process.
When duplicate node values do not appear in the tree, it makes no difference
whether the replacement is the greatest value from the left subtree or the least value
from the right subtree. If duplicates are stored, then we must select the replacement
