Explore
For Enterprise
Join for Free
Log In

Arts et humanités
Business
Informatique
Science des données
Technologies de l'information
santé
Mathématiques et logique
Développement personnel
Sciences physiques et ingénierie
Sciences sociales
Apprentissage des langues
Diplômes
Certificats

Explorez l'intégralité de Coursera

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

Trees and Forests

Loading...

Analyse de la complexité des algorithmes

Université de Princeton

4.8 (52 notes) | 22K étudiants inscrits

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. All the features of this course are available for free. It does not offer a certificate upon completion.

Visualiser le programme de cours

Avis

4.8 (52 notes)

5 stars
45 ratings
4 stars
3 ratings
3 stars
3 ratings
1 star
1 ratings

AK

Apr 29, 2018

This course is more about mathematic than algorithms, it teaches how to solve tricky combinatorial problems

HL

Mar 10, 2018

This is great course if you already done some algorithms courses and want to go deeper.

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

Trees and Forests14:16

Binary Search Trees 22:50

Path Length 25:55

Other Types of Trees 13:56

Enseigné par

Robert Sedgewick
William O. Baker *39 Professor of Computer Science

Transcription

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.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales