B-Tree Leaf Deletion

[00:00:00]
>> Deletion is a little weird, okay? So we're gonna kinda do it in like phases because there's a lot of rules. And so the simplest one we're gonna look at is leafs. They're not simple they're actually really, really, really, really hard, easy but hard. So leafs, the simplest one we can think of is if we have Kmin + 1 keys, right?

[00:00:24]
We're somewhere between kmin + 1 to kmax. If we just delete any of the keys, right? 10, 20, 30, let's just say we have we're on an order 4 tree that means our minimum is one. If we were to delete any of these keys, well, that's actually really, really easy.

[00:00:40]
Because you just just delete the keys there's no children, you just delete the key. Get out of here because we maintain all of our requirements. I'm gonna bump this up to a because it just feels nicer. I think it's easier to see we're gonna do an order five tree for the deletion part of things.

[00:00:56]
Which means I have to do a lot more writing but I just think it's a little bit easier to kinda see how these things work out. All right, so we're still at our minimum which is two, so we're good. Now, let's just draw out some things here. I'm gonna go one, two, three and let's get rid of this one.

[00:01:15]
And that means we have to have what, five up here? We have to have 15 right here and let's have 25 right here. Yeah, that feels good. That feels just so good. We got to have this one that means we have to have more keys. Let's not do that.

[00:01:31]
Well we do want to do we do, we do, we do, we do which means we need to come up with something right here which will be [SOUND] this one's not right. We need to do 12, we need to do, we'll do 16, 17 and then this last one will be 27, 28.

[00:01:52]
Perfect and let's actually also add in an 18. All right, I'll rewrite it for you guys 16, 17, 18, beautiful. All right, so now let's pretend we're deleting 28 or we're deleting 12, all right, 12. We don't even, we do have 28 on here. We're deleting 12. Well, we are at the key minimum, right?

[00:02:15]
If our order's five our minimum is two can we delete this key? I mean the answer is yes overall but can we just delete it by just removing it? No, not at all. So what we do now, remember this is where we get to use our terms again.

[00:02:31]
I erased it. What a, just a loser of man. Imagine if I had it still up here. We need our in-order predecessor or our in-order successor to be able to do this and it's kinda like that but it's a little different but it's the same thing. It's gonna be effectively our in-order on our sibling on either side it's the exact same thing.

[00:02:53]
So either we're taking the largest of the small or the smallest of the large when it comes to leafs. We're gonna say, hey, can we borrow that? So case one of course we already talked about, three cases let's get rid of these cases. Let's [SOUND] move this to four cases.

[00:03:11]
Four cases, one Kmin + 1 we already did that one that's easy-peasy. The next one is Kmin with left Kmin + 1. All right, so your left-hand side has enough keys to be able to spare, which means what we're going to do is we're gonna take the three and we're gonna move that three up to where the five is.

[00:03:43]
We're gonna take that five and move it to the front of the list down here, because when you take from the minimum side, you move it to the front of the list. So now, can we delete the 12 easily? Yes, we've reduced case two to case one, case one, goodbye, you are dead.

[00:03:59]
All right, so now we're gonna do the exact same thing except we're gonna delete ten now. All right, so this leads us to case three, which is we are at a Kmin with a right Kmin + 1 fantastic. That means we need to take the smallest item from our larger sibling.

[00:04:21]
You can't go two over, you have to go one over. Maybe there is a way you could find a way to snake it through but we're not gonna do that because that would be just crazy talk. So what we're gonna do is we're gonna take 16, we're gonna move it up to 15.

[00:04:36]
Notice we're not violating any rules right now, right? We are maintaining all the rules of that it's fantastic. So that means our 15 comes down and adds to the end of the list because again it's on the larger side. The larger side goes to the end of the list, the smaller side goes to the beginning of the list.

[00:04:53]
Choose your data structure wisely. Now we can delete ten because now we've reduced case three to case one. Beautiful, delete, you're dead. All right, so now that we've done that, we want to delete yet again, 15. What are we gonna do here?
>> Do it twice,
>> Do it twice, wrong, great idea, wrong.

[00:05:18]
Okay, I love the passion you have but it's incorrect. I want you to look at this list just imagine it for a second. What if the files were in the computer? All right, they're right there. It's already right in front of you right now. We could actually create a list called one, two, three, five, 15 we are going to merge it.

[00:05:40]
This right now is in violation it is Kmax + 1. This will always be Kmax + 1 because we did came in twice plus one more so that's always a violation rule. It's always Kmax + 1 which means now that our three came down and we're trying to delete 15.

[00:05:58]
15 is gonna go away and we're gonna have a new tree so let me just erase all of this. Three goes out of here and now we are sitting like that it's now been deleted. All right, fantastic we've done it. Now there comes a point where a violation can then happen at your next level.

[00:06:21]
Which means that as you delete a leaf, you're then going to have to recursively walk back up the item until we find where a violation has happened. Now again, you could do the exact same algorithm. You can look to the left, you can look to the right or you merge upwards.

[00:06:40]
You just keep on playing the same game over and over again as you fix the tree upwards. Awesome, everyone's feeling good about that one. I'm feeling pretty good about that one. Yeah, it's pretty fun. This is pretty fun, all right. So that is deletion at a leaf level I forgot the right fourth case.

[00:07:00]
Fourth case is merge. Look at those ease those easy, beautiful, all right. No, this is not middle out. Middle outs when you grow, right? Because when you grow you literally take the middle when you take it out so there you go.