Self Balancing AVL Tree

[00:00:00]
>> Let's talk about self balancing trees. So we're gonna talk about something called AVL trees which is going to respond to that problem that we just had that we have these kind of worst case scenarios that we have to go through 100 hops and 100 numbers. An AVL tree is the same as a BST.

[00:00:23]
So every AVL tree is a BST. So that's one thing to keep in mind. Not all BSTs are AVLs. So an AVL tree is a specialized version of a binary search tree. And the good news here is you can add numbers in order, and it'll automatically bounce out your tree for you.

[00:00:41]
It has a self balancing mechanism built into the tree. So AVL trees are not necessarily the best ones. In fact, I would venture to say that you'll never use AVL trees directly in production as well. But it's a really good, perhaps most simple self balancing tree that we can talk about.

[00:01:01]
If you're wondering what AVL stand for, it stands for the last names of the authors, which is Adelson, Velsky and Landis, right? Hence, AVL. Okay. So the nice thing about AVL trees is, things mostly work the same. The deletes work the same, the ads work the same, the finds all work the same.

[00:01:31]
All that stuff ends up being exactly the same except for one key part. So when you go down and you do an ad, you'll actually perform what's called a balancing. And that's actually going to allow you to make sure they have a balanced tree. So let's take a look at this one here.

[00:01:52]
I'll just make this full size so you can see. So we're going to add a number here. So the first thing you do is you're gonna do exactly like a BST. You're gonna find where it should go, okay? So we're gonna add a child to the eight here.

[00:02:09]
Okay, so I added nine here to the eight, right? So this is still a valid BST right now, right? Nothing here is a miss for a BST. However, this tree right here ends up being out of balance. This is much lower than like say, the 71 over here.

[00:02:31]
So we wanna do some sort of balancing to make sure that these lookups stay really fast. So, what it's gonna do is it's gonna go up the tree and say, hey, is this leg balanced? Is this leg balanced? Is this leg balanced? It's gonna land on the seven, and the seven is out of balance.

[00:02:50]
And the way we're gonna define our balance is the right child has two height difference from the left child, right? So the left child height of the seven is zero, right? It has no left children so it has no height on its left side. The right height, it has eight and nine, right?

[00:03:10]
So it has a right height of two. So it's going to balance itself through what's called a rotation, okay? So let's kind of just step back through that, right? So it's going to move eight to be the root of this little sub tree. It's gonna make seven the left sub child, and nine the right sub child.

[00:03:36]
So you can see there now it's balanced and now everything is balanced, right? And there you go. So that's called a single rotation. I think it's technically a left rotation. As you might imagine, you can rotate the other way, right? So, the right child is heavy. But as you may imagine, you can also have the left child be heavy in which case, we would rotate to the right.

[00:04:14]
And that's it. That's the only difference here that we're really concerned about, is these rotations. So before I advance there, does anyone have any questions about single rotations? At least conceptually. All right? So let's talk through what the rotations look like. I have five, eight and I try, which is currently a valid AVL, right?

[00:04:51]
This is a left height of zero and a right height of one, right? Which is not too different, right? It needs to be two different so if I had like a nine here for example, right? This is now not a valid AVL tree because this five is out of balance.

[00:05:06]
Okay, so I call ad with nine. I do a normal BST add which puts it down here on node C. Now, I have to do a balanced check on my way up. So whereas before on the BST you and I did a iterative add, right? So we used a while loop to find the correct place to put the node.

[00:05:31]
On an AVL tree we're gonna do it recursively because on the way back up, in fact you can see it here. So I add nine. And then every node on the way up, you can see where it says eight. It's saying, am I imbalance? Now does it on the seven, it says am I imbalance and it says no.

[00:05:51]
And that's when we start doing the rotation. So on the recursion up, we're asking every single node, are you balanced after I added, okay? So, check the balance of node C, left height is zero, right height is zero. Node C here is in balance. On node B the left height is zero, the right height is one.

[00:06:15]
So node B is in balance. It checks on node A. And it says the left height is zero, the right height is two. That's a difference of two, so this is out of balance. So, it's unbalanced, right heavy, child is right heavy. When I say child is right heavy, it means that it goes five, eight.

[00:06:38]
And then its child is on the right, not on the left cuz that ends up being important, right? So if this was five, eight, seven, we would have to do something slightly different. In other words, if it's a straight line like this, we're gonna do a single rotation to the left.

[00:06:56]
See, I always messes up. This is technically a right rotation cuz the right child is heavy. Anyway, doesn't matter. So what we're gonna do here is this is the entire logic of a rotation diagram, step by step for you, okay? So node A, yeah, you're gonna swap the values of node A and node B.

[00:07:23]
So five is gonna go here and eight is gonna go here. Make node B's the left child of A. So you're gonna move node B to B here as the left child of node A. Make node C, the right child. So node c will be the right child of node A, okay?

[00:07:50]
We're gonna move node B's right child to its left child. In this case, they're both nulls so this step ends up not doing anything. And then you're gonna make node A's original left child, which was null in this case. So this is also not a necessary step. The left child of node B.

[00:08:05]
And then you just need to make sure you update the heights on all of them when you're coming back out. So this is what you end up with. Where eight is the root, five is over here, and nine is over here. The thing that I wanna make sure you understand here, notice that node B's value used to be eight.

[00:08:22]
And node B's value down here is now five, right? So we do swap some values around, whereas these nodes are, yeah, the nodes are changing values. Make sense? Good so far? All right. So I showed you a right rotation, right? Which is moving from the right to the left.

[00:08:47]
As you might imagine, the left rotation is the exact mirror of what I just did, right? Okay? So this is the generalized formula here. Like literally I went line by line in my code and I diagrammed out. If you follow these steps exactly, this works in every case.

[00:09:12]
Now let's talk about double rotations. I should say, this is the hardest thing you're gonna do today. I probably should have led with that, but here we are. [LAUGH] All right. So, double rotations. We are going to add nine to this array or to this BST, right? So we have this existing tree, we're gonna find where to add nine.

[00:09:44]
Nine should go here, right? And so we end up with this tree. As you can see here, number seven here is out of balance. It has a right height of two and a left height of zero. So this is not gonna work, we need to perform a rotation.

[00:10:04]
Now, here's the problem. If you notice, if you remember the other one, this line was straight so it had a right child and then a right child, right? That's allowed us to do a single rotation and everything was fixed. The problem with this is if it's a bent one, right, so you go right then left.

[00:10:25]
This is a right rotation but a left child heavy. So we actually have to do what's called a double rotation. Now, the good news is you're just using the same rotation method just twice. So the first thing we're gonna do is we're gonna do a right rotate or sorry, a left rotation on this 11.

[00:10:56]
And it doesn't actually show, it does, okay. All right, so we're gonna do that right rotation. So now we're right heavy again, right? So we made nine the child here and 11 the right child. So basically, we switch to these positions, right? So now nine is coming over here, 11 is going down here.

[00:11:24]
And now we have a straight one, and now we can just perform a normal right rotation on seven, and then we end up with this rotation here. So that nine is now the root, seven is now the left child and eleven is now the right child. And everything is balanced, and happy.

[00:11:49]
Hold on. So just to, yeah, feel free to watch that a few times to kind of understand exactly how the rotations happen. So one right rotation, sorry, left rotation on the nine, and then a right rotation on the seven is technically how that works. So let's just visualize why you do it this way.

[00:12:25]
So I have five and eight, right, and I wanna add seven. So now I have a right heavy child on the five. So if I perform a single rotation just on the five here, I end up with this tree where eight is the root, five is the left child and seven is the right child.

[00:12:49]
Still out of balance, didn't help, right? I just have a different problem now. So the correct thing to do here when you have a tree like this, where seven is the left child, is I'm gonna call right rotate on eight. It's literally just the same method, right? I don't have to write anything special, I just call left rotate, [LAUGH] call left rotate on eight.

[00:13:12]
So now I have five, seven, eight, and I have this straight line here, right? And then I call, right rotate on five here, and I end up with five, seven, eight, like that.