Loading...

Core: Trees

Course video 76 of 109

Welcome to week 4! We know you've been working hard. We hope you tried that optional Markov Text Generation programming assignment last week, but if not, no worries. You can always go back and do it later (spoiler alert: it's pretty amazing that such a simple algorithm can produce such realistic text). This week there's more fun (and hard work) as we learn about trees. Trees rely on the same linked structure idea as Linked Lists, only they're MUCH faster (usually...). In the project this week you'll add auto-complete to your text editor. Believe us when we say it's so cool when you get it working! You'll see... and we bet you can't wait for the programming assignment now. :)

Data Structures and Performance

加州大学圣地亚哥分校

课程 4（共 4 门，面向对象 Java 程序设计专项课程）

How do Java programs deal with vast quantities of data? Many of the data structures and algorithms that work with introductory toy examples break when applications process real, large data sets. Efficiency is critical, but how do we achieve it, and how do we even measure it? This is an intermediate Java course. We recommend this course to learners who have previous experience in software development or a background in computer science, and in particular, we recommend that you have taken the first course in this specialization (which also requires some previous experience with Java). In this course, you will use and analyze data structures that are used in industry-level applications, such as linked lists, trees, and hashtables. You will explain how these data structures make programs more efficient and flexible. You will apply asymptotic Big-O analysis to describe the performance of algorithms and evaluate which strategy to use for efficient data retrieval, addition of new data, deletion of elements, and/or memory usage. The program you will build throughout this course allows its user to manage, manipulate and reason about large sets of textual data. This is an intermediate Java course, and we will build on your prior knowledge. This course is designed around the same video series as in our first course in this specialization, including explanations of core content, learner videos, student and engineer testimonials, and support videos -- to better allow you to choose your own path through the course!

查看授课大纲

您将学习的技能

Trees (Data Structures), Data Structure, Linked List, Binary Tree

教学方

Christine Alvarado
Associate Teaching Professor
Mia Minnes
Assistant Teaching Professor
Leo Porter
Assistant Teaching Professor

脚本

[MUSIC]

In this lesson we're gonna start learning about trees.

Trees are incredibly powerful and

versatile data structure that are used commonly throughout computer science.

In fact, many of the data structures,

built in data structures that you've used in java before,

almost certainly have trees on their back end, in their implementation side.

So, where gonna do today is just look at why are trees valuable and

why are they so common?

So, trees somewhat naturally represent data in the real world.

So, you've almost certainly seen a family tree before where you have

a parents whose children are below them in the tree and

then you've got the children of those children even further down the tree.

And this is a tree from a fairly popular TV show these days.

Decision trees are also fairly common.

If you ever gone to a medical health site,

you almost certainly went through a decision tree if you were trying to figure

out what to do based on your symptoms.

Similarly, this is kind of a fun anecdote, if your house is clean,

you might make a decision.

Yes, my house is clean, so I just relax.

No? Well.

Is my floor clean?

Well, no, so I better sweep the floor.

So these kinds of decision trees help guide decisions you might make.

Well think of it in science, you might do an expression tree.

Now we're not gonna dive into the details of this, but

if you wanna evaluate the expression 45 / (3 +6), you actually represent

it really cleanly as a tree and be able to evaluate it much more easily.

You almost certainly have file systems on your computer.

And file systems are perfect examples of trees.

Where if I want to know that my path is users, porter,

well I know it based on the tree structure.

You can see that there's a root, then users, then porter.

So there's lots of trees in computer science.

In fact, you almost certainly have heard of some of these.

But there's just regular trees, there's binary trees, there's heaps, there's

binary search trees, there's Huffman trees, there's AVL trees, randomized

search trees, red black trees, tons of these, all throughout computer science.

Why are there so many trees?

Well, there's two reasons why trees are so powerful.

The first is that they're a dynamic data structure.

What I mean by that is, it's really easy to add a new directory say,

for Professor Alvarado.

So dynamic data structures just like are nice, cuz it's easy to add and remove.

The more powerful feature to trees is that their structure conveys information.

So the fact that users is a child of root and

that porter is a child of users tells me that that path exists to users/porter/.

In fact, if you just change the structure around a little bit,

you get all these different kinds of trees.

If you make the structure such that root, the very top level,

has to be the most important.

Well now you've got a heap.

If you wanna organize it based on character frequencies in say a body

of text, well now you've got a compression tree or Huffman tree.

If you wanna organize it based on the natural ordering of the nodes,

well now you've got a search tree.

And there's all these different ways that we can organize these trees

to get different data structures.

We'll look in detail at a few of these trees, in these following lessons.

关于 Coursera

课程、专项课程和在线学位均由全世界一流大学和教育机构的顶尖授课教师教授。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取