This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Exercise 9 Solution Part 1" Lesson
[00:00:00]
>> [MUSIC]
[00:00:03]
>> Brian: Let's power through some AVL trees. We're gonna say this.root = null, and we're going to add real quick.
>> Brian: Okay, and so if we don't have a root, sorry if we don't have a root rather.
>> Speaker 2: This is tree of the group?
>> [INAUDIBLE]
>> Speaker 2: Trees [INAUDIBLE] to know, right?
[00:00:31]
>> [INAUDIBLE]
>> Brian: Yeah, so the way I chose to implement it is I actually make the nodes kind of trees, right? So, I had this like wrapper tree class, and then the individual trees are inside it. So it kind of off skates the those internal methods from the consumer for the most part, that's kind of the idea.
[00:00:52] But however, you can make trees, That class as well. Whatever works for you conceptually, I'm totally okay with that. Basically, it puts all the logic into the nodes as opposed to being all the logic being in the tree. So new Node (value).
>> Brian: root.add. Basically, we're delegating to the node, at this point, to be able to create that.
[00:01:29] Okay. And then, if you wanna use the visualizer, just kind of do a toObject. Which is just going to return this.root.
>> Brian: Okay, so now we're gonna make our class Node. And it's gonna have a constructor of (value, left=null, right=null). And say this.value = value;. This.left = left;.
[00:02:08] And this.right = right;. Okay? And then we're gonna do add.
>> Brian: add(value).
>> Brian: So, this is gonna look pretty remarkably similar to what we've been doing before. So, if
>> Brian: Value.
>> Brian: So instead of current, we're gonna be using this right because we're gonna be talking about the node itself.
[00:02:47] So in this particular case, we're gonna go left. If the value is less than the value of the node that were in our cells. Value being whatever we're trying to add right? So, if I have a left child, then I'm gonna call add on the left. Else, I found like one of them supposed to be and so this.left = new Node (value).
[00:03:19] Okay, so at this point I need to ask like this is just like our normal add right and that's totally fine and in fact we could go do right as well right now but we'll do that in a sec. So I'm going to say, if this.right or this.right.height is less than this.left.height that was the other thing, I messed up up here up here in the constructor you also need to construct the height to be equal to one.
[00:03:54] Because you're gonna count yourself as being in your height. You can also not count yourself. Well hold on. You have to count yourself. Okay. So yes you must count yourself in your own height.
>> Brian: Okay, [COUGH] so this is just the logic to be able to make sure that your height is correct.
[00:04:22] So this.left.hight + 1. So basically you're saying, if by adding you I've increased my height, right because if I don't have a right child and I add a, or if I do have a right child and I add a left child that doesn't actually change my height, right, because I was already height one or height two in this particular case.
[00:04:42] Does that make sense, we follow? Let me maybe diagram that.
>> Brian: So, if I have. Let's make this white as well.
>> Brian: So if I have 5 and 6, right? Like say this already exists. And I go to add four. Well if I add 4, that didn't actually change my height in that particular case right because I already had 6 right?
[00:05:14] So 5 was already of height, two in this particular case and adding 4 didn't change it. So, that's the deal there.
>> Brian: Okay, and so that's the only thing that's going to change for adds is just making sure their heights stay correct. Else, and then we are just going to the exact same thing for the opposite.
[00:05:43] So, if this.right then this.right.add(value). Else, we found we were supposed to go. So we're gonna say, this.right = new Node(value).
>> Brian: Okay, and then we're gonna this.left or this.right.height. Right height is greater than this.left.height. Then we're gonna say this.height = this.right.height + 1, okay. So, that's just keeping our height in sync for our right child.
[00:06:38] Then the very, very last thing that we do before we're done with our add is just make sure I get my curly brace in the right place.
>> Brian: Not that one, it's outside that one. Right, this one. I'm going to say this.balance, okay? So now, we've added it correctly, we made sure everything had the correct height, so let's go ahead and go do our balance now.