Core: Searching in a BST

Loading...

Do curso por University of California San Diego

Estruturas dedados: medindo e otimizando o desempenho

1342 ratings

University of California San Diego

Estruturas dedados: medindo e otimizando o desempenho

1342 ratings

Curso 4 de 4 em 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!

Na lição

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

Conheça os instrutores

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]

Now that we have a good idea of what a binary search tree is,

let's talk about how we do a search in a binary search tree.

So by the end of this video,

you should be able to perform searches within a binary search tree.

So the idea behind a binary search tree is very similar to binary search of an array.

So what we're gonna do is I'm just going to give you a few examples of this and

then we'll talk about how we could solve this with code.

So first off, let's say I'm trying to find element C, well how am I gonna get there?

Well I'm gonna start with the root and we'll look and I'm gonna say is E C?

Are those the same things?

No they are not.

E is actually greater than C.

And because E is greater than C, it tells me to look in the left sub tree of E.

So, my next step is to move my current notion of tree node down to B.

I'm going to look at B and compare B to C.

Are they the same?

They're not.

B is less than C.

So I now need to look at the right sub tree of B.

So now I'm gonna head and look at C.

So in other words in node C where going to ask is C equal to C.

It is, yay, we found it!

We're done, all we have to is return true or

return the node depending on what we're doing with the search.

We found this binary search tree contains the element C.

So, let's do one more example here.

Let's start searching for P.

So, what I'm gonna do is again start at the root.

I'm going to look at E.

I'm gonna ask.

I'm gonna compare E and P, and I'm gonna ask are they the same.

They're not. E is less than P, so

I'm gonna go into the right sub tree of E.

So now I'm gonna look at M.

I'm gonna ask again, what's the relationship between M and P?

Well, M is still less than P so I need to go to the right sub-tree of M.

And now I'm gonna look at Q.

And I'm gonna see that, do the same comparison, Q is not P.

I'm gonna see that Q is greater than P,

therefore I need to look in the left sub tree of Q.

There is no left sub tree of Q.

P is not in this array, so it's no here and I can return false.

Essentially that's not found.

So now that we have the idea of how to do this search,

the question is how are we gonna put this into code?

Well first off, you could solve this fairly cleanly using recursion.

And the way I want you to think about this is that if I'm thinking about what do I

wanna do at node E, so the tree rooted at node E.

It's very similar to what I'm gonna want to do when I'm looking at the sub tree

rooted at node B, which is very similar to the comparisons I might make for

the sub tree rooted at C.

So because it's the same behavior at each step, this lends itself well to recursion.

You can also solve this very cleanly using iteration.

And here you would just have a loop where you're essentially keeping track of your

current node.

So just like we did before, you'd have your current node be E, then B, then C and

you can just essentially walk through the tree that way.

Now at this point, I want you to try this on your own.

So you're gonna be searching in the project for an element.

And I'd like you to try that code on your own before you look for

any support videos.

But if you want some more support, and you're a little bit stuck on how to search

a tree, we have a more thorough walk through of doing search

in one of our support videos, so you can always look at that there.

Next, we're gonna start looking at how to do insertion and

deletion from this binary search tree.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play