Core: Trees

Loading...

来自 University of California San Diego 的课程

Data structures: Measuring and Optimizing Performance

1354 个评分

University of California San Diego

Data structures: Measuring and Optimizing Performance

1354 个评分

课程 4（共 4 门，Specialization Object Oriented Programming in 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? 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 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! (including Binary Search Trees and Tries)

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. :)

Core: Trees3:09

In the Real World: Trees0:34

Core: Defining Trees3:31

Core: Binary Trees5:25

Core: Pre-Order Traversals7:03

Core: Post-Order, In-Order, and Level-Order Traversals (Breadth-first search)8:53

When I struggled: Why traverse a tree?0:50

Core: Introduction to Binary Search Trees5:31

Core: Searching in a BST3:23

Support: Code for BST's "Find" Method7:39

Core: Inserting into a BST4:03

Support: Code for BST's "Insert" Method6:02

Core: Deleting from a BST4:26

Concept Challenge: BST Shape7:08

与讲师见面

Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Leo Porter
Assistant Teaching Professor
Computer Science and Engineering

[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 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

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

通过 App Store 下载

通过 Google Play 获取