Section 6.3 Decision Trees
537
5. Consider a search algorithm that compares an item with the last element in a list, then the first element,
then the next-to-last element, then the second element, and so on. Draw the decision tree for searching a
six-element sorted list. What is the depth of the tree? Does it appear that this is an optimal algorithm in the
worst case?
6. Consider a search algorithm that compares an item with an element one-third of the way through the list;
based on that comparison, it then searches either the first one-third or the second two-thirds of the list.
Draw the decision tree for searching a nine-element sorted list. What is the depth of the tree? Does it appear that this is an optimal algorithm in the worst case?
7. a. Given the data
9, 5, 6, 2, 4, 7
construct the binary search tree. What is the depth of the tree?
b. Find the average number of comparisons done to search for an item that is known to be in the list
using binary tree search on the tree of part (a). (Hint: Find the number of comparisons for each of the
items.)
8. a. Given the data
g, d, r, s, b, q, c, m
construct the binary search tree. What is the depth of the tree?
b. Find the average number of comparisons done to search for an item that is known to be in the list
using binary tree search on the tree of part (a). (Hint: Find the number of comparisons for each of the
items.)
9. a. For a set of six data items, what is the minimum worst-case number of comparisons a search algorithm
must perform?
b. Given the set of data items 5a, d, g, i, k, s6, find an order in which to enter the data so that the corresponding binary search tree has the minimum depth.
10. a. For a set of nine data items, what is the minimum worst-case number of comparisons a search algorithm
must perform?
b. Given the set of data items 54, 7, 8, 10, 12, 15, 18, 19, 216, find an order in which to enter the data so
that the corresponding binary search tree has the minimum depth.
11. An inorder tree traversal of a binary search tree produces a listing of the tree nodes in alphabetical or
numerical order. Construct a binary search tree for “To be or not to be, that is the question,” and then do
an inorder traversal.
12. Construct a binary search tree for “In the high and far-off times the Elephant, O Best Beloved, had no
trunk,” and then do an inorder traversal. (See Exercise 11.)
13. Use the theorem on the lower bound for sorting to find lower bounds on the number of comparisons
required in the worst case to sort lists of the following sizes:
a. 4
b. 8
c. 16
14. Contrast the number of comparisons required for selection sort and merge sort in the worst case with the
lower bounds found in Exercise 13 (see Exercise 23 in Section 3.3). What are your conclusions?
Exercises 15–20 concern the problem of identifying a counterfeit coin (one that is two heavy or too light) from
a set of n coins. A balance scale is used to weigh a group of any number of coins from the set against a like
number of coins from the set. The outcome of such a comparison is that group A weighs less than, the same as,
or more than group B. A decision tree representing the sequence of comparisons done will thus be a ternary tree,
where an internal node can have three children.
537
5. Consider a search algorithm that compares an item with the last element in a list, then the first element,
then the next-to-last element, then the second element, and so on. Draw the decision tree for searching a
six-element sorted list. What is the depth of the tree? Does it appear that this is an optimal algorithm in the
worst case?
6. Consider a search algorithm that compares an item with an element one-third of the way through the list;
based on that comparison, it then searches either the first one-third or the second two-thirds of the list.
Draw the decision tree for searching a nine-element sorted list. What is the depth of the tree? Does it appear that this is an optimal algorithm in the worst case?
7. a. Given the data
9, 5, 6, 2, 4, 7
construct the binary search tree. What is the depth of the tree?
b. Find the average number of comparisons done to search for an item that is known to be in the list
using binary tree search on the tree of part (a). (Hint: Find the number of comparisons for each of the
items.)
8. a. Given the data
g, d, r, s, b, q, c, m
construct the binary search tree. What is the depth of the tree?
b. Find the average number of comparisons done to search for an item that is known to be in the list
using binary tree search on the tree of part (a). (Hint: Find the number of comparisons for each of the
items.)
9. a. For a set of six data items, what is the minimum worst-case number of comparisons a search algorithm
must perform?
b. Given the set of data items 5a, d, g, i, k, s6, find an order in which to enter the data so that the corresponding binary search tree has the minimum depth.
10. a. For a set of nine data items, what is the minimum worst-case number of comparisons a search algorithm
must perform?
b. Given the set of data items 54, 7, 8, 10, 12, 15, 18, 19, 216, find an order in which to enter the data so
that the corresponding binary search tree has the minimum depth.
11. An inorder tree traversal of a binary search tree produces a listing of the tree nodes in alphabetical or
numerical order. Construct a binary search tree for “To be or not to be, that is the question,” and then do
an inorder traversal.
12. Construct a binary search tree for “In the high and far-off times the Elephant, O Best Beloved, had no
trunk,” and then do an inorder traversal. (See Exercise 11.)
13. Use the theorem on the lower bound for sorting to find lower bounds on the number of comparisons
required in the worst case to sort lists of the following sizes:
a. 4
b. 8
c. 16
14. Contrast the number of comparisons required for selection sort and merge sort in the worst case with the
lower bounds found in Exercise 13 (see Exercise 23 in Section 3.3). What are your conclusions?
Exercises 15–20 concern the problem of identifying a counterfeit coin (one that is two heavy or too light) from
a set of n coins. A balance scale is used to weigh a group of any number of coins from the set against a like
number of coins from the set. The outcome of such a comparison is that group A weighs less than, the same as,
or more than group B. A decision tree representing the sequence of comparisons done will thus be a ternary tree,
where an internal node can have three children.