Optimal Binary Search Trees
| node | depth | probability | contribution |
|---|---|---|---|
|
|
|||
| k1 | 1 | 0.15 | 0.30 |
| k2 | 0 | 0.10 | 0.10 |
| k3 | 2 | 0.05 | 0.15 |
| k4 | 1 | 0.10 | 0.20 |
| k5 | 2 | 0.20 | 0.60 |
| d0 | 2 | 0.05 | 0.15 |
| d1 | 2 | 0.10 | 0.30 |
| d2 | 3 | 0.05 | 0.20 |
| d3 | 3 | 0.05 | 0.20 |
| d4 | 3 | 0.05 | 0.20 |
| < d5 | 3 | 0.10 | 0.40 |
|
|
|||
| Total |
2.80 |
||
For a given set of probabilities, our goal is to construct a binary search tree whose expected search cost is smallest. We call such a tree an optimal binary search tree. Figure 15.7(b) shows an optimal binary search tree for the probabilities given in the figure caption; its expected cost is 2.75. This example shows that an optimal binary search tree is not necessarily a tree whose overall height is smallest. Nor can we necessarily construct an optimal binary search tree by always putting the key with the greatest probability at the root. Here, key k5 has the greatest search probability of any key, yet the root of the optimal binary search tree shown is k2. (The lowest expected cost of any binary search tree with k5 at the root is 2.85.)
As with matrix-chain multiplication, exhaustive checking of all possibilities fails to yield an efficient algorithm. We can label the nodes of any n-node binary tree with the keys k1, k2, ..., kn to construct a binary search tree, and then add in the dummy keys as leaves.
Step 1: The structure of an optimal binary search tree
To characterize the optimal substructure of optimal binary search trees, we start with an observation about subtrees. Consider any subtree of a binary search tree. It must contain keys in a contiguous range ki, ..., kj, for some 1 ≤ i ≤ j ≤ n. In addition, a subtree that contains keys ki, ..., kj must also have as its leaves the dummy keys di-1, ..., dj.
Now we can state the optimal substructure: if an optimal binary search tree T has a subtree T′ containing keys ki, ..., kj, then this subtree T′ must be optimal as well for the subproblem with keys ki, ..., kj and dummy keys di-1, ..., dj. The usual cut-and-paste argument applies. If there were a subtree T" whose expected cost is lower than that of T′, then we could cut T′ out of T and paste in T", resulting in a binary search tree of lower expected cost than T, thus contradicting the optimality of T.
We need to use the optimal substructure to show that we can construct an optimal solution to the problem from optimal solutions to subproblems. Given keys ki, ..., kj, one of these keys, say kr (i ≤ r ≤ j), will be the root of an optimal subtree containing these keys. The left subtree of the root kr will contain the keys ki, ..., kr-1 (and dummy keys di-1, ..., dr-1), and the right subtree will contain the keys kr 1, ..., kj (and dummy keys dr, ..., dj). As long as we examine all candidate roots kr, where i ≤ r ≤ j, and we determine all optimal binary search trees containing ki, ..., kr-1 and those containing kr 1, ..., kj, we are guaranteed that we will find an optimal binary search tree.
There is one detail worth noting about "empty" subtrees. Suppose that in a subtree with keys ki, ..., kj, we select ki as the root. By the above argument, ki's left subtree contains the keys ki, ..., ki-1. It is natural to interpret this sequence as containing no keys. Bear in mind, however, that subtrees also contain dummy keys. We adopt the convention that a subtree containing keys ki, ..., ki-1 has no actual keys but does contain the single dummy key di-1. Symmetrically, if we select kj as the root, then kj's right subtree contains the keys kj 1, ..., kj; this right subtree contains no actual keys, but it does contain the dummy key dj.