AVL Trees Q&A

[00:00:01]
>> Okay, let's take some questions about AVL trees.
>> I guess I can go first. I'm kind of struggling where to put AVL trees conceptually. So the way I see computer science, right? It's, I guess I'm up. Three is here, drugs there, all that stuff. And then there's a VM please.

[00:00:28]
I don't really get how they fit in the big picture. I don't know. I just don't strike me.
>> Yep.
>> I'm trying to put it somewhere desperate.
>> For sure, no, I totally understand where you problem is. [COUGH] So the question is, what the hell do I do with this knowledge that I have now?

[00:00:48]
Why did I learn this? Why did you subject me to this torture? Valid question, honestly, I'm not totally sure myself sometimes. It's not cuz I'm a sadist or something like that. I mean a bit, but it's for fun. So the time that you want self balancing trees, so I'm gonna say self balancing trees as opposed to AVL trees.

[00:01:14]
Because something like a red black tree which does the same thing just with different methodologies is better. It just works better but it's harder to implement. So, with self-balancing trees. Basically, you wanna think about using these when you have huge amounts of data like 9,500 things and you need to be able to find things very quickly.

[00:01:37]
So, you're willing to sacrifice ad performance and delete performance for extreme searchability. That's really like, hey, self balancing trees, that's gonna be the thing that I need. So again, database indexes is like, is a good example of this. I have 1 million things in my database. I have I mean, how many Facebook users are there right, a billion users, and I need to be able to look up any user at any time.

[00:02:05]
You're gonna use some sort of self-balancing tree probably for that index, right? Where you can say, give me user number 1350, and that'll go into the tree, and it'll find that really quickly and hand you back the user. That's the part where self-balancing trees end up being super useful for you.

[00:02:26]
Does that make sense?
>> Yes, it does. So I guess, like it's a scalable tree, circle, right? That's what it is.
>> That's exactly what it is. It's a extreme scalable tree.
>> About the rotations is there like an explanation, that's much easier to or analogy for what happens during a rotation.

[00:02:53]
>> I mean the best
>> I mean the concept I'm really struggling to understand.
>> Weird so I totally understand. And honestly these videos are the best things I can show you, right? [COUGH] Basically, you're just trying to make the depth of the tree flatter, so I tried to do here with the the video that you can watch.

[00:03:14]
If you go to visualgo.net, which is where these videos are from. They have here binary search trees and you can click on here. yeah cool, I got it. And then they have like a little AVL tree module up here. So you can insert in here, Click Go. And you can see here it will actually go through and insert all those things for you.

[00:03:48]
You can kind of visualize what's happening. So that's the best thing I can say of like, how to kind of conceptually visualize them more. As far as like the specific logic of what it's actually doing for you like this code right here. It's just doing that mechanism of rotating the tree around.

[00:04:14]
>> So, if you were to explain the difference between the left and the right rotation Apart from like, visualizing it isn't there's no real there's no easy way.
>> There's no like, conceptual analogy to make there. It's just moving nodes around in a tree to make it look flatter.

[00:04:38]
A right rotation, right? Is this right child? There's two here, the left child. There is zero here. And you're trying to make it so 8 is gonna be the root node of this, and then you're gonna have a left child of 7 and a right child of 9, right, cuz that's flatter.

[00:04:54]
So it means that there are less hops, right, so that you end up with trees that are really nice and pretty, like these ones. That's the whole point of why you do it, and then the the actual mechanism that you do it is just, again, these steps right here.

[00:05:18]
But beyond that, it's just it's really abstract [LAUGH] And I'm not sure if I can make that abstract concept any more concrete than it is because it's just inherently an abstract concept. Is that a sufficiently unsatisfying explanation of that?
>> I think I'll just go to visual go and try to little concept on that.

[00:05:48]
>> I would say that would probably be your best bet, yeah.
>> Thanks.
>> Yep, of course. Is there another question?
>> This height thing is a bit confusing, the balancing thing. Correct me if I'm wrong, the balancing thing is like if height of the like, left and right is like minus is greater than or less than or less than 1.

[00:06:12]
So is it balanced is it or like what like.
>> So the difference has to be 2, right?. So again looking, let's look at this tree, right? so this 6 Itself has a height of, I call it 3 in mind, right? Because this is height 1, this is height 2, and this is height 3.

[00:06:34]
So it's left height, sorry, the height of its left child is 2, and the height of its right child is 1, so they're balanced, right? Cuz 1 is only 1 different than 2. So as long as it doesn't have a difference of 2 or more, then it's considered balanced.

[00:06:58]
If I added 2 here, so this would have, the 2 would go here, right? This would now have a left height of 3, and this would now have a right height of 1, so it'd be out of balance, and it'd be out of balance on the left. So we'd have to balance here.

[00:07:18]
Does that make sense?
>> Yeah, what if you had a 0 then? Then the height of 6 would be 4, is it?
>> So if I added a 0 to this tree, where I'd go here, right? Same thing with we'd still have to rotate.
>> Yeah, but the height of the 6 word like 1, 2, 3, 4, is that's how I've been I'm just confused with the like the current node we have given it as a height of 1, right?

[00:07:45]
Then it's like a, it's children predecessors would be the counting 2, 3, 4.
>> Let's see if I can just explain it. So, if we added 0 to this tree, the 0 would go here, right?
>> Yeah
>> This would have a left height of 1 a right height of 0.

[00:08:03]
This would have a left height of 2 and a right height of 1, that's fine. This would have a left height of 3, and a right height of 1. This 6 would be out of balance, and so we would rotate left
>> But yeah, little bit confusing yeah, but yeah.

[00:08:27]
[LAUGH]
>> It's inherently confusing, [LAUGH] I didn't invent the algorithm. [LAUGH] Yeah, it just takes some getting used to. And again, this visual algo is actually pretty helpful and understanding. When to rotate left when to rotate like right.
>> Yeah, another thing like the approach that we followed in this AVL trees like we applied the methods on all on load, right?

[00:09:01]
But can we follow the approach that we follow it on the binary search tree like on the tree node? Pre bootlicker we applied to makers like adding or checking these is it balanced or not like
>> This is what we were talking about before, so the question is in the BS tree, just bring it up here, in the BS tree we have all the the root the logic here for adding the tree.

[00:09:30]
Use the while loop. And here in the AVL tree, we switch to a recursive add that exists on the node. Could you do it with a iterative approach on the tree? And I think the answer is no, I think you have to do it recursively because the balance has to be checked on the way up And I don't think there's another way to handle it, though, I could be wrong.

[00:09:55]
That's just my intuition in terms of how I chose to implement it. Because I think you have to update the heights and you have to update the rotations in which case you would need to do that recursively