Depth-First: Delete

[00:00:00]
>> It's by far the hardest part to all of this. And so let's go. So let's just kind of draw a tree. I wish I had a good tree in mind right now. I think I can create one on the fly. I'm gonna put little X's here to denote that it's null, just to really make it obvious.

[00:00:21]
Let's go 51 why not, good safe. And then let's do 25, let's do 37, and let's do 100. All right, so here's kind of the, let's do this. So, deletion. Let's just talk about deleting this one first. What happens if we were to delete this one? How do we ensure that we preserve the shape of our binary tree correctly?

[00:00:53]
Well, this thing has no children. Therefore, if we just remove it, is our tree still valid? Yes, our tree is still valid. So case one, no child. The answer is just simply delete, right? That makes sense. But let's say that we didn't do that for a second. We still had four right here.

[00:01:20]
Sorry, here, I'll just redraw it out. We still have four right here, and we wanted to delete. How do we delete this this time? Well, if there is only one child, then we can take our parent pointer to ourselves, and point it down to four, right? We just simply remove ourselves, and point it to the next one.

[00:01:48]
So this is a lot like a linked list operation. Hopefully, now you see why you started link list, and move on, cuz what the hell just doing a singly linked lists operation, right, or a doubly linked list operation? Breaking the parents, setting this right. We're just doing the whole back and forth fun times.

[00:02:04]
And you have to make sure you do it in the correct order. So case two, which of course is one child, that is set parent to child. All right, so there's two more cases, and this is where things get old if you will. So the first one is this right here, or this is the one right here.

[00:02:33]
If we were to delete this one, what do we do? Well, let's just say we pointed to this, what happens to 100? It's gone, right? It's gone. You can't get it back. You've not only deleted 51, you've also deleted the entire right subtree, that'd be bad, right? We don't.

[00:02:53]
That's not a very good approach to things. At least in my book, that's not a good approach to how you wanna do a binary search tree. So we need a different tactic, right? We need something that is a bit different. So if we can reduce our case to either case one or two, we've already solved it, right?.

[00:03:10]
So let's try this one. What happened if we took this, and we took our left hand side, which is our smaller side, and found the largest element in our smaller side? Does that makes sense? So we'd go down to our left subtree which is our smaller subtree, and then went as far as we can this way.

[00:03:37]
What happens? Will we find the largest element in our smallest subtree, which means, that if we put it right here, what happens? Everything on this side, will be smaller than or equal to it. Everything on this side, will be larger than it, because this is the largest element in our smallest side.

[00:03:58]
We can also do the same thing on the other side, and we kind of do all of, there is one last thing. We also do one little proof here, which is when we go down to our subtree on our left hand side and go all the way this direction, we can guarantee one thing, it will either have only one or zero children.

[00:04:15]
Meaning that, we keep on going right, until we hit a place where we cannot go any further right. Which means that it can only have one or none, right, because it's could still actually have a left hand child. And if it does have a left hand child, we already know how to solve that, right?

[00:04:30]
So let's just say that is 32, well, simple stuff. We're gonna go here, we'll set this one to now point to that on the right hand side, and this one to now be the parent. See as I said, it's pretty involved level of transitioning, but this is just what you have to do, it makes sense at this point.

[00:04:47]
And you can do the reverse operation on this side of the subtree two, we find the smallest on the large side, and set that as the parent, or we find the largest on small side, that said, yeah. Close enough, right? So why would you wanna choose one over the other?

[00:05:18]
Now this is gonna require you to really think about things in kind of a unique way. Why would you choose one over the other?
>> You'd be more likely to find one that fits the rules on the large side.
>> Nope, cuz the large side you go to the large side, and then go left, until you don't hit a left anymore.

[00:05:37]
On the small side, you go to the small side, and go right until you don't hit a right anymore. So they both could have the case of either case one, no children, or case two, one child, right? We can't tell that type of shape. So I'll give you a little hint right here.

[00:05:51]
You can think height of the tree. That's a reason why you do that, if you kept information in the node about what my maximum height is, plus, my children have their own maximum height. You will be able to tell in old one time, which side has a smaller height.

[00:06:08]
And then you probably want to reorganize the one with a larger height, reason being is that, what are you gonna do? You're gonna shrink up the tree, right? So there could be benefits to being able to know the height, and make sure that you're always maintaining a tighter binary search tree, rather than just keep on letting it kind of spider out.

[00:06:27]
Because if you do a bunch of inserts, guaranteed you're not gonna get a complete binary tree, right? You're gonna have a pretty spidery one, which means that your find, is gonna be much slower. But if you do your deletes right, you could shrink back up your tree. Does that make sense?

[00:06:43]
It's kind of a pretty big, is a fairly big topic right here, and it's not super duper simple, but it's also super nice, I really like it a lot