This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Double Rotation" Lesson
[00:00:00]
>> [MUSIC]
[00:00:03]
>> Brian Holt: Let's take a look at a double rotation now. Okay, so we have 5, 8 and we're gonna add 7. So now we have kind of this bent look, right?. We're gonna have to perform a right rotation, right, because this 8 has to come over. But unfortunately, if you perform a normal rotation, you end up with this.
[00:00:25] If you do a single rotation just right off the bat, that actually doesn't really buy you anything cuz it's still out of balance, right? So, you have to perform what's called a double rotation. The nice thing about a double rotation is what you do is you do a left rotation on one of the children and then you do a right rotation on the root node, right?
[00:00:41] So you just do a left rotation on one of the lower kids and then you just do a right rotation on the parent and that's it. Okay, so the way you tell you need to do this double rotation. Is that I need to do a right rotation that but it's left heavy, right?
[00:00:57] So when I say left heavy, I mean the left is greater than the right. It doesn't mean it's out of balance, right, because in this case, 8 is not out of balance. It's just left heavy, right, but I'm gonna perform a right rotation. In other words, if you see this bent look to it, that means you need to do a double rotation.
[00:01:15] Whereas if it's a straight one like this, then it only needs to be a single rotation. So again, if you do a right rotation but it's left heavy, you need a double rotation and vice-versa. If you need to do a left rotation and it's right and the child is right heavy, then you have to do a double rotation.
[00:01:36]
>> Brian Holt: Okay, so again, this is what it looks like in terms of that logic. So nodes C, when you add it, right, this it right after you add it. This is children are zero zero, so it's imbalance. It's children is zero and one, right? So it's imbalance being node B.
[00:01:58] And then node A we get, it's right child is out of balance, right? Or it's out of balance because it's right child has height two and it's left child has zero. But unfortunately, node B is left heavy, but we need to do a right rotation. So that's when we know it need to do a double rotation.
[00:02:17] So what we're gonna do is were gonna call a left rotation on node B. And all is gonna do is it's gonna basically make this 5,7,8, so you can perform left rotation and it's just gonna make it look like this. So you're gonna make it basically a straight line.
[00:02:39] And then after that we can easily do just a normal rotation and everything works out just great. And you'll end up with 7, 5, 8, right? And that's eventually what you're gonna end up with.
>> Brian Holt: So that's the idea of what's happening with the double rotation. So this is not what we want, right, this is what it looks like when it's broken.
[00:03:07] Okay, so we have 5, 8, 7. So we added 7, that's fine. We find out that we need to perform a double rotation, right? Because we figured out that it needs the right rotation and it's left and it's the right child is left heavy. Again, heavy meaning that the left side is greater than the right side.
[00:03:28] If there was another child here like 5, 7, 8, 9, right? And there is something off here. Then that be fine, right? Because it wouldn't be heavy on one side. Except you would never have that happen. Never mind, disregard that. Okay, so
>> Brian Holt: We've discovered that when you do a right rotation, it needs to be double rotation because 8 is left heavy, check.
[00:03:55]
>> Brian Holt: So first thing we're gonna do is we're gonna perform a left rotation on the left heavy right child [LAUGH], which means 8. We're gonna perform a left rotation on this one. Don't worry, I hear myself. I hear the things that I say
>> Speaker 2: [LAUGH]
>> Brian Holt: And I know it's complicated.
[00:04:13] I'm so grateful I already learned this [LAUGH]. Okay, so after performing that it's like literally the same logic, you don't have to have any sort of special functionality. You just need to say do I need to perform a left rotation or right rotation on the offending child, right?
[00:04:34] And then that's it. So while this is conceptually difficult ,the code for it is literally an if statement, do I need to do an extra rotation, yes, do the extra rotation. And that's it.
>> Brian Holt: Okay, so I performed that left rotation on 8 and I end up with this, right, which is what we expect.
[00:04:53] Now, it's a right rotation with the right heavy child, which is A plus. We can do that, no problem and you end up with this.
>> Brian Holt: So again, the real problem code here to write is the left and right rotation. It's the actual, this part right here. This is far and above the stuff that it's hard to do and really just hard to conceptualize and difficult to get out and cut.
[00:05:21] But once you have the left and right rotation functions using, it's just application of those two different functions.
>> Brian Holt: Okay, so I swear to God, that's it. [LAUGH] So it's just nailing down those rotations is a pain. So, to be totally honest, even though we're not doing deletes today, but even deletes follow this pattern.
[00:05:46] The only issue with deletes is as you go up the tree, you have to keep asking every step of the way, do I have to perform a rotation? Because deletes can get things way out of whack, right? Whereas when you're doing ads, it's only a single rotation or a double rotation every time.
[00:06:01] There's nothing you can do to an AVL tree to make you have to do more than that, within that.