Java Reference
In-Depth Information
when the
remove
method is implemented, the special case is handled auto-
matically.
The complicated case deals with a node having two children. The general
strategy is to replace the item in this node with the smallest item in the right
subtree (which is easily found, as mentioned earlier) and then remove that
node (which is now logically empty). The second
remove
is easy to do
because, as just indicated, the minimum node in a tree does not have a left
child. Figure 19.4 shows an initial tree and the result of removing node 2. We
replace the node with the smallest node (3) in its right subtree and then
remove 3 from the right subtree. Note that in all cases removing a node does
not make the tree deeper.
1
Many alternatives do make the tree deeper; thus
these alternatives are poor options.
A node with two
children is replaced
by using the small-
est item in the right
subtree. Then
another node is
removed.
19.1.2
java implementation
In principle, the binary search tree is easy to implement. To keep the Java fea-
tures from clogging up the code, we introduce a few simplifications. First,
Figure 19.5 shows the
BinaryNode
class. In the new
BinaryNode
class, we make
everything package-visible. More typically,
BinaryNode
would be a nested
class. The
BinaryNode
class contains the usual list of data members (the item
and two links).
The
BinarySearchTree
class skeleton is shown in Figure 19.6. The only
data member is the reference to the root of the tree,
root
. If the tree is empty,
root
is
null
.
The public
BinarySearchTree
class methods have implementations that call
the hidden methods. The constructor, declared at line 21, merely sets
root
to
null
. The publicly visible methods are listed at lines 24-39.
The
root
references at the
root of the tree,
which is
null
if the
tree is empty.
The public class
functions call
hidden private
routines.
figure 19.4
Deletion of node 2
with two children:
(a) before and
(b) after
7
7
2
9
3
9
1
5
1
5
3
4
4
(a)
(b)
1. The deletion can, however, increase the average node depth if a shallow node is removed.
Search WWH ::
Custom Search