M-Way Tree Structure

[00:00:00]
>> So this is where things get a little bit more wild. This is where we really have to apply all of our great understanding. So, all we've been talking about are binary trees, where it's always this situation where there's zero, one, or two children. But why do we have to keep it that way?

[00:00:17]
Can't we have more children? Yeah, probably. But can we maintain the binary search mechanism where we can take advantage of fast search, but we have more splits? The answer, of course, is yes. It's called an m-way tree. Very excite. These things are pretty wild. Everyone says they're used in database indexing, and fast searching, and you can make B-trees.

[00:00:46]
We're gonna get to B-tree, but you can make B-tree lookups and all that fun stuff. But how an m-way search tree works is it follows this exact same principle, except for z may look a little bit different. So you could imagine you have a list of keys at any node.

[00:01:05]
And so I could have, say I have 10, 20, 30, so this is my root node. Now, that means every child off of 10 is going to be less than, whoopsie, that's the wrong way, is gonna be less than 10. All right, that means every child off of here is going to be greater than 10, but less than 20.

[00:01:31]
That means every child right here, same thing, is gonna be great, my goodness, it's gonna be greater than 20 and less than 30. And the exact same thing right here, which is everything right here is going to be greater than 30. That was a terrible circle. All right, look at that.

[00:01:51]
So that is the core concept behind an m-way search tree. One thing that's really nice about an m-way search tree, obviously, you can get a whole more amount of items inside of your tree without a huge amount of height. I think this inherently makes sense, right? Does anyone have any questions, by the way, on this exact item, this m-way kind of setup?

[00:02:13]
>> Does this mean that every node would have 1 plus the length of the array of children?
>> [SOUND] Precisely, so that's gonna be one of our definitions about to happen. For every item you always have, if you have x items in your m-way tree, you'll have x+1 children.

[00:02:38]
I think that inherently makes sense, because you have to be able to have sides here and sides here. Now, in a standard m-way tree, that's not necessarily true. Meaning that you don't have to have, this node just doesn't have to exist, right? A standard m-way tree has no bounds as to what you're doing.

[00:02:55]
Just like a binary tree, you don't have to have both children. You just have to have an adherence to zero, one, or two. An m-way is you have to have an adherence to zero, one, two, three, up to, depending on the m. I forget if the m specifies the keys or the amount of children.

[00:03:12]
I wanna say m specifies the amount of children, so up to m children, and then you'll have m minus 1 keys. I could be wrong on that one. Now that we got that concept down, we're gonna move on to the more exciting part. So an m-way tree has no rules about how you set it up or anything.

[00:03:27]
So I'm going to use an m-way tree and we are going to insert a few values. All right, so we'll just do 10, 20, 30, 40, 50, 69, 70. Okay, so let's just pretend we have a three-way tree. And so we'll start off by inserting these keys. So I'm gonna insert a 10 in here.

[00:03:51]
All right, awesome. Now we're gonna insert a 20. Well, 20 is larger than 10, should I make it its child? Why not, all right? Let's do the 30. Well, 30 is larger than 10. It's larger than 20. You wanna guess the problem we're currently having?
>> We're turning it into a linked list.

[00:04:07]
>> We're turning it into a linked list, and you're like, whoa, whoa, whoa, whoa, whoa, that's not how you do it. Why don't you put all the things in the same right here? Okay, okay, okay, okay, okay, calm down. We'll go 10. We'll put in 20. We'll put in 30.

[00:04:21]
We got it. We're full, so now we put in 40. Well, 40 better hang off here. All right, so now we got 40. We got 50. We got 69. Now we put in 70. Guess what? We pretty much have the exact same problem again, right? So no matter how you just have simple rules to an m-way tree, you're gonna run into the exact same problem that you did with the binary tree.

[00:04:42]
So therefore, what do you think we need for an m-way tree? A tree balancing algorithm. Let's go. Tree balancing algorithm, called it. Man, so exciting.