0:04

Today we're going to talk about trees.

Â This is the first second half of the course is

Â the first 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 did was introduce analysis of algorithms.

Â But then we 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 performance of algorithms.

Â And then we finished off last time by introducing analytic combinatorics.

Â So this is all about mathematics and about the techniques.

Â 0:43

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 classical commenatorial

Â classes with lots of applications.

Â And we're going to look at

Â 1:07

And this will bring us to a really basic combinatorial class with all kinds

Â of applications.

Â Trees, permutations, strings and triads, words and mappings.

Â And we'll be using labeled and unlabeled classes.

Â They're alternating with ordinary generating functions and

Â exponential generating functions.

Â Really applying all the mathematical techniques

Â that we learned in the first half of the class.

Â So today, were going to begin with trees.

Â And we'll start off by talking about basic definitions of trees and forests.

Â To begin I'll review what we've talked about in terms of binary trees,

Â 2:16

The external nodes are signified with little boxes and

Â the internal nodes are signified with circles.

Â And 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 the tree.

Â Starting with the root at depth zero,

Â the children of the root at depth one, and so on.

Â 3:01

And we did a derivation with the symbolic method that I will just rush through

Â because we have 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 s to 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 we set the size of those atoms,

Â that's what we're going to count.

Â In this case, we're counting internal nodes.

Â And then we have a combinatorial construction that comes 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.

Â 4:07

So now in general, the classical mathematical concept of

Â a tree is In terms of forests.

Â So a forest is a set of trees and a tree is a forest with a root added to the top.

Â And there's actually, just from this quick observation,

Â the generating function that enumerates forest is just 1 over Z or

Â the generating function, that enumerates trees,

Â is just Z times the generating function, that enumerates forest.

Â By corresponding to adding the root.

Â So, this is the recursive definition, but these are recursive structures.

Â A forest is a sequence of destroyed trees.

Â A tree is a node, called the root.

Â And it should say, forest is empty or secret to destroying trees.

Â Trees of node, called the root, connect into the roots of trees, in the forest.

Â And so, now a route can have any number of children, including zero.

Â In the leaf nodes of the nodes with zero children.

Â 5:07

And then the level is the same as before,

Â we start with the root at depth 0,

Â the children of the root at depth 1, and so forth.

Â And the height is, again, the deepest node in the tree.

Â 5:40

So these are all the forests with one, two, three, and four nodes.

Â And immediately, right away, you can recognize

Â 6:06

another node in either order.

Â Or the root node connected to two children or the straight

Â line which is a root connecting to a child connecting to a child.

Â Notice the order of significance, a forest is a sequence of trees and

Â that's consistent with computer applications where we have to represent

Â the thing in the computer some way, we pick a sequence usually.

Â 6:32

So anyway, the catalan number are here and of course

Â a tree is 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 a shift over by one.

Â 6:55

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 the completely wrong answer.

Â So it's 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 is just one kind of node.

Â And it's 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 do we say?

Â We say 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 ogf's for

Â those two commonotorial classes.

Â F(z) = 1 / 1-G(z) and G(z)=zF(z) that's what I referred to on the previous slide.

Â So now if we just solve that we get F(z) substitute in one minus Z F of Z for

Â G of Z and the solve for F, you get F of Z minus Z, F of Z squared equals one.

Â That's exactly identical to the catalan generating function.

Â So it means that the number for

Â a forest with N node is exactly equal to the number of trees with N nodes,

Â which is the catalan numbers, which we know the asymptotics [INAUDIBLE] For.

Â And the number of trees within nodes,

Â the number of forests with N minus 1 nodes, so it's gotta factor for less.

Â 8:41

So that's a symbolic method that shows that the number of forests and

Â the number of trees is exactly the same.

Â Now from an analytic point of view, we're happy to get the result.

Â But usually,

Â in common 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.

Â 9:32

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 of the forest corresponds to the top node

Â in the binary tree, and so forth.

Â That's a one to one correspondence between forests and binary trees.

Â Another way to look at it that's even maybe easier to see, called a rotation

Â correspondence If you take this binary tree [COUGH] and connect it up as if it

Â were the nodes of the forest, you can see that you have the forest kind of rotated.

Â 10:09

And that's a very useful and

Â easy way to represent forests and general trees within a computer.

Â Because a binary tree is easy to represent in chunks of memory where

Â every node has whatever information's associated and its two children.

Â Whereas in a forest you have to deal with a variable number of children per node

Â which can be inconvenient or difficult in some computing environments.

Â 10:38

Just as an aside, at this point it's worth thinking

Â about is the idea of an algorithm for drawing binary tress.

Â 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 tress is a worthwhile exercise for everyone to do.

Â 11:01

So the most natural approach that we use very often,

Â particularly when talking about sorting and searching algorithms,

Â 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 highest and then just subtract one.

Â 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 inorder traversal of the tree.

Â And just assign x coordinates every time you reach a note.

Â And that's corresponding to say the recursive

Â programming says what's a coordinate of a root?

Â It's the number of nodes on the left plus 1 and

Â then the x coordinate of everything on the right side is bigger than that.

Â Then you can see immediately that number one is easy to assign the coordinates,

Â just do an in order a traversal of the tree and

Â number two it's basis the nodes on 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 will 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 evenly space them and

Â center them on the root node.

Â 12:55

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

Â 13:18

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 see quite

Â 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.

Â So we have to analytically characterize this in some way.

Â I may be 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 behavior.

Â And of remarkably we were able to get very far in doing that and so that's what we'll

Â start doing now, that just a brief introduction about trees and forests.

Â