Section 6.2 Trees and Their Representations
527
a. The minimum number of data values to insert into a B-tree of order 5 to force it to have two levels is 5.
Find the minimum number of data values required to force the tree to have three levels.
b. Prove that when a B-tree of order 5 has the minimum number of data values to force it to have n levels,
n ≥ 2, the bottom level contains 2(3
n−2
) nodes.
c. Find (and justify) a general expression for the minimum number of data values required to force a
B-tree of order 5 to have n levels. aHint: 3
0
+ 3
1
+ c + 3
n−2
= a
3
n
− 3
6
b.b
In Exercises 55 and 56, two trees are isomorphic if there is a bijection f: N 1 S N 2 , where f maps the root of
one tree to the root of the other and where f (y) is a child of f (x) in the second tree when y is a child of x in the
first tree. Thus the two trees shown are isomorphic graphs but not isomorphic trees (in part (a) the root has two
children and in part (b) it does not). These are the only two nonisomorphic trees with three nodes.
r
r
(b)
(a)
55. Draw all the nonisomorphic trees with four nodes.
56. Draw all the nonisomorphic trees with five nodes.
57. One of the most efficient sorting algorithms is HeapSort, which sorts an array of values into increasing
order. To understand how the HeapSort algorithm works, it is best to imagine that the array elements are
stored in level order as the nodes of a binary tree. Thus the values in a 7-element array that is indexed from
0 through 6 would be stored in a binary tree with element 0 at the root, elements 1 and 2 at depth 1, and
so on.
1
3
4
5
2
6
0
A heap is a binary tree in which the value at every node is greater than the value at its two child nodes.
HeapSort is a two-phase process. The first phase is to reorganize the tree elements into a heap (more on
this later), and the second is to sort the heap. The key idea is that in a heap, the largest element is the root of
the tree; its proper place in the sorted array is at the end of the unsorted section of the array (at the lowest,
rightmost tree element not yet in its sorted position). The tree root gets thrown to the last unsorted position, and the element that formerly occupied that position must be inserted back into the unsorted section
in such a way as to preserve the heap property. Consider the following binary tree, which is a heap—each
node value is larger than the values at the two child nodes.
1, 2, 3, 4
1, 2
1, 2
4, 5
4, 5
3
3, 6
7, 8
527
a. The minimum number of data values to insert into a B-tree of order 5 to force it to have two levels is 5.
Find the minimum number of data values required to force the tree to have three levels.
b. Prove that when a B-tree of order 5 has the minimum number of data values to force it to have n levels,
n ≥ 2, the bottom level contains 2(3
n−2
) nodes.
c. Find (and justify) a general expression for the minimum number of data values required to force a
B-tree of order 5 to have n levels. aHint: 3
0
+ 3
1
+ c + 3
n−2
= a
3
n
− 3
6
b.b
In Exercises 55 and 56, two trees are isomorphic if there is a bijection f: N 1 S N 2 , where f maps the root of
one tree to the root of the other and where f (y) is a child of f (x) in the second tree when y is a child of x in the
first tree. Thus the two trees shown are isomorphic graphs but not isomorphic trees (in part (a) the root has two
children and in part (b) it does not). These are the only two nonisomorphic trees with three nodes.
r
r
(b)
(a)
55. Draw all the nonisomorphic trees with four nodes.
56. Draw all the nonisomorphic trees with five nodes.
57. One of the most efficient sorting algorithms is HeapSort, which sorts an array of values into increasing
order. To understand how the HeapSort algorithm works, it is best to imagine that the array elements are
stored in level order as the nodes of a binary tree. Thus the values in a 7-element array that is indexed from
0 through 6 would be stored in a binary tree with element 0 at the root, elements 1 and 2 at depth 1, and
so on.
1
3
4
5
2
6
0
A heap is a binary tree in which the value at every node is greater than the value at its two child nodes.
HeapSort is a two-phase process. The first phase is to reorganize the tree elements into a heap (more on
this later), and the second is to sort the heap. The key idea is that in a heap, the largest element is the root of
the tree; its proper place in the sorted array is at the end of the unsorted section of the array (at the lowest,
rightmost tree element not yet in its sorted position). The tree root gets thrown to the last unsorted position, and the element that formerly occupied that position must be inserted back into the unsorted section
in such a way as to preserve the heap property. Consider the following binary tree, which is a heap—each
node value is larger than the values at the two child nodes.
1, 2, 3, 4
1, 2
1, 2
4, 5
4, 5
3
3, 6
7, 8