Java Reference
In-Depth Information
figure 23.6
Recombination of
siblings after a
deleteMin
. In each
merge, the larger root
tree is made the left
child of the smaller
root tree: (a) the
resulting trees;
(b) after the first pass;
(c) after the first
merge of the second
pass; (d) after the
second merge of the
second pass
6
3
4
5
9
7
10
13
8
11
15
14
12
17
19
16
18
(a)
3
4
7
6
10
13
5
8
9
19
11
15
14
12
17
16
18
(b)
3
4
7
5
8
6
10
13
11
15
9
19
14
12
17
16
18
(c)
3
4610
13
7
5
8
11
15
9
19
16
18
14
12
17
(d)
next sibling. The third link is
prev
, which references the parent if the node is a
first child or to a left sibling otherwise.
The
findMin
routine is coded in Figure 23.9. The minimum is at the root,
so this routine is easily implemented. The
insert
routine, shown in
Figure 23.10, creates a one-node tree and merges it with the
root
to obtain a
new tree. As mentioned earlier in the section,
insert
returns a reference to the
newly allocated node. Note that we must handle the special case of an inser-
tion in an empty tree.
Search WWH ::
Custom Search