So let's take any old optimal binary search tree for keys one through n with

frequencies P1 through Pn. The thing we're trying to prove asserts

that the left subtree T1 should be optimal for its keys, one through r minus

one, and the right subtree T2 should be optimal for its keys, r plus one through

n. So we're going to proceed by

contradiction, we're going to assume that's not true.

What would that mean? That means for one of these two

subproblems, either one through R - 1 or R + 1 through n, there's an binary search

tree with even smaller weighted search cost, search time, then T1 or T2

respectively. The two cases are totally the same

whether. In our contradiction, we assume T1 is not

optimal or the T2 is not optimal. I'm just going to prove it in the case

the T1 is not optimal. So if T1 is not optimal, there's gotta be

a search tree on its keys, one through r - 1 which is better.

Call that purportedly better solution T star one.

Now as usual, the thing which we're going to try to contradict to get the final

proof is we're going to exhibit a search tree on all of the keys, one through n

which is even better than T. The T was supposed to be optimal, so that

would be a contradiction. So how do we get our superior search tree

for all of the keys? Well, we're just going to take T and

we're going to do cut and paste. We're going to do surgery on the tree T,

ripping out it's left subtree T1 and pasting in this subtree T star one.

Call the resulting tree T star. So, to complete the contradiction and

therefore the proof of the optimal substructure lemma, all we have to show

is that the weighted search cost of T star is strictly less than that of T,

that would contradict the purported optimality of T.

So that's precisely what I'll show you on this next slide and it's going to be

evident if we do a suitable calculation. Here it is.

So let's begin just by expanding the weighted search time of our original

tree, capital T, the purportedly optimal one.

Let's expand its definition. So you have one sum n for each of the

items i and the weight we give to a given item is just its frequency p sub i.

And we multiply that by the search time of for i n T So let me now pause to tell

you the point of this calculation we're about to do.

So we start with the weighted search time in T,

and that's, of course expressed in terms of search times in this tree T.

What I want to show next is that can equally be, be well expressed in terms of

search times in the subtrees T1 and T2. That is, there's a simple formula to

compute the search time in T if I told you the search times in T1 and T2.

That's what's going to allow us to easily analyze the ramifications of the cut and

paste and to notice that in cutting and pasting in a better tree for the

subproblem, we actually get a better tree for the original problem.