Section 6.3 Decision Trees
535
sorting
Decision trees can also model algorithms that sort a list of items by a sequence of comparisons between two items from the list. The internal nodes of such a decision tree
are labeled L3i 4:L3 j 4 to indicate a comparison of list item i to list item j. To simplify
our discussion, let’s assume that the list does not contain duplicate items. Then the
outcome of such a comparison is either L3i 4 < L3 j 4 or L3i 4 > L3 j 4 . If L3i 4 < L3 j 4,
the algorithm proceeds to the comparison indicated at the left child of this node; if
L3i 4 > L3 j 4, the algorithm proceeds to the right child. If no child exists, the algorithm terminates because the sorted order has been determined. The tree is a binary
tree, and the leaves represent the final outcomes, that is, the various sorted orders.
praCTiCe 26
a. Construct the binary search tree for the data of Example 34 entered in the order
12, 9, 14, 5, 10, 8, 2
b. What is the depth of the tree?
■
example 36
Figure 6.56 shows the decision tree for a sorting algorithm acting on a list of
three elements. This algorithm is not particularly astute because it ignores the
transitive property of < and therefore performs some unnecessary comparisons. The leaves of the tree indicate the various final outcomes, including two
cases (marked with an X ) that result from contradictory information. For example, one X results from the following inconsistent sequence of outcomes:
L314 < L32 4, L324 < L334, L31 4 > L334.
<
>
<
>
<
>
L[2] < L[3] < L[1]
L[2] < L[1] < L[3]
X
X
<
<
>
>
L[1]:L[2]
<
>
<
>
L[1]:L[3]
L[1]:L[3]
L[2]:L[3]
L[2]:L[3]
L[2]:L[3]
L[1]:L[3]
L[1] < L[3] < L[2]
L[1] < L[2] < L[3]
L[3] < L[1] < L[2]
L[3] < L[2] < L[1]
Figure 6.56
praCTiCe 27 Draw the decision tree that would result if the algorithm of Example 36 were modified to
eliminate unnecessary comparisons.
■