All language subtitles for 12 - Searching Through a Binary Search Tree English

In this tutorial we're going to walk through how binary search actually works.

And before we get into that we need something to compare it to.

And so what we're going to compare it to is something called linear search on the page right now.

We have a standard array and its array of integers going from 1 to 25.

The order doesn't matter at all because all we're concerned with right now is searching for an item.

So let's do a sample search.

The first thing we're going to search for is 15 and we're going to see how many times we have to iterate

through the array which means to go through each element in the array before we get to 15.

So we start out at the zero element which actually is one is the value.

And so we go one two three four five six.

So we actually have six things that we have to go through in order to get to that 15 value.

Now if we want to go to 25

in this case we would go one two three four five six seven eight nine 10 and 11.

And what if there was nothing the element we were looking for wasn't even in the array.

So say we had ninety nine.

It would be what we call and there would be in you know which is similar to 25 except in this case it's

considered the worst case time complexity because the element isn't even in the array which means we

would go through the entire array without finding an element and then returning that we couldn't find

it.

So this is not a good way to search because right here we only have 11 elements.

What would happen if we had a thousand elements or a million elements or 10 million elements.

If you think about when you're using Google it's not going through every single site on the web to find

what you're looking for.

It has an algorithm that makes it a much much more efficient.

And what we're going to look at is not exactly what Google uses but we're going to look at a way to

make searching a lot more efficient than this.

If you're taking this for an algorithm class you'd one know the worst case time complexity is going

to be big go of and for a linear search through an array like this.

And if you're not taking it for our algorithm classes you know what it's talking about.

Don't worry it's just called Big O notation.

So we're going to do the same thing here.

We're going to go 15 25 and the

you get now to know how search works on a binary search tree it's very important to know the structure.

So if you've not watched my previous video on showing how to set up a binary search tree you may want

to go watch it.

If not just follow along and it is pretty intuitive and easy to pick up.

So we're going to first do our very first search which is 15.

In this case 15 is the root node which means that our this only took one iteration we only had to search

through one item we found it and then we returned.

That's not always the case.

In fact it's very rarely going to be the case the item you're looking for is actually at the root.

But when it is that's what it's going to return.

Now let's look at what it would be if it was 25.

If you remember last time it took us 11 steps to get to 25 here.

Let's see how many steps it's going to be.

So we start at 15.

That's one then we realize that 25 is bigger than 15.

So we go to the right hand side.

So here we see okay we compares 25 bigger or smaller than 20.

We know it's bigger.

So we look at the right note again so so far this is we've taken two steps.

Now we're at 22.

Once again we compares 25 bigger than 22 or is it less than we know it's bigger and we arrive at 25.

That took us a total of one two three three steps until we got to it.

And if you want to include that last one it took four steps to get to it.

Ninety nine would actually be the same number it would only take us four steps because we would go from

15 to 20 20 to 25.

We'd realize that 25 is the leaf and there is nothing greater than 25.

And the system would return that 20 the 99 was not in the binary tree.

So you can see right there and compare these two.

This is dramatically faster than than having to go linearly and go through every single item.

It's very rare that you would actually find something using a linear search faster than using a binary

search tree.

Mainly because it's very rare you'll find your element on the second or third second or third iteration.

But the way to think about this is what really helped me understand this at least was being able to

think of opening up a phone book.

And when you have a phone book say that you start and you're using the white pages for example it's

sorted by last name and you have somebody that Star last name you're looking for starts with an M. you're

going to open it up somewhere in the middle doesn't matter where you look it up.

And then from there you're going to compare them or you could compare whatever page you opened up.

So let's say you opened it up and you open it up at the letter D and you know that you need to get to

em.

So you have a goal of getting to them now you look at the U.S. that is less than or greater than them.

We know it's less than them alphabetically.

So what do we do.

That means that we would go to the right and we would open that up again and then we would keep on doing

this over and over again until we find them.

And so it's a very similar thing with the binary search tree.

You take the number you're trying to find.

You go through every different stage every different level of the tree and you look either to the right

or to the left and then you make your decision based off that.

So just to practice it one more time.

This time we'll look for the number 21.

So we started 15 is 21 less than or greater than 15.

It's greater than we go to 20.

Now at 20 we do the same thing.

The comparison says that 21 is greater so we go down again and we have 22 there with 22.

When we compare coin one is less than 22 and we find it and it only took us four steps which is incredibly

fast.

Now the average time complexity is big.

So of blog base to event.

And so this is extremely fast if you're familiar with the principles logarithms.

Logarithms are kind of like exponents except backwards.

So if the other search was was N log in means it's dramatically faster.

That's on the average case which is very important to note.

This is an average case.

What makes something an average face when it comes to a binary search tree has a lot to do with how

balanced the tree is.

So that is something to remember.

You want to have your binary search trees balanced.

Very important the key to this is something I'm going to show you a binary search tree can actually

equal the same complexity as a regular linear search.

And do you know how that can happen.

It's actually relatively intuitive.

Here you can see are nodes.

You have the root and you can see this tree is actually completely symmetrical.

It's very rare to have it exactly like this but it's nice when it is because it makes searching through

it incredibly fast.

Now on this page you will see this is a horribly balanced tree.

There essentially is no tree and you will run into cases where this happens.

And so what you're going to have to deal with here when it comes to searching you're going to have a

complexity of big-O event which is actually identical to searching using a linear search method.

And the reason for that is this is actually the root node.

I know it doesn't even look like a tree.

So it's hard to see however.

This is the root.

So if we have a number we can simply say the number is 1.

We actually have to go through each element and it's the last element in the search tree that has that

total.

So this makes searching really kind of pointless or using this kind of data structure pointless if this

is what your tree looks like.

It works out much better if you have a well-balanced tree and there's some tutorials I'm going to create

that will talk about how you can balance your tree out if you happen to have something that looks like

this.

But this is this is where usually can have a way that you can randomize and balance out your tree so

that you can get back to those log in type of search complexities.

But it is important to know that the worst case performance of a binary search tree can be as bad as

big event.

So it's important to just always keep that in the back of your mind.

But that's a tutorial please let me know if you have any questions on this whatsoever.

And after this we're going to start learning how to insert and delete nodes off of a binary search tree.