Java Reference
In-Depth Information
FIGURE 25-10
The largest entry
a
in node
N
's left subtree occurs in the subtree's rightmost
node
R
Node
N
e
a
Node
R
25.25
The following pseudocode summarizes this discussion:
Algorithm Delete the entry e from a node N that has two children
Find the rightmost node R in N's left subtree
Replace the entry in node N with the entry that is in node R
Delete node R
An alternate approach involves
b
, the entry that is immediately after
e
in sorted order. We have
already noted that
b
occurs in
N
's right subtree. It would have to be the smallest entry in that sub-
tree, so it would occur in the leftmost node in the subtree. Thus, we have the following alternate
pseudocode:
Algorithm Delete the entry e from a node N that has two children
Find the leftmost node L in N's right subtree
Replace the entry in node N with the entry that is in node L
Delete node L
Both approaches work equally well.
Note:
To remove an entry whose node has two children, you first replace the entry with
another whose node has no more than one child. You then remove the second node from the
binary search tree.
25.26
Example.
Figure 25-11 shows several consecutive removals from a binary search tree of names.
The first algorithm given in the previous segment is used. To remove
Chad
from the tree in
Figure 25-11a, we replace it with its inorder predecessor
Brittany
. We then remove the node that
contained
Brittany
to get the tree in Figure 25-11b. To remove
Sean
from this new tree, we replace
it with its inorder predecessor
Reba
and remove
Reba
's original node. This gives us the tree in
Figure 25-11c. Finally, to remove
Kathy
from this tree, we replace it with its inorder predecessor
Doug
and remove
Doug
's original node, to get the tree in Figure 25-11d.
