All language subtitles for 11 - Binary Search Tree Introduction English

In this episode we're going to walk through the structure set up in the properties of a binary search

tree.

The first thing to know about a binary search tree is what it is and how you can think of it is a visual

representation of a data structure.

And when you connect the search functionality what you're doing is trying to create a rapid way that

you can iterate through your data structure to give you a result.

And so if that doesn't make any sense.

Don't worry we're going to walk through every stage of it.

The first thing we're going to do is talk first about how to set it up because that's the way that I

learned best and that's the way that helps me out the most.

So to set it up you're going to assign a integer to a root node.

And so we put that up at the top of the tree.

And so we're going to give it a value of 15 and we're going to put a circle around it.

That is what is called our root node.

That is

the root node and everything else is going to be based off of that whether it's to the left or to the

right.

So the next thing we're going to do is give it to different branches to its children.

So we're going to have a branch here and branch here and then we're going to go to different nodes the

other node on the left is going to be 12 and the node on the right is going to be 20.

Now each of these nodes has their own set of children.

And so to represent that we're going to draw two more.

And so we have a node here and here and this one is going to be 10 and on this one we're going to set

it up with 14 and we're going to keep on going here on the left hand side of the of the tree.

And so the last one we're going to do is going to have two nodes and it's going to be one and 11.

Now when we get to a spot of the tree where it did know does not have eight children.

These are called leaves.

So this is and this these are all called leave notes

and so when you hear someone say the leaf of the tree or the leaves of the tree that means that they're

talking about you no that has no subsequent children underneath them.

So that complete to the left hand side of our tree.

And now we're going to go on the right hand side.

So 20 root than 20 has two children what once every 16 and the one on the right is going to be a 22.

And then 22 has two children notes as well.

And on 22 it's going to be 21 and the last one is 25 thinker.

Now the leaf nodes on this are 16 21 and 25.

And we have a complete binary search tree structure set up now looking.

Talking about the properties.

It's a very important thing as I was writing it out you probably saw with the sequences and the way

that's to be set up this root node right here in the middle

anything to the left of the node has to be less than the root node.

So everything over here.

Everything on the left hand side is going to be less than the root.

Everything on the right hand side

is going to be greater than the root.

Now if you notice because this is some recursive functionality not only is this the case for the root

is also the case for each of its subsequent children.

So let's do something what we call traversing the tree.

So we start off with 15 and then we go down to 12 from 12 you see 12 as two children twelves children

a child on the right is 14 on the left it's 10 the right node is greater than 12 the left node is less

then go down further down the training of 10 which is less than 11.

The the child on the right hand side and then one which is less than the parent of ten.

And if you go into the right hand side you have the exact same structure and set up the really nice

thing about using a binary search tree is not only is it great to search and or the subject of our next

episode it's going to be on how to actually iterate through the tree to find the number.

The really nice thing is to find min and max value and if you think about it you think about it's very

easy it's also very fast and efficient.

From a performance standpoint.

So how do you find the minimum value of a tree.

All you have to do is start at the root and traverse all the way down the left side and you know the

left route the left node the no furthest to the left in the tree is always going to be the lowest value

in the tree.

And in the exact opposite context if you take the 15 the route and extend all the way to the right to

find the max all you have to do is do that.

You just go through the tree traversing the tree go all the way find the element all the way to the

right and you found your next county.

So great job.

If this is your first time learning binary search trees.

If they look a little bit tricky at first do not let that stop you from learning them.

They are extremely useful in computer science.

They're a great way to visualize data and they are have a great performance value as we're going to

get in the next episode when it comes to search and using heaps and different things like that.

And I think the more you get used to the easier they'll be you'll become very familiar and you'll be

able to use it in a lot of practical ways as you develop applications.

So thank you for your time.

And I look forward to seeing the next episode.