Four Semesters of Computer Science in 5 Hours Binary Search Tree
This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Binary Search Tree" Lesson
>> Brian Holt: Let's talk about binary search trees. So these are not lists. That's the first thing to keep in mind with these trees, is they're not actually lists. They can be used to implement sets, but they're not necessarily a set either, because you can have duplicates, and there's nothing that in the binary search that says you can't have a duplicate.
[00:00:25] But it is a way to store information that makes it very easy and very fast to search for, right? So if you imagine just storing these sequentially, right? Yeah, and there is some notion of order, but the order is made by comparison, right? Anyway, okay, so it makes things very fast to find.
[00:00:47] So instead of having to, if I'm looking for 10, I don't have to go through 1, 3, 4, 6, 7, 8, 10, right, in order to be able to find 10. I can be able to find 10 by going to 8, 10, right? And it's just like right there, it's very quick to find.
[00:01:02] It flattens out your data structure in the sense of like, it makes those finds a bit more quick to find. Okay, so it’s a tree right, so every node, or branch, whatever you wanna call it, we're gonna call them nodes, has zero, one, or two children, right, and no more than that.
[00:01:25] Hence, binary, it's the binary part of the binary search tree, right. Everything to the left of the node, so in this particular case 3, 1, 6, 4, 7, is lesser than, and everything to the right is greater than 10, 14, 13, right. And so, when you're adding things to the BST, you just have to make sure to respect that, right.
[00:01:46] So in this particular case if I were to add two, right. It would go 8 is lesser than 3 lesser than 1 greater than. Nothing's there, so I'm just gonna stick it there. So two would go right here. See if I can.
>> Brian Holt: So,
>> Brian Holt: Here, right? That's where two would go.
[00:02:17] And that's the basic gist of a binary search tree, is it's putting these things into a data structure that makes them very easy to find. Hence, the search part of the binary search tree makes it very fast to search for things. And the great thing about these is these lookups are logarithmic.
[00:02:31] So when we start adding a million elements to this, it's still relatively flat, right, so makes these searches logarithmic to find. So we can keep adding more and more things, and those increases in time to search for things are pretty small.
>> Brian Holt: Okay.
>> Brian Holt: Yeah, and adding things is pretty simple because you just have to add a new pointer to point at something.
>> Speaker 2: Thomas G has the question, where does the nine go in that tree?
>> Brian Holt: Where does nine go in this tree? So if we're doing nine, so if I call BST. Let's see, come on.
>> Brian Holt: Okay, so if I say,
>> Brian Holt: bst.add(9), right? It's gonna go, it's bigger than 8, smaller than 10.
[00:03:29] 10 has no left child, so it just says add the new child right there.
>> Brian Holt: So if you get to a place that doesn't have a child, then it just goes there. So, basically you're following the path along until you find a path is like, it should go here.
[00:03:46] But there's no node to go there, so I'm just gonna put a brand new node right there. It's a good question. Other questions about binary search trees?
>> Speaker 2: I have a question.
>> Brian Holt: Yeah.
>> Speaker 2: You mentioned earlier duplicates. Is that supported in this particular tree?
>> Brian Holt: It is, and it's one of those things where you just have to decide, it always goes the left or always goes to the right.
[00:04:06] So l if I did 8, right, it would eventually just go here. If it always went left, or you would always go here if it always went right. So you just have to make the decision that it's always going to go to the left or it's always gonna go to the right if it's duplicate.
[00:04:22] Does that makes sense, cool.
>> Brian Holt: Any other questions?
>> Brian Holt: Great, well let's make sure I got everything here. So here's another binary search tree in crude ASCII art. So let's say add is called with 7, right. Well, it's smaller than 10, so if it's less than 10, go left to 5, okay.
[00:04:50] It's greater than 5, so we're gonna go right to 8. And it's lesser than 8, and there's no node there. So we're gonna create a new left subtree and put 7 there underneath 8, right. And that's really the whole gist of writing a binary search tree. So there lookups that are (log n) on adds and deletes.
[00:05:13] But they can have a worst case of n. And the reason for that, imagine if you add numbers in order to a binary search tree. It's gonna be a straight line, it's gonna be like a really crappy linked list essentially. So that's the big danger with binary search trees, is having your data somewhat randomized is actually really important for a binary search tree.
[00:05:35] Or in other words, we're actually never gonna use binary search trees in production, we're gonna use something called a self-balancing tree, which is our next exercise after this.
>> Brian Holt: Okay, so just ignore that, just be aware that that's a thing. And we're gonna do these.