Four Semesters of Computer Science in 5 Hours Single Rotation

Transcript from the "Single Rotation" Lesson

[00:00:00]
>> [SOUND].
>> Brian Holt: So, let's look at it, like just like, what a basic rotation looks like here. Okay, so let's say we have this tree right here 5, 8. That's a balance tree, right? This has a right height of 1, in the left height of 0, okay? So we'll call, add with 9.

[00:00:21] So we're gonna go five, eight, 9. That makes sense if, because we just had bsts, right? But now, five is out of bounds. Well let's actually, go through the entire process. We call add, go all the way down to 9, added on 9, okay? Then on the way up of recursion, we're gonna ask on every single level, am I balanced?

[00:00:41] Okay? So check the balance of C, left height is 0, this has no children and the right height is 0. So, it's balanced. Node C is balanced. Then we're going to check the balance of node B. The right height is 1 and the left height is 0. Right.

[00:00:59] So it's balanced. But then we're gonna check the balance of node A, and the left height is zero, and the right height is two, right? So, now all the bells are going off. It's out of balance. So now we have to fix it. So what we're going to do is, we're gonna perform what's called a right rotation.

[00:01:19] And this is literally, line by line, the code that you do. Like, seriously, if you go and do this like, one line of code does this, one line of code does this, one line of code just like, I literally spelled it out for you. So it's such a pain.

[00:01:36] Yeah.
>> Speaker 2: Yeah guideable questions online here. The first is, can you go over the how you, like, how do you determine if it's balanced? That's from Ernest. And then second, there's a whole bunch coming in. The second question is, why are we concerned with it being balanced?
>> Brian Holt: Okay.

[00:02:00] Let's talk about why we're concerned. So, we're concerned if it's balanced, because if, it gets out of balance, it becomes very hard to search, right? Which totally defeats the entire purpose of a binary search tree, right? We're doing this so we can have fast lookups. And so, that's why we care if things are in balance or out of balance.

[00:02:21] Cuz if it gets out of balance, we've lost the entire purpose. This becomes life is meaningless, and we wander through life with no purpose. How do we tell if it's balanced? Well, what we're gonna see here, is we're going to keep track of the heights in every single node.

[00:02:39] So you can basically say, hey, right node, what's your height? Hey, left node, what's your height? And then, it's gonna compare the two to see if they're, one side is too greater than the other two or greater than the other.
>> Speaker 2: And I think height, the word height might be part of the confusing part.

[00:02:53]
>> Brian Holt: Okay.
>> Speaker 2: So if you can maybe define that and how you're calculating
>> Brian Holt: Sure. So height is like, how far is it from you to the to the bottom of the leaf node? Taking the greatest path, right? So in this particular case, this has a height of three.

[00:03:09] Right? Because this is one, two. But this is one, two, three? Or any of one of these would be one, two, three. So that's the height, it's the path that you have to take to get to the greatest height that it has. So this is a height one, right?

[00:03:23] This is a height two, right?
>> Brian Holt: Yeah, I mean as long as you, consistently you count it. So that's what I mean by height, it's how many nodes before you reach. The bottom leaf node that, the greatest leaf node that you can get to. The greatest in the sense of, what's the most amount of hops I can take, right?

[00:03:42] So one, two, three. That makes sense?
>> Speaker 3: So after re-balancing really changes the root, in that simplest thing you showed here. God. Visually you're taking like this, and you have pivoting. [INAUDIBLE] [CROSSTALK] This little one through you.
>> Brian Holt: Yeah exactly. I mean, it looks exactly like this. That's what a rotation ends up looking like, and like this ends up being like the pivot or the fulcrum or whatever you want to call it.

[00:04:17] So that's exactly right. So, on any sub-tree that you're performing a rotation on you're changing the root,right? So you're rotating the root around.
>> Brian Holt: Okay, more questions? Okay, great. Okay. So let's talk about yeah, okay, so we've discovered at this point that node A is out of balance, we figured that out.

[00:04:52]
>> Brian Holt: So now, we're gonna do perform a right rotation, and again, this is literally line by line of the code that you need to do to perform a right rotation. So swap the values of node A and B. Okay, so node A and B. This is, the 8's gonna go here, the 5's gonna go here, okay?

[00:05:13] Make node D, the left child of node A. I'm sorry, this is just, there's no way you can really reason through this. You literally just have to, I just got it from the book, right? Okay, so node B becomes a left child of node A. So, node B, so remember this is five at this point, in fact maybe I can just draw this to help you out.

[00:05:38]
>> Brian Holt: Okay, so.
>> Brian Holt: So at this point, what we've done is we've made, this is gonna be eight, this is gonna be five. So we're not changing the nodes at this point, we're actually just swapping the values. You can change the nodes if you want, it just ends up you have to change more pointers and it's a pain in the butt.

[00:06:00] So I recommend just changing the values. Okay, so yeah we swapped those, then make node B the left child of node a. So, now this eight down here becomes this, so it's going to be. Not sure I'm doing this right. Make node B. Sorry, the other way around.

[00:06:26] So, let's just do that again. So, this is gonna be, eight, five and then, eventually what we're gonna do is, we're gonna do, move five to be over here, and 9 is still attached down here. Then we're gonna make node C the right child of node A. So at this point, we have 8, 5, 9.

[00:06:53] And then there's two more steps down here. Because we're at the bottom and we're dealing with leaf nodes, actually, technically aren't necessary, because these children are null. But if they had children, then they would become important. So we move node B's right child to its left child. In this case they're both null, so doesn't matter.

[00:07:14] And we make node A's original left child, right, I know it's crazy. But node A's original left child, which was null in this case. The left child of node B. So in this case, node A didn't actually have a left child. But we would move that down. To be the left child of B, right?

[00:07:34] So let's say, just for argument's sake, we wouldn't perform a rotation in this case, but say it was 4, right? Then basically 4 would come down here, right? That's the gist. And then you just have to go back and recalculate your heights to make sure that, for future rotations that they'd be correct, right?

[00:07:57] And it's crazy, but like that, that's the set of instructions that you have to do to perform a rotation on AVL3.
>> Speaker 2: Do you defined leaf node?
>> Brian Holt: Yes. That's actually a good thing to define. Leaf nodes because this is a tree. Right? The leaf nodes are the last ones.

[00:08:16] Right? So, it's anything that doesn't have children. Right? Leaf node, leaf node, leaf node, leaf node, leaf node, this is not a leaf node because it does have children. This is a leaf node, that's a leaf node, and that one, and that one, right? So all those ones that have no children, those are the leafs, leaves.

[00:08:38]
>> Brian Holt: Good question.
>> Brian Holt: Great. So you end up with a tree that looks like this. So notice that again, because we did some swapping, that, this was node A before and now node A actually still is the root, but we since we swapped the values, that now node A's value is eight and node B is down here with five.

[00:09:09] So, that's how that happened. And that was a right rotation, so as you might imagine a left rotation is just the mirror image the total opposite. So instead of going, you know swap the value of node A and B, right? Well you would still do that, right? That's still fine.

[00:09:28] But instead of making node B the left child, you'd make node B the right child, right? That's just the mirror image of everything happening here. Okay, so unfortunately, that's not the end of the story. But the good news is. You only have to do left and right rotations once, and then everything else is just an application of left and right rotations.

[00:09:50] Sometimes you just apply them twice. Okay? It's crazy but let's keep going and we'll talk about why sometimes we have to perform, double rotations as but what they're called. Okay. So first of all, I'll be okay with single rotations and when how many questions about single rotations before I move on to double rotations.

[00:10:12] Okay. That's it. There's no triple rotations. [LAUGH] Who wants to get double rotation that's what, I swear to God that's it. I tell you to delete. But we're not doing deletes. [LAUGH]
>> Speaker 4: Even making this you're going to be good for a while. Actually, I just missed the first lesson.

[00:10:27]
>> Brian Holt: [LAUGH] Yeah I did promise this is going to be the hardest one though.