Java Reference
In-Depth Information
findMax
operation is similar, except that branching is to the right. Note that the
cost of all the operations is proportional to the number of nodes on the search
path. The cost tends to be logarithmic, but it can be linear in the worst case.
We establish this result later in the chapter.
The hardest operation is
remove
. Once we have found the node to be
removed, we need to consider several possibilities. The problem is that the
removal of a node may disconnect parts of the tree. If that happens, we must
carefully reattach the tree and maintain the binary search tree property. We
also want to avoid making the tree unnecessarily deep because the depth of
the tree affects the running time of the tree algorithms.
When we are designing a complex algorithm, solving the simplest case
first is often easiest, leaving the most complicated case until last. Thus, in
examining the various cases, we start with the easiest. If the node is a leaf,
its removal does not disconnect the tree, so we can delete it immediately. If
the node has only one child, we can remove the node after adjusting its par-
ent's child link to bypass the node. This is illustrated in Figure 19.3, with
the removal of node 5. Note that
removeMin
and
removeMax
are not complex
because the affected nodes are either leaves or have only one child. Note also
that the root is a special case because it does not have a parent. However,
The
findMin
opera-
tion is performed by
following left nodes
as long as there is a
left child. The
findMax
operation is
similar.
The
remove
opera-
tion is difficult
because nonleaf
nodes hold the tree
together and we do
not want to discon-
nect the tree.
If a node has one
child, it can be
removed by having
its parent bypass it.
The root is a special
case because it
does not have a
parent.
figure 19.2
Binary search trees
(a) before and
(b) after the insertion
of 6
7
7
2
9
2
9
1
5
1
5
3
3
6
(a)
(b)
figure 19.3
Deletion of node 5
with one child:
(a) before and
(b) after
7
7
2
9
2
9
1
5
1
3
3
(a)
(b)
Search WWH ::
Custom Search