B-Tree Internal Deletion

[00:00:00]
>> So now that means we have to do the other side of deletion, which is deleting internal nodes. That's where things kinda get a little bit more tricksy. But if you remember our original deletion rules, which I just, my goodness, I just happened to delete the original deletion rules.

[00:00:15]
There's only three cases in deletion world. Case number 2, you have to use the in-order predecessor or the in-order successor rule. Guess what we're gonna be doing again? Exact same rule. It's the same thing. It's just the same thing cuz it's all just this. It just boils down to the same problem, which is you have a spot in which one side is less than, one side's greater than, or the value.

[00:00:33]
You can do the same operations, the same maneuvers. I wish it had some super cool name for the maneuver, but it doesn't. All right, so I'm just gonna erase this and make it look prettier, and we're gonna do some deletions. You're dead. What is that from, by the way?

[00:00:50]
Is that Zootopia? And you're dead. Yeah, I think it's Zootopia. I think it's Zootopia. I think it's Zootopia. Anyways, doesn't really matter. Okay, it doesn't matter. All right, so I'm gonna just put an x over here. I don't think we need to consider or worry about that tree for now.

[00:01:06]
And so I'm gonna have [1, 2, 3], [13, 14, whoa, that's a tight one right there, 16. Then let's go. What do we wanna do here? What do we wanna do here? Let's go, [17, 18, 19], why not? I'm just gonna put an x over here. I don't think we actually need to worry about that one.

[00:01:29]
So let's delete 16. So case 1 of our internal deletions is pretty straightforward. Case 1 is in-order predecessor. All right, which means that if we are deleting 16, we are gonna go to our smaller side, largest element, and we're going to swippity swap it out, okay? So that means the 15 is gonna go where the 16 is, the 16 is gonna go where the 15 is.

[00:02:03]
And then we've now reduced ourselves down to the simplest possible case, which is a leaf node delete. And so now we just replay all the rules of a leaf node delete. And this only works if your in-order predecessor, technically, it comes to a point where you break this rule, but this only works if your in-order predecessor has kmin + 1.

[00:02:23]
So this creates a very simple deletion. You just swap, delete it out, very easy. Number 2 is in-order, Successor. Do the exact same thing. If we were to delete 15, again, this place, this is just the worst place to be in this. You go down, you find the in-order successor, you swap it out, put a 15 right here, put a 17 right here.

[00:02:49]
And now, very simple delete, case 1 deletion. Again, this is only if you have kmin + 1 or more keys. Okay, so we're looking pretty good. But what'd happen if you don't have that, right? And now we wanna delete 17.
>> Merge.
>> Merge, merge is a possible solution.

[00:03:12]
Now, the problem is that when you look at material on this, they always talk about it in this kind of sense. Which meaning that you're talking about something internal that has leaf nodes right below the internal, which is kind of unfair just to say we just simply merge this, right?

[00:03:30]
Cuz we merge it, delete it, and that's that. I would probably be pretty crappy of me to leave it right here. Though everything you look at pretty much leaves it right here, that's not technically what should happen. Because what happens if you're deep in the internal tree? You can't just grab your in-order predecessor and your in-order successor nodes and merge them, cuz they could be two completely separate subtrees, and you just break everything and all things would fall apart.

[00:03:58]
Really, you should swap it out with one of them, and then run this algorithm at that point where you merge back up the tree. But in this case, since it's simple, and we can look at it, we're just simply going to just do this right here. We just merged those two nodes, and now we have one less node.

[00:04:16]
And this just keeps on going over and over and over again. And that's really it. That's the deletion part of B-trees. Everything else is the same thing. You just keep on merging, you shrink down, you grow up. Grow up, [LAUGH] I like that. That's great. I'm gonna use that more often.

[00:04:36]
All right, well, that concludes most of the tree portion of the algorithms class. Is everyone happy about that? Are we happy about the trees? The trees are great? Trees are really cool. There's obviously more things you can do with the tree. But this really covers the basic idea of all advanced usage of trees.

[00:05:02]
You now understand B-trees, for the most part. Very hard to implement, obviously, lots of little rules, lots of easy ways to shoot yourself in the foot. You're pretty much walking just on guns that are shooting, it's very, very easy to screw it up. I suggest a lot of tests.

[00:05:16]
This is the only time in the universe that I would ever suggest something like TDD because you know the input and you know the output. I would never suggest this professionally, okay? Don't let anyone know I'm suggesting this. But for these type of things, if you're ever implementing a problem that can be boiled down to such a simple in and out, always use TDD for that.

[00:05:37]
Besides to that, don't you do it, don't be a fool. Professional advice, with me, teaching an algorithms class. Also, never take advice from anyone that writes exclusively on a whiteboard. That is just like, they just haven't been out in the real world for a long time. I think I've created you a logical conundrum.