Java Reference
In-Depth Information
6.
(a)
(b)
40
80
60
80
60
30
70
30
20
50
70
20
50
10
40
10
(c)
(d)
80
80
40
60
60
70
70
20
30
50
40
30
20
50
10
10
7.
(a)
85 is larger child of 30; 30 < 85, so move 85
30
85
60
70
80
20
50
10
40
0
1
2
345
6
7
8910
(b)
80 is larger child of vacated node; 30 < 80, so move 80
60
85
70
80
20
50
10
40
0
2
3
4
5
7
8
9
1
6
10
(c)
Reached leaf
85
80
60
70
20
50
10
40
0
1
2
345
6
7
8
9
10
(d)
Insert 30
85
80
60
70
30
20
50
10
40
0
1
2
3
4
5
6
7
8
9
10
8.
If a node at index
i
has children, they are at indices 2
i
and 2
i
+ 1. The node at
lastIndex/2
then has a child at
lastIndex
. Since this child is the last leaf, any nodes beyond the one at
lastIndex/2
cannot have children and so
must be leaves. Thus, the node at
lastIndex/2
must be the nonleaf closest to the end of the array.
Alternatively, examine some complete trees and notice that the desired nonleaf is the parent of the last child.
This child is at index
lastIndex
of the array representation, so its parent has index
lastIndex/2
.
