This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.
Trees and Forests
Loading...
En provenance du cours de Princeton University
Analysis of Algorithms
32 notes
À partir de la leçon
Trees
The quintessential recursive structure, trees of various sorts are ubiquitous in scientific enquiry, and they arise explicitly in countless computing applications. You can find broad coverage in the textbook, but the lecture focuses on the use of analytic combinatorics to enumerate various types of trees and study parameters.
Rencontrer les enseignants
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
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.
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
Techniques from analytic combinatorics that we use to study them.
Including applications to the analysis of algorithms.
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,
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 and
two binaries tree were the order of the internal nodes is significant.
So, at the top is the root and in this case that root has to binary trees or
two internal nodes as its children.
And down at the bottom,
we have some notes 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.
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.
And the deepest node in the tree, that's what we 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 trees are there with N nodes and
that is the axillary numbers.
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.
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.
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.
In contrast to binary trees, we don't have external nodes in general trees.
So that's, now a question comes up immediately, it's enumeration.
How many different forests are there with N nodes?
So these are all the forests with one, two, three, and four nodes.
And immediately, right away, you can recognize
that the catalan numbers are rising yet again.
So there's five forests with three nodes.
Just three individual nodes or a tree of size two and
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.
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.
So let's looks at the analytic combinatorics for
deriving the catalan generating 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 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.
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.
So here's how that bijection goes.
Every forest with N nodes corresponds precisely to a binary tree with N nodes.
Now, the forest node can have multiple children.
A binary tree node can have exactly two children.
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.
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.
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.
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.
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
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 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.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
