Java Reference
In-Depth Information
FIGURE 25-8
Two possible configurations of a node
N
that has two children
(a)
(b)
Node
P
Node
P
Node
N
Node
N
Node
C
L
Node
C
R
Node
C
L
Node
C
R
25.23
We know that the entries in the tree are distinct. Let
e
be the entry in node
N
. Since node
N
has two
children,
e
is larger than the entry in
N
's left child and smaller than the entry in
N
's right child.
Thus,
e
cannot be the smallest entry in the tree, nor can it be the largest. So, if we imagine the tree's
entries in ascending order, we can write
...
a
<
e
<
b
...
Here,
a
is the entry that is immediately before
e
, and
b
is the one that is immediately after. An inor-
der traversal of the tree would visit these entries in this same order. Thus,
a
is called the
inorder
predecessor
of
e,
and
b
is the
inorder successor
of
e
.
The entry
a
must occur in a node in
N
's left subtree;
b
is in a node in
N
's right subtree, as Figure 25-9a
illustrates. Moreover,
a
is the largest entry in
N
's left subtree, since
a
is the entry that is immediately
before
e
. Suppose that we are able to delete the node that contains
a
and replace
e
with
a
, as Figure 25-9b
shows. Now all of the remaining entries in
N
's left subtree are less than
a
, as needed. All of the entries in
N
's right subtree are greater than
e
and so are greater than
a
. Thus, we still have a binary search tree.
FIGURE 25-9
Node
N
and its subtrees: (a) the entry
a
is immediately before the entry
e
,
and
b
is immediately after
e
; (b) after deleting the node that contained
a
and
replacing
e
with
a
(a)
(b)
e
a
Node
N
Node
N
b
a
b
Entries
e
Entries
a
Entries
e
Entries
e
a
25.24
Locating the entry
a
.
The previous segment assumed that we could find the appropriate entry
a
and
delete its node. So, let's locate the node that contains
a
and verify that it does not have two children.
Consider again the original tree in Figure 25-9a. We already know that
a
must be in
N
's left subtree,
and that
a
is the largest entry in that subtree. To find an entry larger than the one in any given node,
we look at the node's right child. Thus,
a
occurs in the subtree's rightmost node
R
, as Figure 25-10
illustrates. Node
R
cannot have a right child, because if it did, the child's entry would be greater than
a
. Therefore, node
R
has no more than one child and so can be removed from the tree easily.
