Introduction to Algorithms, Third Edition

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
k
i
; : : : ; k
j
, for some
1
i
j
n
.
In addition, a subtree that contains keys
k
i
; : : : ; k
j
must also have as its leaves the
dummy keys
d
i
1
; : : : ; d
j
.
Now we can state the optimal substructure: if an optimal binary search tree
T
has a subtree
T
0
containing keys
k
i
; : : : ; k
j
, then this subtree
T
0
must be optimal as

---

400
Chapter 15
Dynamic Programming
well for the subproblem with keys
k
i
; : : : ; k
j
and dummy keys
d
i
1
; : : : ; d
j
. The
usual cut-and-paste argument applies. If there were a subtree
T
00
whose expected
cost is lower than that of
T
0
, then we could cut
T
0
out of
T
and paste in
T
00
,
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 opti-
mal solution to the problem from optimal solutions to subproblems. Given keys
k
i
; : : : ; k
j
, one of these keys, say
k
r
(
i
r
j
), is the root of an optimal
subtree containing these keys. The left subtree of the root
k
r
contains the keys
k
i
; : : : ; k
r
1
(and dummy keys
d
i
1
; : : : ; d
r
1
), and the right subtree contains the
keys
k
r
C
1
; : : : ; k
j
(and dummy keys
d
r
; : : : ; d
j
). As long as we examine all candi-
date roots
k
r
, where
i
r
j
, and we determine all optimal binary search trees
containing
k
i
; : : : ; k
r
1
and those containing
k
r
C
1
; : : : ; k
j
, 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
k
i
; : : : ; k
j
, we select
k
i
as the root. By the above argument,
k
i
’s
left subtree contains the keys
k
i
; : : : ; k
i
1
. We 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
k
i
; : : : ; k
i
1
has no actual keys but
does contain the single dummy key
d
i
1
. Symmetrically, if we select
k
j
as the root,
then
k
j
’s right subtree contains the keys
k
j
C
1
; : : : ; k
j
; this right subtree contains
no actual keys, but it does contain the dummy key
d
j
.