Self Balancing AVL Tree Exercise

[00:00:00]
>> A lot of information. I'm gonna give you an opportunity to do this. But we're gonna walk through this kinda piece by piece first and then I'm gonna give you some time to do the exercise. So let's pop over to our CodeSandbox here. And we're gonna pop into AVL and do AVL test here.

[00:00:22]
Most of your actual logic is gonna live in the node. So I'm gonna say here we're going to code a constructor, And we're gonna say this.root = null, We're gonna do an add, It's gonna take in a value. And actually, let's just go ahead and do this together before I let you get started.

[00:00:52]
I'm gonna say if this.root, then this.root = new Node(value), else what you're gonna do is you're gonna say this.root.add(value). And then we're gonna put all of the add logic on the node. Okay, and then we're gonna put two object method here, if you wanna use that visualizer again.

[00:01:27]
That's just going to return this.node, return this.root, rather. Okay, this is the complete tree method, you don't have to do anything else here. That's it. Okay, on the node, We're gonna put a constructor, There we're gonna say this.left = null, this.right = null. We're gonna say this.value = value, so you also need to accept the value here.

[00:02:21]
And we're gonna say this.height = 1, cuz we have to keep track of a height to know when we need to rotate things, right? So make sure when you're adding new nodes to your tree, make sure you're updating the height on the fly. Okay, you're gonna have an add method, Which is gonna take in a value, this is recursive, right?

[00:02:48]
So, you're gonna have this add method called the add method on its children, right? So if I have going back to here, Let's look at this tree I guess, if I call add on 15, what I'm gonna do is, I'm gonna call and I'm gonna add let's say 13.

[00:03:09]
I'll say tree.add(13), and then I'm gonna say this.route add 13, it's gonna call this on its left child. So it's gonna say this.left add 13, this.right add 13, right? And it's gonna just go down the tree until eventually finds the correct space, right?
>> Would this be the recursive method that you talked about for the binary search tree?

[00:03:32]
>> If you did the recursive way with the binary search tree, this is the same logic, mostly, right? It's, you're definitely on a good start there.
>> That's okay.
>> Cool, good question. So, basically here you're gonna decide to go left or right. It's gonna look a lot like that while loop that we wrote if you wrote it like I did.

[00:04:02]
Okay, Until eventually you're gonna find the right place. Find the correct place to add, And again, make sure you update, you're updating heights, okay? The very last thing that you wanna call on this add is this stop balance method. Okay, and then we're gonna make a balance method.

[00:04:56]
You're going to basically on every node, you're gonna ask, is this node out of balance? By checking the highest, right, remember if it has two or more different switches, if it has two difference, right? Then that's you need to call a rotate. So, So if it is out of balance, if it's not out of balance then do nothing.

[00:05:31]
If not out of balance do nothing, if it is balance ask is, All right, do I need to do, do I need to single or double rotate? So, if single just call rotate on self, if double call rotate on child, then on self.
>> On line 16 is that supposed to be if it is balance or if it's out of balance?

[00:06:23]
>> Yeah, sorry if it is out of balance. Thank you, appreciate it, Okay? Then, we're gonna write two methods down here called rotateRR, And rotateLL. Why they're called RR and LL I'm not exactly sure, but I think everyone calls them that so I just continue to call them that.

[00:06:56]
So, You call rotateLL if the left child is heavy, you call rotateRR, if the right child is heavy. So it's from the right to the left is right, from the left to the right is left. And then when you call these rotate methods, you're gonna have to do some updating on the heights as well.

[00:07:20]
So I wrote a function called updateInNewLocation(). So if you're doing an RR, sorry, if you're doing a LL, you're gonna say at the bottom of this, this.right.updateInNewLocation(), this.updateInNewLocation(). Rotate and then rotate this one you say this.left.updateInNewLocation() this.updateInNewLocation(). Okay, here, You're just basically gonna calculate the new height, that's all this is gonna do.

[00:08:10]
So basically you're gonna say, do I have a left child, do have a right child? If I have neither than I'm of height 1, in the heights I include myself as height 1. So actually, an empty child I had is height 1, but as long as you're consistent.

[00:08:22]
If you wanna call a node with no children 0, that's totally fine too, I just stuck with 1. And that's really it. So the one thing I wanna say and just re-emphasize too, For the rotate, which is definitely the hardest code to write here, follow, This logic exactly.

[00:08:55]
This is literally line for line the code that you need to write. If you do this, if you can translate this into code, that's the correct way to do rotations.
>> Going down trying to find the final note to add the new value to.
>> Yep.
>> If the current node has just one child on one side and if I'm adding to that single child, I think that's right place for rotation?

[00:09:26]
So I think I can know beforehand, I'm not sure about this, can I? I'm going down trying to find a node to add to and I have this node which has a single child. And I'm sending the value towards that child, there is a rotation waiting to happen, is that true?

[00:09:54]
>> Probably. Are you saying that you can do this without a recursion and you could do it with a loop? Is that what you're asking? So to answer your question, it probably is, I'd have to write the code to really think about it. But the reason why you wanna do recursion is because you want to update all the heights on the way back up.

[00:10:19]
So I guess if you were willing to keep a queue of items that you need to update the heights of. So you could like keep like a list of all the nodes that you've looked at so far, so that on the way back up, you can add them.

[00:10:37]
Then that would probably would be okay, I guess you could just do it on the way down too. Yeah, I guess there are a couple of ways to, write this. This is just the way that made the most sense to me.
>> Just trying to make sense of how this thing works.

[00:10:52]
That's why not because I'm trying to avoid recursion.
>> It's okay. It's still possible to use recursion and know beforehand, right?
>> Yeah, I think that's possible. But again, there might be some unforeseen issue that I'm not thinking of at the moment. But I'd love to see it, so if you wanna try writing it, let me know, that'd be great.