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. 
So the right way to search time in T in 
terms of the weighted search time in T1 
and T2, it's going to be convenient to 
bucket the items into three categories. 
Those that are in the left subtree T1, 
i.e. 
one through r minus one, those in the 
right subtree T2, r plus one through n, 
and then of course left over is the root 
r itself. 
So let's just break down the sum into its 
three constituent parts. 
So the sum and corresponding to the root 
r contributes the frequency of r times 
the search time for r, namely one because 
it's the root. 
And then we have our sum, over just the 
items up to r - 1 of their frequencies 
times their search times and similarly 
those r plus one up to n, their 
frequencies times their search times nT. 
So for the next step, let's observe it's 
very easy to connect search times in T 
with search times in the subtrees T1 and 
T2. 
Suppose you were, you, example, you were 
searching for some key in T that was in 
T1. 
So some key that was less than r. 
What happens when you search for this 
item in the tree T? 
Well, first you visit r, 
it's not r, it's less than r, so you go 
left, and then you just search as 
appropriately through the search tree T1. 
That is, the search time in the big tree 
T is simply the search time in the 
subtree T1 + 1, 1 because you had to 
visit the root r before you made it in to 
the subtree T1. 
So that is, for any object i other than 
the root, we can write its search time in 
the big tree T as simply one plus the 
search time in the appropriate subtree. 
So now, let me expand in groups and terms 
just to clean up this mess. 
So now that the dust has settled, let's 
inspect each of these three sums. 
We actually have a quite simple 
understanding of each of them. 
So, the first sum is just the sum of the 
Pi. So for example, in the conical case 
where we're dealing with actual 
probabilities, this is just one. 
The point is, whatever the Pis are, this 
first sum is just a constant, meaning 
it's independent of the tree T, with 
which we started. 
What's the second sum? 
So it's the sum of the objects from one 
to r minus one, the frequency of ithe 
times search4I time for i in the 
searchtree T1. 
Well, we have a much better, shorter 
nickname for that sum. 
It's the weighted search time of the 
search tree T1, for the objects that 
contains one through r minus one. 
Similarly this last sum, sum from i over 
r plus one to n of the frequency of i 
times the search time in T2, that's just 
the weighted search time in the search 
tree T2. 
So, we did this computation with the 
purportedly optimal search tree capital T 
in mind. 
But if you think about it, you look at 
this algebra. 
This, it applies to any search tree you 
like. 
For any search tree, the weighted search 
cost can be expressed as the sum of the 
Pis plus the weighted search cost of the 
left subtree of the root plus the 
weighted search cost of the right subtree 
of the root. 
In particular, that's true for this tree 
T star we got by cutting and pasting the 
better left subtree T star one and for 
T1. 
So applying this reasoning to T star, we 
can right its weighted search cost as the 
sum from micro one to n of all the Pis 
plus the weighted search cost of its left 
subtree of its root, which remember by 
construction is T star one, 
and then it has the same right sub tree 
as the tree T does, namely T2. 
And the point of all this algebra is that 
we now see in a very simple way what are 
the ramifications of cutting and pasting 
in this better left subtree, we get a 
better tree for the original key set 
contradicting the purported optimality of 
the tree T that we started with. 
That completes the proof of the optimal 
substructure lemma for optimal binary 
search trees.