Next we're going to talk about binary 
search trees. 
And we said that binary trees are a 
classic structure in combinatorics. 
And they are enumerated by the Catalan 
numbers. 
But there also a classic structure in 
Computer Science. 
It's a fundamental data structure that's 
used for all sorts of things. 
But one of the most important is, for 
implementing symbol tables where we have 
lots of information. 
Each piece of information is associated 
with a key and we want to insert things 
into the symbol table, and we want to 
retrieve them by key. 
You can find much more inflammation, 
information, about symbol tables in our 
algorithms book or on the book site 
associated with the book. 
But I'll describe what minory trees, 
minory search tree's are because one of 
the, that's one of the most important 
algorthms in computer science and it uses 
a classical data structure, the binary 
tree. 
So, we work with nodes. 
and those are the things we can write 
programs to manipulate. 
Each node has a key, and the keys have 
values that are so called comparable 
values. 
That, that means is, it means, means that 
we will take two of them, and know 
whether one's less, equal or greater than 
the other, that's all. 
now usually in the implementations we do 
nowadays we assume the keys to be all 
distinct. 
we can do things with equal keys but both 
for the analysis and for the 
implementation, it's better to use 
distinct keys. 
now in the binary tree representation, 
nodes have 2 sub-trees, left sub-trees 
and right sub-trees, which are empty or 
might be whole trees. 
And if there's keys in the left sub-tree, 
all those keys are smaller than V. 
And if there's keys in the right 
sub-tree, they're all larger than V. 
that's what a binary search tree is. 
Now [COUGH] in Java and again without 
going into detail of Java code for those 
of you who don't know it, it might take 
some, you might have to read the 
algorithms book a bit to really follow 
all of this, and those of you who do know 
it, but either way it's very. 
Had, it's elegant it's simple it's small 
amount of code, to implement nodes and 
binary trees in java. 
so we build a data type, that, holds the 
associated information, so that we can 
manipulate it and keep it together. 
Programs that manipulate, and you'll see 
what those look like in just a minute. 
and the only operation that we need to 
perform is to be able to create a new 
node, with a given key and value, and 
that's what this code does. 
It defines that data type. 
That holds a, node's got four fields, 
it's got a key and a value, and it's got 
a reference to the two subtrees. 
The left subtree has smaller keys and the 
right subtree has larger keys, and that's 
how we represent it. 
and for programming language aficionados, 
we usually use generic types for keys, 
which means that we can hold any type of 
data with that. 
And again, you can read about these 
details in the algorithm. 
[INAUDIBLE] so that's what the computer 
representation of a binary search tree 
looks like. 
we have nodes that have keys and values 
and then each node points to another node 
which is another [INAUDIBLE], another 
binary search tree, the one on the left 
with smaller keys and the one on the 
right with larger keys. 
Keys. 
And it's a recursive structure, and 
eventually we get to places where the 
left sub tree is empty or the right sub 
tree is empty, in which case those links 
would be null. 
So that's the structure, and now what 
we're going to, what I'm going to 
describe is programs for manipulating 
that structure, for inserting your keys 
and for searching [UNKNOWN] for keys. 
the easiest is search unless look at the 
search implementation. 
This is a recursive program that operates 
on that recursive structure. 
there's some programming language jargon 
at the top, that has to do with the 
generics in otherwise let's look at what 
it does. 
so this is a data type for manipulating 
binary trees. 
What is a binary tree its a root node, so 
that is what the first line code says. 
Then theres the definition of nodes, and 
then this is the method for retrieving 
the value associated with a given key. 
I'll do it line by line. 
We have a variable X that we set to be 
the root of the tree, as long as that 
node acts as not-null. 
Then we got to compare the key at X. 
That's X dot key. 
with the key we were given to search for. 
that comparison can have three outcomes. 
Either less than zero, greater than zero 
or equal zero. 
If it's less the key we're looking for is 
less than x's key, then we're go to the 
left. 
Go to the left is x=x.left. 
That's recursively move down the tree to 
the left sub tree that contains smaller 
nodes than x's, and we have a smaller key 
so that's where we want to go. 
If it's greater, we go to the right, and 
if it's equal, we're done, we return x's 
value. 
that's an implementation of search for 
binary search trees, so in this example 
you can see to search, say for M, we 
start at S. 
M is less than S, so we go left. 
It's greater than E so we go right and 
then we're successful to see M. 
If we're searching for something that's 
not in the tree, say we're searching for 
Q we go left again, Q's less than S, it's 
bigger than E we go right, it's bigger 
than M we go right, but now we're on a 
null link and essentially that says that 
If Q were in the tree, it would have to 
be here. 
But there's nothing in the tree here so 
it's not here. 
And in that case down at the last 
statement in the implementation we 
return. 
So it's a very simply expressed 
algorithm. 
this is in a modern programming language. 
It's also easy to program these in even 
assembly or machine language that people 
my age have done that even. 
in any programming environment now you 
can implement binary trees pretty easily 
with a small amount of code. 
and so it's unsucessful. 
Now what about insert. 
so this is the code, for insert out of 
the algorithm script. 
and essentially what it does is, when we 
Do an unsuccessful search, and we come to 
a null link. 
So, say to insert q, we get to the same 
place. 
But, then what it does is create a new 
node for q. 
That's the first line. 
x equals null return new node, and then 
attaches it there. 
In the recursive calls rather that x 
equals x dot left, we say x dot left 
equals recursive calls and that is what 
does the attachment of the new note this 
is a little bit tricky but it is a very 
concise recursive code. 
And then now we've implemented both, 
insert and search. 
And so that's an important algorithm, 
that we want to analyze the performance 
of this algorithm. 
It's actually got good performance and 
it's widely used. 
Now the key fact that we have to worry 
about in doing this analysis, is that the 
shape of a binary search tree depends on 
the order of insertion of the keys. 
so the best thing that can happen would 
be the keys are inserted in such a way 
that the tree is perfectly balanced. 
that's like the tree that's described 
merge sort, that we looked at in the 
first lecture. 
the height of that tree is log N. 
Uh,and in that case all searches are 
going to be guaranteed to take less than 
log n, key comparisons say. 
a typical case, is more like the one that 
I showed for the example, where there's 
some nodes on either side on most, for 
most sub trees. 
But it's not perfectly balanced. 
That's the one, that we want to analyze. 
And we'll get to that in a minute. 
and it's also the worst case. 
so the keys come in, in order. 
if the keys come in, in order it's not 
very good performance. 
because their average cross for searching 
for Q in the tree is going to be about 
N/2, and that's going to be a performance 
problem. 
If you think of a huge symbol table. 
And, nowadays most of them are huge. 
With say a million or a billion keys. 
This one over here is going to get to any 
key with twenty or thirty searches. 
This one could require a half million or 
a half Billion. 
It's a very important performance 
difference. 
It's going to make the difference between 
being able to address the problem and not 
address it at all and we're to see 
average fall in between. 
that's where the analysis of algorithms 
comes in. 
so it's reasonable to analyze binary 
search tree structures under the 
assumption that the keys are inserted in 
random order. 
now that's a, a starting point. 
certainly you've got situations where 
clients do not insert em in random order. 
And it's not like Quick Sort where we can 
randomize because the insertions might 
come from some completely external force. 
And we don't, we don't have any source. 
And we don't have any way to rearrange 
their orders. 
So it's not quite as it's not a 
randomized algorithm that we can 
guarantee performance probabilistically 
the way we can with quick sort but still 
it's a reasonable model that actually is 
it can be validated in lots of practical 
situations. 
So it's a good starting point for 
analysis of a tree algorithm. 
when you, when you do that, if you have, 
this is BST built from, EDTs inserted in 
random order. 
you can see that the trees you get, 
they're different but unlike what we saw 
for random binary trees, would be tree 
[INAUDIBLE] likely. 
these are kind of balanced. 
well sometimes you get a little 
imbalance. 
so that's a typical random binary search 
trees. 
And again our goal is to characterize 
this analytically and explain why this is 
different from what we get with random 
binary trees. 
so we're going to analyze them both. 
now the key thing is that when you're 
analyzing binary search trees, the shape 
of the tree is a property of 
permutations, not trees. 
Our input model is a random permutation. 
that's N things in arbitrary order, 
N-factorial possibilities. 
Binary search tree is where we're talking 
about a random tree we're talking about 1 
out of a [UNKNOWN] number of 
possibilities, which is way less. 
So, that's really important to remember. 
We're talking about propertation of, 
property of permutations, not tree. 
So you could have, and this gives all 
possibilities, for 1,2,3, and 4 nodes. 
And, the one that's blown up, is just one 
illustration, that shows, that. 
2 different permutations can lead to the 
same tree shape. 
So this case 1 comes in, tree goes to the 
right and then 2 goes to the left of tree 
and then 4 goes to the right of the tree. 
But 4 and 2 could come in the other order 
and you'd still get the same tree. 
And again, on the other hand, the tree 
where the keys come in all in order, 
1-2-3-4, that's the only permutation that 
gives that shape. 
The ones that are more balanced, there's 
more permutations that give rise to them. 
Now that's an important observation to 
try to understand why we get more balance 
with binary search trees than with binary 
trees. 
so that's an observation and we're going 
to validate that. 
now it, it's int, in order to get it done 
we really want to think about the 
question if you have a tree shape, how 
many permutations are going to lead to 
that tree shape. 
So that means how many, if you would take 
a permutation and insert it into an 
initially empty binary search tree, how 
many are going to give that shape? Well, 
we sort of just did that. 
The answer to that is there's two 
different ones. 
The two has to be first. 
That's the one at the root. 
Then either you could either have the one 
go to the left, and the three go to the 
right. 
Or the three go to the left, and the one 
go to the right. 
and those are the only ones. 
Let's look at a bigger tree, how many 
permutations mapped to that one? Well 
that's a more complicated problem. 
so well one thing you know is that the 
root has to be 4. 
So you got, at least the first element 
permutation has to be 4. 
And then you have to have 1, 2, and 3 on 
the left. 
And 5 and 6 on the right. 
The 5 and 6 on the right, ther'es only 
one order that gives, that shape. 
Five has to go first and then six. 
And on the left you have the two 
possibilities. 
Either the two, one, three. 
But the other thing is that there's, Two 
possibilities, with the 1, 2, 3 and 5 and 
6. 
They can be intermixed any number of 
ways. 
So, the answer is 20. 
you've got 5 keys that's left of the 
stuff that goes on the left and the right 
and you can intermix them, 5 choose two 
ways and then you've got the two 
possibilities for the left and the 1 
possibility for the right. 
and those are the 20 permutations that 
lead to that tree shape. 
and you can check that, validate that and 
if you don't quite believe or understand 
that math. 
so that's a bigger example. 
And then from that it's not hard to come 
to the general case, how many 
permutations map to a general A binary 
tree like that. 
Well, there's some number of nodes on the 
left sub tree. 
so the left sub tree is t sub l and the 
size of t sub l. 
Then the root has to be that number plus 
one. 
and then right sub tree has it, has its 
number of nodes. 
And then by the same argument that we 
just gave, if you define P sub 2 to be 
the number of permutations that map 
toward tree t. 
Then you have a recursive formula. 
P sub t = t sub L + t sub R choose t sub 
L, there's a number of different ways to 
intermix them. 
The smaller elements and the larger 
elements, and then for whatever all the 
ways of intermixing them, you can still 
put them in any one of the P sub P sub L 
orders or any one of the P sub P sub R 
orders. 
You have to multiply all those together 
to get the number of permutations that 
map to a general binary tree. 
so that's an interesting observation, and 
actually you can apply that formula 
recursively and just read off from the 
tree the number of shapes that map to it. 
But we're going to use that exact 
formula, a little bit later. 
so, and the other thing to observe from 
this formula is, that that binomial 
coefficient is going to be much much 
larger when the, two sub-trees are nearly 
balanced. 
that's the Gaussian distribution, so it's 
much larger at the middle. 
And we verified that analytically. 
if it's within square root of the, it's 
going to be much much larger. 
And, 
if T sub L is small, or T sub R is small, 
it's going to be exponentially smaller. 
So the, a number of permutations that map 
to an unbalanced tree is way, way smaller 
than the number that mapped to a balance 
tree, and that's why, that's what we 
observe in practice. 
so in summary so far. 
I describe two different binary tree 
models that, they're both fundamental, 
binary, random binary trees from the 
Catalan is, classic [UNKNOWN] structure. 
Binary search degrees is a classic, 
Computer Science strucuture. 
in the one model, in the BST model, that 
we used in, certain type of 
implentations. 
balanced shapes are much more likely. 
And actually, one way to think of it, is 
what's the probability that the root is 
of length k for a given k from 1 to n. 
Well in the BST model, it's built from a 
random permutation. 
So, in it's the first element in the 
permutation that goes at the root so the 
probability that any particular value is 
at the root is just 1/n. 
It's the same for all. 
It doesn't seem like it balances, but if 
you compare it with and so anyway, that's 
what the balances is, and in the 2nd one 
will compare that probability in what you 
get for the other case. 
so the [UNKNOWN] model, on the other 
hand, each tree shape is equally likely. 
and, and this is the probability that the 
root is of rank k in a random binary 
tree. 
you can have any tree on the left and any 
tree on the right out of all possible 
trees. 
that's called a Catalan distribution. 
and that gives rise to these much more 
unbalanced trees. 
2 fundamentally different models. 
I don't want to emphasize that because we 
go into the analysis soon we get into the 
math without the picture it's easy to 
lose track of the fact that we're talking 
about something that's totally, totally 
different. 
In fact, here's a plot of that Catalan 
distribution. 
that the root is of rank k, in a randomly 
binary, chosen binary true of n nodes. 
And again, this is normalized, the way 
that we usually do these distributional 
plots, so that we can see how it 
converges to a curve, and look at the 
curve. 
the most of the weight is off on the 
edges, extremely close to the edges in 
fact. 
So as N gets larger, most of the 
probabilitiy that the root is a rank of 
N/2 becomes exponentially small, and the 
probability that the root is the smallest 
or the largest actually is a quarter. 
So the, it's actually a pretty good 
chance that it's going to be unbalanced. 
and just, by the way there's no magic in 
plotting a distribution like this and 
people who are comfortable with 
programming, I encourage you to go ahead 
and. 
Try to develop plots like that. 
You can it's easy to write inefficient 
programs but if you think about it And 
this one isn't even all that efficient, 
but anyway this is the program that I use 
to produce that pot. 
so the prob, as I mentioned, the 
probability that at least one of the two 
sub-tress is empty is about a half. 
So that's why it's going to be 
unbalanced. 
it's like flipping a coin and, and 
putting an empty or putting a random one. 
It's, it's a going to lead to much, much 
different shape than we have for the 
other case. 
Now again just to full disclosure of the 
code that I'm using to make these 
pictures for people that are comfortable 
with programming, the code that I use to 
generate random binary trees and it's all 
very similar to the code that I talked 
about for binary search trees. 
The only difference is that I add 
coordinates to get the height and the 
width, and it's the little calculation in 
terms of where to place nodes and I used 
our programming model from the 
algorithm's website to do the drawings. 
But what I want to talk about now is the 
generate method. 
that's supposed to generate a new tree at 
a certain depth. 
And what that node does is basically it's 
a recursive program that computes the 
internal length of the root according to 
the appropriate probability distribution. 
and then recursively generates trees on 
the left and on the right. 
so and in this case to make the trees 
look good, I actually included the 
invisible external nodes in the rank 
field. 
and the point of this is to show there 
are a lot of similarities, and. 
I use this same curve to generate both 
kinds of trees. 
the only difference is, for random BST I 
uniformly choose the value of that rank. 
And for a random binary tree, I went to 
that Catalan distribution. 
to use it. 
So with a relatively small amount of code 
I've been generating these tree diagrams. 
and then again full disclosure and I'm 
not going to go through that. 
This is the code using our standard 
drawing model from the Algorithms book 
site, that scales and draws the binary 
tree as I talked about a few minutes ago. 
and for those of you who enjoy 
programming, it's a, it's a interesting 
exercise, to imlement the centered 
bi-level method that did for 
I already ran the Catalan trees. 
It's a draw general trees, and forests, 
and other things. 
Each one of those tasks, is intriguing 
programming exercise for, for people who 
enjoy programming. 
So that's a introduction to binary search 
trees and next we'll get into the 
analysis.