Deletions & Insertions

[00:00:00]
>> Alright, so we're going to talk about deletions from a binary tree. So this is where things get a little bit intense we didn't cover this last time. I just wanna make sure we have this for knowledge because now covering this will be fun. All right, so there's three cases when it comes to deletion.

[00:00:13]
So I'm just gonna come up here and say three cases. So let's cover case number one, which is you're just a child with no children, right? You're somewhere in the tree, I guess I could have just said you're a node with no children. That probably makes more sense.

[00:00:31]
So let's just draw out just a fictional binary tree. We don't even have to fill in the values. If we were to delete this right here, there is no special handling required, right? Because when I delete this, well, it's just gone, there's no adjusting. So I would just simply delete the link and whatever reclamation you have to do for your node you can do if this is rust, it drops it automatically.

[00:00:52]
If it's JavaScript, you'll collect it later at some point with a nice garbage collection halt. All right, now the next one it's going to be one child. This one's a bit more difficult. And I'm gonna continue to use these terms in a general sense, because I think it's a little bit easier than putting concrete numbers.

[00:01:12]
Because the moment you put concrete numbers, you think in more concrete terms. But remember, all we are gonna think about is less than, greater than. So in other words, x is less than, I'll put z in the middle, which is less than y. So always think in these terms because it makes it really easy to organize and understand this tree.

[00:01:31]
So down here, let's just pretend this is A, this is B, and potentially we have B right children and we have B left children. Look at that BR, Brazil mentioned. People love Brazilian mentions, it's the quickest way to get 1,000 likes on a tweet. Just say Brazil and it'll just be filled with Brazil mentioned, they just love it.

[00:01:52]
All right, so now that we got that done, if we were to delete A, how do we delete A? Anyone have any ideas?
>> Place it with B?
>> Yeah, that's pretty much it. You erase, erase, down. It's pretty much straightforward when you only have one child, you don't have to worry about this, because is this still true?

[00:02:13]
What is BL's relation to up here? I'll put x as the root. Well, we know one thing. BL is less than B. B was less than A, but A is greater than X. And since it's all on this side, we also know that BL is, by the very nature, greater than X.

[00:02:30]
So therefore, we can just move it up. We don't have to move any of these nodes around. We know they're all still upholding the rules of a binary search tree, which is just this. You must maintain this rule, so it's very, very important. I like the hood up, this is a good move.

[00:02:44]
All right, so let's do one more. I'm gonna, again, just use very general terms cuz numbers really don't help you in this situation. So let's just pretend we have the node in which we wish to delete, but we have A, B and we have A C and there are B left children, B right children.

[00:03:06]
There is C left children and there's C right children. So this one is a little bit more tricky. So we do know that whatever is up here, all of these nodes are greater than, we're gonna pretend this is on the right hand side. So we kind of have that in our minds, so we know kind of where we're at in life it really doesn't matter you just know that whatever it is we don't have to worry about anything on this side cuz we're only dealing with this subtree right here.

[00:03:31]
All right, so a strategy is you kind of have two choices when it comes to case three which is of course the two child problem. Kind of like the three-body problem, but not as long of a book. So we have to choose, do we want to delete from the left or the right?

[00:03:49]
Now I did leave up this right here, because we are gonna use this term in order very, very importantly. There is something called the in-order successor and the in-order predecessor. It probably makes sense to you because you know that when we printed out everything in the tree in order, the numbers were in order, right?

[00:04:08]
So let's just pretend we had a tree that when we printed it out, it did 10, 20, 30. And there's also just a bunch of stuff on this side and a bunch of stuff on this side. As we went through the tree, if we are thinking about 20, this is its in-order predecessor, this is its in-order successor.

[00:04:25]
And what that means is that if we were to go to A and we wanted to find the in-order successor, we would go to the right and then find the smallest child in the larger hand branch. The predecessor would be going to the left and then finding the largest item within the left branch.

[00:04:43]
Cuz what we know is that whatever the largest item is in the left branch will be one less or some less. It will be the next thing next to A, right? So if we were to print it all out in order, it is the 10. This one would be the 30.

[00:04:56]
And so we have to pick one of those two nodes. You get to choose which one you want to pick, and at that point, you can just swap places like whole hog. So let's just pretend we went C and a CL. And let's pretend whatever that value is, we'll just call it C's left largest, right?

[00:05:13]
We're gonna bring that up. We're gonna race out A, and we have C's left largest in here, and now we have A down here. The first thing you must notice is that we reduced A's case down to case one or case two, because you can still have some children here on that side.

[00:05:30]
Wait, hold on, let's see, yeah. Not on that side, my bad, on the other side. You could still potentially have children on this side. And what I mean by that is that as we go down the left side, we're trying to go all the way right. You could still have a left branch coming off the right, but that is okay.

[00:05:44]
We already know how to delete that one. You just simply break the link, break the link, go right here. So that's easy to delete A, we know how to delete A. Why is this true? Well, what can we say about this one? This one is smaller than C, it's smaller than all of C's children on the left because it was the smallest child on the left.

[00:06:06]
Therefore, if it goes into this place, it 100% upholds this because we already know C, right? They're all larger than C. This was on the left hand side so we know it's smaller. So we can maintain this rule by moving the largest or the smallest large item up, same thing with the other side.

[00:06:23]
You move the largest small item up, it will be larger than everything on this side, but it'll be smaller than everything on this side. So we do get to maintain this by just simply grabbing that out. So that's a very kind of important concept. Hopefully everyone kinda gets that.

[00:06:39]
Are we feeling good about delete? Does this make sense?
>> So you're saying that A might still have children, but CL, was that a leaf node?
>> It's sort of a leaf node. Here, I'll draw it up in concrete terms now, really quickly, and we can just kind of see this happen in action.

[00:06:55]
And I'll make sure it happens in a good way. So I'm just gonna put 100 in here, because that way I don't have to plan has had nearly as well. Let's do 50, 60, 70, 65 and then we don't care what's on this side, okay, we'll just call that B.

[00:07:14]
So if we were to do the in order predecessor at this point, we would go and find the largest value on this site. So we'd go left once, and we'd drill right as far as possible. So right, right, can no longer go right, so we choose 70. Now 70 is gonna go up here.

[00:07:31]
100 will go right here. 100 is currently in violation, but we're deleting out that element since now we've reduced it down to a case one or case two. It should be pretty easy, since its case to delete link, delete link, delete node, establish new link. And you'll notice that it maintains the correctness, but now this thing is on the right hand side because we deleted off the right hand side node.

[00:07:55]
But notice that 70 is larger than everything on this side but we know it's smaller than everything else on this side. Does that make sense? You can still have children, you can still run to the 1K side. Because when you drill to the left, there's still potentially the leftmost node may have a right child.

[00:08:11]
Just like this one, the rightmost node had a left child.
>> So you go until you can't find any greater number, and then that nodes parent, it's new right becomes the node that you're deleting left.
>> Yes, yes, which makes sense because here I'll reestablish this situation. So let's go back here.

[00:08:32]
So we had 100 moved in right here and we had 65 right here. 100 is to the left of 60. So when we just simply remove out 100 and keep this up, we know for a fact that everything within this subtree is gonna be larger than whatever's right here.

[00:08:48]
So of course it naturally has to move into the right-hand position. So it's very good just to kind of keep this in mind because this is one of the trickiest parts about algorithms, is understanding the basic principles and how to move things around in the basic principles. That is why I actually started with deletion as opposed to insertion, cuz insertion is actually rather simple.

[00:09:06]
So we're gonna move on to insertion really quickly. This one is not very hard at all. So I'm gonna put in these following nodes. All right, should be pretty easy so we start with 10, nothing here, boom we have a 10. All right, we're gonna insert 20 Which direction do we go left or right?

[00:09:25]
>> Right.
>> Awesome. All right, we're gonna insert in 30, 30 is larger than 10 goes down to 20, 20 is still smaller than 30. So therefore we go right again, we put it in. All right now we're gonna put in 40, 40 is larger than 10, 40 is larger than 20, 40 larger than 30, therefore we go all the way down here.

[00:09:43]
What has happened to our tree?
>> Upside of it.
>> Our tree sucks, right? Like this is actually, if you really think about it, we just got done writing a very complicated linked list. That's all we just got done doing, we have just made a linked list. And so this thing sucks and we want to be able to do something about this.

[00:10:02]
Our search time, remember, is not log n, it's technically h. In a well balanced binary tree that is log n, but in this tree h is n. And so that totally sucks. And so there you go. This is the introduction to the last algorithms course you'll ever want because hopefully by the end of it, you never wanna see a whiteboard or an algorithm again because this is gonna get slightly complicated.

[00:10:28]
All right, that's the fundamental knowledge you need. Now we can get into some data structures and algorithms.