Binary Search Tree Overview

[00:00:00]
>> The first thing I wanted to talk about are binary trees, everyone familiar with binary trees. If you're not familiar with binary trees, either you have zero children, one child, or two child, that is it. So a binary tree simply just looks like this for everybody. If you're not familiar with it, this right here is called a full binary tree.

[00:00:18]
Meaning that every single possible node has two children and it is perfectly in, there's just no extra levels. The levels completely filled at every single style, so that is called a full binary tree. If you have one missing this is called a partial complete binary tree and why it is partial complete.

[00:00:36]
Is a complete binary tree would be this, kind of odd that a partial complete can have more nodes. Where a complete binary tree will have less nodes. A complete binary tree just simply means that every single node has its max children on it. So it's a little bit different than a full fold being the greatest binary tree possible.

[00:00:53]
But I figured everyone kind of knows a binary tree. I just wanted to say it just in case people are a little bit behind on that. So really what we're gonna focus on is binary search trees. So let's start there, if you're not familiar with the binary search tree, you can imagine that at any one node.

[00:01:08]
You have a link to a parent and a link to potentially two children. On this side of the binary tree, everything is going to be less than whatever is in the middle. On this side of the binary tree, everything is going to be greater than what's on this side.

[00:01:23]
So if this side is Y, this side is X, X is going to be lower than whatever is in here. And this side is going to be always larger. So that's kind of like a rule you must have in your head. Because the rest of the course will make literally no sense for the next two to three hours.

[00:01:36]
Or however long this takes to get through the binary section because it just is like, we will use this to move children. We'll use this to kind of visualize how to walk through everything, because it is just fundamentally very important. So I'll just do something like this right here, so is this value larger than z?

[00:01:59]
No, good job, right. Any sub tree has to follow the rules of its parents, good job. This is a very special node, by the way, we will cover that special node. All right, so I just want to make sure everyone just understands the basic principles of binary search tree.

[00:02:11]
So let's actually write one out. So I'll just go out here and do 10, 8, 3, 9, 20. You can have duplicates, and there are algorithms that talk about having duplicates. But in general, when people are teaching or talking about binary trees, we never actually put duplicates in it.

[00:02:31]
There are things with B plus trees in which there are duplicates, and there are certain ways you move things around. But we're just not going to do those today, sounds good? All right, fantastic, I like everyone's enthusiasm this morning. All right, so searching a binary tree is pretty simple.

[00:02:44]
If I had the value, say we had 15 in here, you start at the tip-pity top of the binary tree. And since we have that really simple rule, which is everything to one side of it, is gonna be less than. Everything to the other side's gonna be greater than, we just need to determine are we this value?

[00:03:01]
Resounding no, exactly. So should we go right or should we go left?
>> Right.
>> Right, exactly. So when we go right, notice that something happened here. Half of the binary tree just became completely invalid. We don't even have to look at that entire half side. So that means we just eliminated one half of all possibilities if this binary tree is nicely balanced like this.

[00:03:23]
So we do it again, are we greater than, less than, or equal to this point?
>> Less.
>> Less than, so which direction should we go?
>> Left.
>> Left, perfect. So when we go left, notice what happened again. Another one half of the remaining tree has been cut out again.

[00:03:37]
Or in other words, one fourth of the total tree has been cut out. And so at this point we land here, we realize we are this value, therefore this value is contained in this tree. Even though there are seven unique values in here, it took us three checks to get to this point.

[00:03:51]
And so as the trees expand when we double the amount of nodes by having one more row. We can still do that cutting out in a really fast space. Now notice that it only takes four checks to find out if there is a node in this tree. As opposed to I forget how many that is, what we at seven, that's 15 nodes.

[00:04:09]
It'd be 15, and we're only doing four checks, so it just grows really slow. That growth is called logarithmic, meaning that search is going to be log of n lookup, n being, how many nodes there are. Or another way to put it, is that it takes the height of the tree amount of searching to find a node, sounds good.

[00:04:28]
Don't worry, we'll be not super hard on the math today. Just because I mean, we'll do some quick maths, but not a lot of maths. Because either I can show you the algorithms or we can focus on analysis and there's just there's not a lot of time to do all of it.

[00:04:42]
So we're gonna kind of focus on, I think, the good parts. Because once you understand how to do some analyzing. It's gonna get easier for you to kinda pick up these algorithms and really understand why they are runtime.