Section 6.3 Decision Trees
531
x = L3i 4: algorithm terminates, x has been found
x < L3i 4: algorithm proceeds to the left half of the list
x > L3i 4: algorithm proceeds to the right half of the list
We will follow the usual custom and not write the leaf that corresponds to the
“middle branch,” x = L3i 4 (see Exercise 21 for a discussion of the consequences of
this convention). If x < L3i 4, the next comparison the algorithm performs is found
at the left child of this node; if x > L3i 4, the algorithm’s next comparison is found
at the right child. If no child exists, the algorithm terminates because x is not in
the list. The tree we’ve described is a binary tree whose leaves represent all the
possible outcomes where x is not in the list. There are many more failure leaves
in binary search than in sequential search, because binary search indicates how x
fails to be in the list (e.g., x < L31 4 or L31 4 < x < L32 4).
example 33
Figure 6.53 shows the decision tree for the binary search algorithm acting on a
sorted list of eight elements.
The worst case, that is, the maximum number of comparisons, will again be
the depth of the tree, which is 4 in Figure 6.53. In Chapter 3 we solved a recurrence
relation to get the worst-case behavior for binary search where n is a power of 2
and found this to be 1 + log n (remember that we are using base 2 logarithms).
Note that 1 + log 8 = 4, so the decision tree agrees with our previous result. The
restriction of n to a power of 2 made the arithmetic of solving the recurrence relation simpler. If n is not a power of 2, then the depth of the tree is given by the
expression 1 + :log n; .
<
>
x > L[8]
x:L[8]
L[7] < x < L[8]
<
>
x:L[6]
<
>
<
>
x:L[7]
x:L[5]
L[6] < x < L[7]
L[4] < x < L[5]
<
<
>
>
x:L[2]
x:L[4]
<
>
<
>
x:L[3]
x:L[1]
L[2] < x < L[3]
x < L[1]
L[1] < x < L[2]
L[3] < x < L[4]
L[5] < x < L[6]
Figure 6.53