Section 6.3 Decision Trees
533
Therefore tree T 1 has depth ≥ :log n; + 1. Because the depth of the decision
tree gives the worst-case number of comparisons, we can state the following
theorem.
tHeorem on The lower BounD For searchinG
Any algorithm that solves the search problem for an n-element list by comparing
the target element x to the list items must do at least :log n; + 1 comparisons in
the worst case.
This theorem gives us a lower bound on the number of comparisons required
in the worst case for any algorithm that uses comparisons to solve the search problem. Since binary search does no more work than this required minimum amount,
binary search is an optimal algorithm in its worst-case behavior.
Binary Tree Search
The binary search algorithm requires that data already be sorted. Arbitrary data
can be organized into a structure called a binary search tree, which can then be
searched using a different algorithm called binary tree search. To build a binary
search tree, the first item of data is made the root of the tree. Successive items are
inserted by comparing them to existing nodes, beginning with the root. If the item
is less than a node, the next node tested is the left child; otherwise it is the right
child. When no child node exists, the new item becomes the child.
example 34
The data items
5, 8, 2, 12, 10, 14, 9
are to be organized into a binary search tree. Figure 6.54 shows the successive
stages of constructing the tree.
8
2
5
8
12
2
5
8
12
10
2
5
8
12
10
14
2
5
8
14
12
10
9
2
5
8
5
5
Figure 6.54