Self Balancing AVL Tree Solution

[00:00:00]
>> So let's go ahead and do the add first. So we're gonna say if, This. Or we'll say if value is less than this dot value, Then we're gonna ask if I have a left child. So if this dot left, Then we're gonna call this dot left dot add with value and recursively go down the tree here.

[00:00:34]
Else, This dot left equals new node, Value. Then here we need to adjust the heights a little bit. So we're gonna say if no this dot right. Or this dot right dot height, Is less than this dot left, Dot height, Then we just need to make sure that say this dot height equals this dot left dot height plus one.

[00:01:28]
So if we're modifying the height here as we're going, we wanna just make sure that we're updating it as we go. And we're gonna have the mere logic in the else but just for the other side. So this is go left. And this is go right. So we're gonna say if this dot right, we're gonna say this dot right dot add value.

[00:01:58]
Else this dot right equals new node with value. And same logic here. If this dot left, Or this dot right dot height is greater than this dot left dot height. Then we just wanna make sure that we say this dot height equals this dot right dot height plus one.

[00:02:35]
So that's all of the add right there. As you can see here it looks. This is basically just a BST add done recursively with the addition of we're worrying about adding heights at the end. Otherwise this is exactly the same as the idea of adding an add to a BST recursively.

[00:02:55]
With the only difference being here that we call balance down here. Okay? I'm just gonna delete all this. So the first thing we're gonna do in balance is say const right height is assigned this dot right. If we have one, then this dot right dot height. Otherwise it's zero const left height is assigned this dot left if we have one.

[00:03:30]
It's gonna be this dot left dot height, Or zero. So we're gonna say if left height is greater than right height plus one. Meaning that there are two different, right? There we're gonna say const. This is the part where we need to check if we need to do a double rotation.

[00:04:01]
So, bear with me for a second. We're gonna say const left right height is assigned this dot left dot right. If that exists, then we're gonna say this dot left dot right dot height or zero. Same thing here for left, left, height const. Left, left, height is assigned.

[00:04:34]
This dot left dot left. And if that exists, then we say you could also do a what is it? Nullish selectors I think that's what they're called. No, I'm thinking the wrong thing. Where you just say, question mark like this. Can't remember the name of that feature, anyway.

[00:04:56]
>> I believe it's called [INAUDIBLE] stuff like that.
>> Null coalescing, that sounds right. I believe you [LAUGH]. But I don't think that's enabled in Code Sandbox right now by default. So we're just gonna do it this way. Dot left dot height or zero. Now we can check if this is basically bent.

[00:05:19]
If it's bent, then we're gonna do a rotation. So what we need to say here is if, Left right height is greater than left left height, then we do this dot left dot rotate RR. So this is a double rotation here. If it's not, then we just skip that part and we just say this dot rotate LL.

[00:06:04]
So if we need to double rotation on the left child we'll rotate to the right or from the right. And otherwise, and no matter what, if we're inside of this block, we're always going to rotate LL on the node itself. Here we're gonna say else if, Right height is greater than left height plus one.

[00:06:31]
Then we need to do a rotation. And same thing here, const right right height is equal to this dot right, Dot right this dot right dot height, Or zero. Then const right left height is assigned this dot right dot left. We'll say this dot right dot left dot height, Or zero.

[00:07:22]
Then if, Right left height, Is greater than right right height. Then we're gonna say this dot right dot rotate LL. And then this dot rotate RR. This is a double rotation. So this is the all of the logic for balancing that we run on on the node. Now we just need to go program these two functions.

[00:08:18]
Rotate LL and rotate RR. But the nice thing notice again, this logic and this logic, it's the same function, right? Still works the same way. Which is nice, we don't have to code four different ways of doing rotations. It's just two ways of doing rotations and sometimes we do it twice.

[00:08:40]
All right, this is gonna be fun, let's do rotate RR first. So we're gonna say const value before is assigned this dot value. Const left before is assigned this dot left. This dot value is assigned this dot right dot value. This dot left, Is assigned this dot right.

[00:09:21]
This dot right is assigned this dot right dot right. If you're looking at this thing like how do I know how to do this? I looked it up [LAUGH]. I can't remember this from memory. This dot left, Dot right. Well that's nice for the sandbox. There we go.

[00:09:50]
This dot left is assigned this dot right, this dot right is assigned this dot right dot right, this dot left dot right is assigned this dot left dot left. This dot left dot left is assigned left before. This dot left dot value is assigned value before. This dot left dot update in new location.

[00:10:23]
This dot update in new location which I already had down there. Make sure I got that right, this top left. So I actually had these backwards. I did, sorry about that. Cool. So that is a right rotation. And now the nice thing, that left rotation is just the exact mere opposite of what we did there.

[00:11:02]
So const value before is assigned this dot value. Const right before is assigned this dot right. This dot value is assigned this dot value. Sorry, this dot left dot value, left dot value. This dot right is assigned this dot left. This dot left is assigned this dot left dot left.

[00:11:37]
This dot right dot left is assigned this dot right dot right. This dot right dot right is equal to right before. This dot right dot value equals value before. And then this dot right dot update new location and this dot update new location. Cool, so those are the two rotations.

[00:12:18]
Now we're just gonna do the update new location and then we are golden. So if this dot right, And this dot left meaning there are no children for this. Then this dot height is equal to one. Else if, This dot right. Or, This dot left and this dot right dot height, Is less than this dot left dot height.

[00:13:10]
So again, if I don't have a right child or I do have a left child. And the right height is less than the left height which means that we need to take the height from the left. Yep, then we're gonna say this dot height is assigned this dot left dot height plus one.

[00:13:35]
Because we rotated it and now the height needs to be adjusted to whatever the left height's rotation is. So the left's height plus one is right because it's the parent of the child. Else, otherwise we can just say this dot height is assigned this dot right dot height plus one.

[00:13:59]
So basically what we're saying, if this is a leaf node aka has no children its height is one. If the left child has the greater height, then use its height and add one. Otherwise use the right child and add one to its height. Right, because the height is always gonna be one more than one of its children.

[00:14:33]
That was a little bit of code [LAUGH]. Hopefully you stuck with me. Let's see if our AVL tree actually passes unit tests. Let's click play. AVL test is now passing. Cool, I was very afraid it wasn't going to [LAUGH]. So I'll take questions here in just a second.

[00:15:10]
But I wanna show you because I think this is the coolest part. We're gonna copy and paste this tree into our tree visualizer. Save it, I'm gonna pop over to our browser and look at our tree visualizer. Look how flat this tree is. How cool is that, right?

[00:15:39]
It's super flat. So we have max depth of 12. And how many things are we adding to it right now? 950 items in the array, or sorry that we're adding all at once. That's unbelievable. So that means despite the fact that we have 950 things in our tree, at most, we have 12 hops.

[00:16:04]
So that means we can find data really quickly. So let's take a look at this as well. Now you can see, if we're adding 100 things, And we're adding them in order, This makes a very flat tree. So we kind of do away with that problem that we had before where it's super bent.

[00:16:26]
Or sorry, not super bent, but it's super straight. So that's pretty cool too. I'm just gonna add 9,500 here, see what happens. It's probably gonna take a second. So I went from 950 to 9,500 items in my tree. And now at most I have 16 hops to find the item I'm looking for.

[00:16:50]
Again, I think that's really cool. Maybe I just have a warped sense of what's cool [LAUGH].