Balance Factor

[00:00:00]
>> So there are two primary ways in which we fix this problem. Number one is an AVL tree. It is actually the oldest tree or tree balancing algorithm out there. I don't know what A, V, or L stands for. But let's just pretend it's really three people's names.

[00:00:16]
That's really probably what it is or it's probably two people with a dash name. We don't really know what's happening but there's some combination there or somebody that named it after their full name that would be super cool if it's just one person. I am Arthur Van Leuven side and then the third AVL tree that's what I really hope happened but I know it's not I know it's two people.

[00:00:34]
Second, there is red black tree. Red black tree is kinda funny because it was made, I believe, at, if I'm not mistaken, I think it's something park, I think it's Xerox. Xerox was the place that started the red black tree algorithm research. If I'm not mistaken, I forget the company, but I'm pretty sure it's Xerox.

[00:00:54]
And at that time, they only had printers that could print well in red or black and so therefore while drawing it out it became known as the red black tree. That's theory number one which they say the creator said this was true the second one that they say is that the people only had red and black markers and that's from the other creator.

[00:01:15]
And so is this true? I don't know if it's true or not true and I don't know which one's which but I love the fact that there are two competing stories of either the printer company had a printer that only printed red and black well or b [LAUGH].

[00:01:29]
It was that they only had red and black markers which just feels so good I just love it it's just so fantastic anyways fun little lore about those two data structures. All right, so we're gonna cover AVL trees. AVL trees I think the most exciting. They're my favorite data structure to ever implement and unfortunately my teacher wanted to just kick us right in the shin.

[00:01:51]
So what he did is that he said that you cannot use recursion while implementing this AVL tree. So we had to do it with while loops and all that, and it was super hard and it took me, gosh, I spent 40 hours trying to do it all correct.

[00:02:04]
And during the presentation to the TA, he asked it in such an order that it didn't break but I did have one bug I never quite figured out how to do it without recursion. It's very simple with recursion but man, is it hard without recursion? Is just the worst algorithm in the universe.

[00:02:20]
So AVL works in such a way that it rotates the tree every time there's a violation of the ordering. So how it knows the violation of the ordering is it keeps something called a balance factor. And a balance factor must be between -1, 0, or 1. So what does that mean?

[00:02:40]
Let's pretend we have the following tree. Again, I'm just not even gonna write any node values here. I'm just going to just draw things and we'll do the balance factor. This one right here has no children. So it has a height of 0 on either side. It has nothing.

[00:02:56]
So therefore, its balance factor is 0. It's perfectly in line. This one has one child to the left, no children to the right. So typically how you're gonna do it, which I think is the right way, people sometimes mix these up and you can go left minus right or right minus left.

[00:03:13]
It's totally right minus left. Never go left minus right, I'll show you why. So we'll go, right node height minus left node height. And why that is important is that if you do it this way, negative numbers are to the left, to the lesser side. Positive numbers are to the right, the greater hand side.

[00:03:30]
So it kinda matches the feel of the binary tree. Therefore, unarguably this is the correct way to do it. So don't ever listen to anyone that says the moment they say it the other way, just, yeah, just get them right out of the place. You don't wanna listen to them.

[00:03:43]
So that means we have a height on this side of 1. We have a height on this side of 0. Therefore we have a negative 1 or a left leaning note. We do it again. On this side, we have a 2. What do we have on the side?

[00:03:56]
Well, we have 0 0 0, we have- 1, 0, -1, we have 2, 2, 0. Now we start seeing the balance factor, meaning that if I were to add one right here, we would then go to a 0 right here, but this top one does not change at all.

[00:04:14]
We still remain within balance. If I were to do one more on this side, we would then get to 00001112 positive 1, and then we get 3 or 2, 3, positive 1. We are now a right leaning tree at this point. And if we were to add one more, we would start causing violations.

[00:04:37]
So let's just do it. We're violating, here we go. Let's add one more. So we go 000011022. So this is where the violation starts and this is what we need to fix. And so this is the idea of the AVL trees that will start fixing right here. Now when we fix this, it makes cause another violation so we have to keep walking up and doing potential rotations.

[00:05:04]
As we go all the way up the tree, you'll never have to like descend into other areas, you just simply only walk upwards. All right, so we're gonna do this in a very simple way. Let's just do a bunch of notes. I'm gonna go like this 42, 69 and 420 and we're gonna insert these into the tree in particular orders, and we'll have to shape these trees.

[00:05:26]
Okay, so we're gonna start with case one. If I started by inserting 42, then 69.
>> Nice.
>> Very good. Thank you. And then for 420, we would now hit a violation. Cuz at this point we are 0, 0, 0, 0, 1, 1, 0, 2, 2. We have now violated, are we within our balance factor allowance?

[00:05:50]
No. No, we are not. We must change it. So this people call it an RR rotation. I don't really like this term because even though it is right leaning, right leaning, you do a left rotation. I don't know why it's called an RR rotation, I think this is the the lean and we need to rotate out of it, I've never liked it, but it's very very simple.

[00:06:13]
All you do is drop down the 42, break link, create link. Now balance factor 0 0 0 0 0 0 0 or 1 1 0 we've now created a balanced tree right here. So we can do the other side as well, so let's just pretend we inserted 420 then 69 all right and then 42.

[00:06:39]
All right, so now that we have that we calculated 0,0,0,1,0,-1,2,0,-2 the balance where are we going out of control? Well, you can tell how we're leaning again by the numbers sign. So this one is leaning left, leaning left, or an LL cake the L-Rotation. All right, awesome. So now we need to do the same thing, but we need to do it to the right.

[00:07:07]
We are gonna rotate to the right exact same thing. Drop this thing down. Awesome. So now we have 0, 0, 0, 0,0, 0, 1, 1, 0. Now we have a proper again, balanced binary tree. So it get's a little bit harder now when we go to the next two cases, these are called double rotation cases, the double entendre of AVL trees.

[00:07:35]
And so if we started with 69 first and then let's say, we don't wanna start with 69 first. That would just be absolutely terrible. Never get anywhere with that. We're gonna actually start with 420 first then we're gonna do sorry, I almost broke the thing then 42, then 69.

[00:07:55]
Now this one we got 0, 0, 0, 0, 1, 1, 2, 0, -2. Notice that we have a left-leaning, right-leaning situation. We have an LR rotation we need to do. Now this one's a touch more complicated. We start down here and we do a rotation this way. Then we finish it off with the classic double L rotation.

[00:08:19]
We already know the double L-Rotation. So let's look at this little one. The little one, we're gonna move the 42 out here. And then we're gonna bring up the 69. So that means we look like this. So now we're gonna 0,0,0,1,0,-1,2, 0, -2, we've just created a rotation we already know how to handle.

[00:08:41]
So then after we start here we rotate here, we go up, we rotate here, so pretty straightforward rotations. And the exact same thing can hold true on the other side, we can do a 42, a 420 and a 69, and that would lead us to a 0,0, 0, 1, 0, -1, 0, 2, 2.

[00:08:59]
In other words, a right-left rotation is needed. So we'd have to do the small followed by the big, which means we're gonna have to move the 420 out here and bring up the 69. I'm actually at the edge of the screen right now. It's very exciting. Very exciting right now,.

[00:09:21]
So 69 would go right here, and there we go so now we have 0, 0, 0 ,0, 1, 0, 2, 2, which means now we just drop down the 42, and now we have 0, 0, 0, make that link happen get rid of that thing, and now we have 1, 1 0.

[00:09:40]
We have balanced the tree. Now you're probably asking me, okay, this sounds really nice, but what happened if they all have children? Wouldn't that make the rotations really, really hard? Cuz it seems easy when you just do simple problems, but the moment you don't do simple problems, it gets excessively hard, right?

[00:09:59]
Wrong, it's actually not all that hard been why did you guys fall for the easiest trick in the book? Okay, we're gonna erase all this. Just get them all out of here. Everyone has the rotations locked in the brain. Yet long as you follow the rule, the rotations are not hard.

[00:10:13]
Just always think of the rule and what that means in placement. So let's look at this. I'm gonna have A, I'm gonna have B, I'm gonna have C, and then I'm gonna have AR. Almost put L BR Brazilian mentioned, and then we're gonna have C L, CR. So now let's do the rotation here cuz at this point, we're gonna just pretend at 0,0,0,1,0, -1 and then it's going to be 2 0,-2, okay?

[00:10:41]
We're just gonna pretend it's those numbers. It doesn't really matter. Inflate them to make it all work out. We need a left left rotation here, okay? Boom, we're gonna do this. So typically, you'd wanna bring down A but now we have all these kids, right? Look at the poor Brazil.

[00:10:57]
What are we gonna do with this one? We what do we do. Well, remember, what's the rule? What can we say about BR in relation to A?
>> It's less than.
>> It's less than, beautiful, kerchow. Brazil moved A here. What can we say about AR in relation to A?

[00:11:16]
>> It's greater than.
>> It's greater than, AR. What do we need to do with C? Nothing. It's great. It's beautiful. Therefore, 0000 or 110000, it's now balanced, it's fantastic. We just did it without having to do anything fantastic here. So you can see it's really not that hard long as you focus on the rule.

[00:11:38]
This is the most important, Important part. If it's not in your head, everything feels hard.