Four Semesters of Computer Science in 5 Hours Exercise 9 Solution Part 2

Transcript from the "Exercise 9 Solution Part 2" Lesson

[00:00:00]
>> [MUSIC]

[00:00:03]
>> Brian Holt: So now let's do our balance method.
>> Brian Holt: So const rightHeight is going to be pulling out (this.right) this.right.height. And this is a ternary expression, for those of you not familiar with them. Basically it's saying, if I have a right child, right, this is an if statement, then grab its height, otherwise its height is zero.

[00:00:32] So if I have no child then my height is zero, but if I do have a child then its height is whatever its height says it is. And same thing for left height.
>> Brian Holt: Okay.
>> [BLANK-AUDIO].
>> Brian Holt: Okay, this is just the best part of it [LAUGH], so if (left height).

[00:01:04]
>> Brian Holt: Is greater than rightHeight + 1.
>> Brian Holt: Then const leftRightHeight. [LAUGH]. And same deal here, (this.left.right).
>> Brian Holt: Then we're gonna say, this.left.right.height:0. Same idea with leftLeftHeight (this.left.left) this.left.left.height:0. Okay, so now we're pulling these out because we wanna check if you do a double rotation or just a single rotation.

[00:01:53] Cuz at this point, we've identified if we get into this block. Where they're out of balance enough that they need to be balanced, right? That's what this block identifies. And now we're gonna identify, are you left heavy or right heavy? And if so, then we need to perform a double rotation.

[00:02:11]
>> Brian Holt: Okay.
>> Brian Holt: What was going on there? Thank you, Spotify.
>> Brian Holt: Okay, so pulled that out.
>> Brian Holt: So, now we're gonna ask, if (leftRightHeight) is greater than leftLeftHeight. Then we have to perform our double rotation, this.left.rotateRR which is our right rotation method. Okay, so that's like, okay, perform your right rotation first on the left child.

[00:02:56] Otherwise just rotate left, well not otherwise. So we're always going to rotate left, but sometimes we're gonna have to rotate right as well, right? That's the gist there.
>> Brian Holt: Else same idea, const rightRightHeight
>> Brian Holt: Okay, so, suffice to say that it's just a ton of these checks to say.

[00:03:28] So let's actually just walk through the finished code here. Otherwise, we're gonna spend the rest of time doing this.
>> Brian Holt: Okay, so.
>> Brian Holt: Go left, left.add, this all looks familiar hopefully to you, we just did that. We can get rid of that, don't need that.
>> Brian Holt: rightRotation, leftRotation, right, otherwise we're doing rightRightHeight, rightLeftHeight.

[00:03:57] If the (rightLeftHeight) is greater than the (rightRightHeight). Then you're gonna have to do the left rotation, then you're gonna do the right rotation, right? All right, so now let's look at what the actual rotations look like. Told you they're kind of ugly, right? Grab the value before, grab the left before.

[00:04:15] Then the value is assigned the left right.value, left is assigned the right. Right is assigned the right.right, left.right is assigned the left.left. left.left to leftBefore, left value to left valueBefore. updateInNewLocation is just gonna go and make sure all the heights stayed in sync. And same thing with, you're gonna have to do on the left child and the current child.

[00:04:36] And left rotation is just again a mirror image of that.
>> Brian Holt: Okay, this is what it looks like to make sure that the heights are correct. So if you have no children then your height's 1. And then, the same questions they were asking up above, which is, if I have the right child then make sure I'm getting the right height.

[00:05:00] Same thing, else, make sure that I'm getting the right height for my right child, right? [SOUND] [LAUGH] That's a lot of words, but hopefully, conceptually, does this make sense about what we're talking about here? And again, the nice part of that is look at this tree, it's really imbalanced.

[00:05:24] In fact, I wonder if I can show you how actually cool it can really be.
>> Speaker 2: Why wouldn't that be, you set this root from the actual tree?
>> Brian Holt: Cuz you never do, cuz we're not doing any deletes, right?
>> Brian Holt: So, if you go up here to.
>> Speaker 2: Doesn't the root need a change, though?

[00:05:51]
>> Brian Holt: It can, but because we're just swapping values, right, remember, we're not actually moving the root node. The root node is actually always staying in place, we're just moving the values between them, right?
>> Speaker 2: Yeah, yeah. Yeah.
>> Brian Holt: Let's see, so if I say.
>> Brian Holt: Sorry, come down here after that but before the unit tests.

[00:06:19] And I say, var x= new Tree. Okay, and then I say, range (255).map (x.add). Let's see.
>> Brian Holt: x.add(index) and then I say render.
>> Brian Holt: No, that's still not gonna work. No x.
>> Brian Holt: x.
>> Brian Holt: Can't remember how to do that off the top of my head. Anyway, I'm going to show that you start getting into these giant trees and they still in the being extremely flat which is exactly what you're looking.

[00:07:32] Wish I could remember how to do it off the top my head, anyway.
>> Speaker 2: So kinda related to that, one of the questions from Drew is assuming AVL trees are slightly slower due to the rebalancing. Would you ever want to use a simple binary search tree and then just set it to occasionally go in and optimize by balancing?

[00:07:54]
>> Brian Holt: You're talking about batching at that point and scheduling. And my theory is that all performance problems eventually come to a scheduling of some sort. Not all but many, many of them do. The answer is you probably wouldn't do it with AVL trees because once you get out of balance it's actually pretty expensive.

[00:08:15] If you get way out of balance it gets really expensive to get back in balance. And to my knowledge, there's no simple way to do that. At that point, you probably just destroy the tree and recreate it. Which, in and of itself is really expensive. So to answer your question, not with AVL trees but I can see you doing that with another data structure.

[00:08:39]
>> Brian Holt: Okay, any other questions before we just bury that? Bury that under, my God, we just did that? Okay.
>> Speaker 2: There was also a question about whether you're reading Dr. Seuss during this.
>> Brian Holt: I am. Actually, I got that from the binary search tree in the hat.
>> Speaker 3: [LAUGH].

[00:09:00]
>> Brian Holt: That's funny. Yes, that actually does sound like Dr. Seuss.