Java Reference
In-Depth Information
Removing an entry is somewhat more involved than adding an entry, as the required logic depends
upon how many children belong to the node containing the entry. We have three possibilities:
•
The node has no children—it is a leaf
•
The node has one child
•
The node has two children
We now consider these three cases.
The simplest case in removing an entry is when the node is a leaf, that is, has no children. For
example, suppose that node
N
contains the entry to be removed from the binary search tree.
Figure 25-6a shows two possibilities for node
N
: It could be either the left child or the right child of
its parent node
P
. Since
N
is a leaf, we can delete it by setting the appropriate child reference in
node
P
to
null
. Figure 25-6b shows the result of this operation.
FIGURE 25-6
(a) Two possible configurations of a leaf node
N
; (b) the resulting
two possible configurations after removing node
N
(a)
Node
P
Node
P
Node
N
Node
N
(b)
Node
P
Node
P
Now imagine that the entry to be removed is in a node
N
that has exactly one child
C
. Figure 25-7a shows
the four possibilities for node
N
and
its parent
P
. To remove the entry in
N
, we remove
N
from the tree. We
do this by making
C
a child of
P
instead of
N
. As Figure 25-7b shows, if
N
was a left child of
P
, we make
C
be the left child of
P
. Likewise, if
N
was a right child of
P
, we make
C
be the right child of
P
.
