A Binary Search Tree Implementation - Data Structures and Abstractions with Java - page 641

FIGURE 25-7

(a) Four possible configurations of a node N that has one child;
(b) the resulting two possible configurations after removing node N

(a)

Node P Node P

Node P Node P

Node N Node N Node N

Node N

Node C Node C Node C Node C

(b)

Node P Node P

Node C

Node C

Removing an Entry Whose Node Has Two Children
25.22

The previous two cases are really not too difficult, conceptually or in practice. But this last case is a
bit involved. Once again, suppose that the entry to be removed is in a node N , but now N has two
children. Figure 25-8 shows two possible configurations for N . If we try to remove node N , we will
leave its two children without a parent. Although node P could reference one of them, it hasn't
room for both. Thus, removing node N is not an option.
We do not actually have to remove node N to remove its entry. Let's find a node A that is easy
to remove—it would have no more than one child—and replace N 's entry with the entry now in A .
We then can remove node A and still have the correct entries in the tree. But will the tree still be a
binary search tree? Clearly, node A cannot be just any node; it must contain an entry in the tree that
legally can be in node N .