Today, we're going to talk about trees. 
this is the first, second half of the 
course. 
This is the first of, of a series of 
lectures on applications. 
just a little bit in the way of 
orientation before we begin. 
for the first half of the class the first 
thing we do is introduce analysis of 
algorithms. 
but then, we spent, have spent the rest 
of the time surveying the basic methods 
that we need in terms of mathematics, in 
order to do scientific studies about the 
perfomance of algorithms. 
And then, we finished off last time by 
introducing analystic combinatorics. 
So, this is all about mathematics and 
about technique. 
now we're going to and now we're going to 
switch to the second half of the class. 
We're going to switch to applications. 
And we're going to talk about some basic 
classic combinatorial classes with lots 
of applications. 
And we're going to look at techniques 
from analytical combinatorics that we use 
to study them, including applications to 
the analysis of algorithms. 
and this will bring us to really basic 
common attoric class with all kinds of 
applications, trees, permeations, strings 
and tries, words and mappings. 
we'll be using labeled and unlabeled 
classes alternating with ordinary 
generating functions and exponential 
generating functions really applying all 
of the mathematical techniques that we 
learned in the first half of the class. 
So today we're going to begin with trees. 
And we'll start off by talking about the 
basic definition of trees and forests. 
To begin I'll review what we've talked 
about in terms of binary trees by 
contrast with the general trees that 
we're going to talk about today. 
recall that a binary tree is an external 
node or an internal node in two binary 
trees where the order of the internal 
node is significant. 
so at the top is a root and in this case, 
that root has two binary trees or two 
[COUGH] internal nodes as its children. 
and then, down at the bottom we have some 
nodes called leaves that have both of 
their children are external. 
the external nodes are signified with 
little boxes and the internal nodes are 
signified with circles. 
we talked about binary tree we've talked 
about those before. 
so now, we refer to the level or the 
depth of a node in a tree. 
starting with a root at depth zero. 
the children of the root at depth one and 
so on. 
and the deepest node in the tree that's 
what we'll call the height of the tree. 
and we'll look at other parameters of 
trees later on. 
now remember one of the first problems 
that we looked at in the last couple of 
lectures is how many binary, binary trees 
are there within nodes. 
And that's the [UNKNOWN] numbers. 
and we did a derivation with the symbolic 
method that I'll just rush through 
because we've done it so many times, but 
just to get back on the notation. so we 
have a generating function which is the 
sum over all objects is either the size 
of that object which collects together 
objects by their size. 
we have atoms that are internal nodes and 
external nodes. 
And then depending on how you set the 
size of those atoms that's what we're 
going to count. 
And this case, we're counting internal 
nodes. 
And then, we have a combinatorial 
construction that comes as, as a 
mathematical representation of our 
explicit definition of what we mean by a 
binary tree. 
And then our basic transfer theorem 
translates that construction immediately 
into an equation on the generating 
function which then we can solve and get 
asymptotic estimates of the coefficients. 
so that's just a quick review of the 
symbolic method for binary trees just to 
set the context for different problems 
that we're going to do in this lecture. 
so now, in general, the mathematical, 
classical mathematical concept of the 
tree is in terms of forest. So, forest is 
a set of trees and the tree is a forest 
with a root added the top. 
and there's actually just from this quick 
observation the generating function that 
enumerates for us is just one of the 
trees, or the generative function that 
enumerates trees is just Z times the 
generating function that enumerates for 
us corresponding to adding the root. 
so this is a recursive definition but 
these are recursive structures. 
A forest is a sequence of disjoined 
trees. 
A tree is a node called a root. 
It should say forest is emptier, 
instead of just disjoined trees. 
Tree is a node called a root connected to 
the roots of trees in a forest. 
And so now a root can have any number of 
children including zero in the leaf nodes 
of the nodes with zero children. 
so [COUGH] the, and then the level is the 
same as before. 
we start with the root at depth zero, the 
children of the root at depth one and so 
forth. 
and the height is again the deepest node 
in the tree. 
in contrast to binary trees, we don't 
have external nodes in, in general trees. 
so that's now a question comes up 
immediately is enumeration. How many 
forests are there within nodes? so this, 
these are all the forests with 1 2, 3 and 
4 nodes and immediately right away, you 
can recognize that the catalan numbers 
are rising yet again. 
so there's 5/4 with 3 nodes just 3 
individual nodes or tree size 2 and 
another node in either order. 
or the node, root node connected to 2 
children or the straight line, 
which is a root connected to a child, 
connected to a child. 
Notice the order of significance, the 
forest is a sequence of trees and that's 
consistent with computer applications 
where we have to represent the thing in a 
computer some way and we pick a sequence 
usually. 
so anyway, the catalan numbers are here. 
And, of course a tree is a root connected 
to a forest. 
So, if you attach roots to all of those, 
you get all possible trees. 
And it's the same numbers with one, 
shifted over by one. 
So let's look at the analytic 
combinatorics for deriving the catalan 
generated function for trees and forests. 
so and we just follow through the basic 
steps that we've outlined many times 
before. 
and we're going to be doing this a lot 
but a small mistake leads to completely 
the wrong answer, so it's good, good to 
be careful. 
so F is the class of all forests and the 
size is going to be the number of nodes 
where our atoms are. 
Now, 
there's just one kind of node and its got 
generating function Z. 
And G is the class of all trees on the 
same atom and again the same size 
function. 
So, those are two combinatorial classes. 
and now, we can use our definitions of 
those classes to develop constructions 
directly from the definitions. 
what did we say? we said, a forest is a 
sequence of trees and a tree is a root 
node in a forest. 
And that immediately corresponds to those 
two constructions. 
and then the transfer theorems 
immediately give us the for For those two 
combinatorial classes. 
F(z) is 1/1-G(z) and G(z)=zF(z), that's 
what I referred to in a previous slide. 
So now, if we just solve that we get F(z) 
substitute in 1-zF(z) for G(z) and then 
solve for F, you get F(z)-zF(z)^2=1. 
and that's exactly identical to the 
catalan generating function, so it means 
that the number of forests with N nodes 
is exactly, exactly equal to the number 
of trees with N nodes, which is the 
catalan numbers, which we know the 
asymptotics for and the number of trees 
with N nodes, the number of force with 
N-1 nodes, 
so it's got a factor of 4 left. 
so that's a symbolic method that shows 
that the number of force and the number 
of trees is exactly the same. 
Now, from an analytic point of view, 
we're happy to get get the result. 
But usually in combinatorics, when you 
find that you have two classes, that 
enumerate exactly the same what you want 
to find is a bijection showing that a 
correspondence between every member of 
one class and every member of the other. 
And, in this case, that bijection is 
important because it gives us a way to 
represent forests and trees in the 
computer conveniently. 
so here's how that bijection goes. 
Every forest with N nodes corresponds 
precisely to a binary tree with N nodes. 
now forest that node can have multiple 
children, in a binary tree, a node can 
have exactly 2 children. 
So the way the correspondence goes is 
that for every node, we connect it to its 
left child and its right sibling. 
So the node at the left in the forest 
corresponds to the top node in the binary 
tree and so forth. and that's a 
one-to-one correspondence between force 
and binary trees. 
Another way to look at this may be even 
easier to see, called the rotation 
correspondence. If you take this binary 
tree [COUGH] and connect it up as if we 
have the nodes in the forest, 
you can see that you have the forest kind 
of rotated. 
and that's a very useful and easy way to 
represent forests in general trees within 
a computer because a binary tree is easy 
to represent in chunks in memory where 
every node has whatever information is 
associated and its two children. 
whereas in the forest, you have to deal 
with a variable number of children per 
node, which can be inconvenient and 
difficult in some computing environments. 
just as an aside, 
that these points what we're thinking 
about is the idea of an algorithm for 
growing binary trees. 
and I want to show that because I'm going 
to be showing a lot of binary trees. 
and the exercise of writing a program for 
drawing binary trees is a worthwhile 
exercise for everyone to do. 
So the most natural approach that we use 
very often, particularly when talking 
about a sorting and searching algorithm 
is to well, first of all, the 
y-coordinate is easy, that's just well, 
it's the depth but since they go down, 
it's the height minus the depth. 
So, we start with the root at the, at the 
highest and just subtract 1 so we know 
the y-coordinate of every node. 
the x-coordinate of the node the easiest 
way to set that up is to just do a 
recursive, in order traversal, 
traversal of the tree and just assign 
x-coordinates every time you reach a 
node. 
and that's corresponding to set of 
recursive programs says, what's the 
coordinate of the root. 
it's the number of nodes on the left plus 
one. 
and then the coordinate, the x-coordinate 
on the right side is bigger than that. 
And you can see immediately that that is 
number one, it's easy to assign the 
coordinates, just do an in-order 
traversal of the tree. 
and number two, it spaces the nodes in 
the tree out nicely. 
usually when we draw big trees we leave, 
big binary trees, we leave out the 
external nodes. 
now, there's a problem with this, is that 
you get the distracting long edges for 
some kinds of trees. 
particularly for say, binary trees 
represent general trees. 
and you can use a similar algorithm like 
this for general trees by the way. 
but anyway, that's a problem. 
So what we do sometimes is take the 
x-coordinate and at every level we just 
evenly space the nodes. 
If there's four nodes at that level, we'd 
evenly space them and send them on their 
route node. 
And that's a useful way to draw trees 
because it gives a profile of what the 
trees how thick the trees are, how many 
nodes there are at each level. 
And that's an interesting thing to know 
about in some kinds of analysis. 
so just, this is what a random binary 
tree looks like with this idea. 
And actually when you see random binary 
trees they have many, many different 
shapes. 
And if we were to do random trees or 
random forests as well you'd see quite A, 
A collection of different and interesting 
shapes. 
and so, the challenge that we have that 
we're going to go into and the reason 
that I wanted to draw these big binary 
trees is to make clear what that 
challenge is. 
And so, we have to analytically 
characterize this in some way. 
maybe averaging over all of these or 
whatever it is that we're doing in terms 
of the analysis. 
it's going to have to explain this this 
kind of behavior. 
And remarkably we're able to get very far 
in doing that and so that's what we'll 
start doing now. 
That's just a brief introduction about 
trees and forests.