Four Semesters of Computer Science in 5 Hours AVL Tree

[00:00:00]
>> [MUSIC]

[00:00:04]
>> Brian Holt: AVL trees are definitely the hardest thing you're gonna learn today. Okay, after that, this is the peak and then it's all downhill from here, I promise. Actually, after this, we get into hash tables. Hash tables are kind of fun. And then we get into functional programming 101, which is actually my favorite section of this.

[00:00:19] Cuz it just feels really cool. I like functional programming a lot. But yeah, this is definitely the hardest one. This just gets kind of crazy, but it's fun. Okay. So an AVL tree Is by definition a binary search tree, but not vice versa. So anything that is an AVL tree is also a binary search tree.

[00:00:44] So we follow that same logic of, lesser goes on the left, greater goes on the right kind of idea, right? AVL trees just kind of take that a little bit further by making sure that these trees stay as flat as possible. So let's take a look here at the answer just, maybe I can show you a little bit.

[00:01:01] Like, notice this tree is actually very flat, right, it doesn't have any big outcroppings, right. It stays pretty level. And that's the point of an AVL tree is it's keeping your tree as flat as possible so you don't end up with trees like this. That's the entire point of the AVL is it's mitigating the worst case scenario of the binary search tree.

[00:01:23] AVL, in case you're wondering, just stands for the last name of the authors. I think I have them on here. Adelson-Velsky and Landis. I'm sure I'm pronouncing that just the worst way possible. But it's gonna end up being pretty flat. So yeah, they are specialized binary search trees.

[00:01:43] So a valid AVL tree is always a valid BST, but not necessarily vice versa. And so the good news is you add the same way. The same algorithm of going left and right, that remains totally the same, 100%. The difference is, is when you're coming back out of the recursion, because it, like I said, it has to be recursive this time.

[00:02:03] You're going to check every single time is, hey, am I balanced? Are both my children in balance? No, then I need to do a what's called a rotation, right. That's the difference here. So how do you tell if it's out of balance? Well, if the difference of height between the two children is 2 or greater, then it's out of balance.

[00:02:26] So let's just look at a bunch of examples of that and hopefully that becomes clear. Okay, so this is an AVL tree right here, because this has a balance of 1, and a balance of 1, if you're including itself, right. So that all of these nodes are in balance.

[00:02:42] This one is not an AVL tree, because this one has a height of 0 and this has a height of 2, right. So this is now out of balance, okay. Also out of balance. This has a height of 2 and height of 0. This is an AVL tree, which looks kind of weird, but I promise it is, because this has a balance of 2.

[00:03:03] This has a balance of 1, right. This is one right here is probably the weirdest one you're gonna see that actually is a balanced AVL tree. So let's walk through and figure out why it is. So balance of 1, sorry, or balance, of 0, right, cuz this has a balance of 0, balance of 0.

[00:03:20] This has a balance of 1 and a balance of 0 so this one's in balance, right? This one has a balance of 2, right, so this one's 2 and this one's 3. So that's only a difference of 1, so that's okay. And then obviously, if you take this one, this is perfectly balanced, right?

[00:03:35] Where this is a balance of 2, balance of 2, balance of 1, balance of 1, right? So everything in there is in balance. It looks super weird, but it actually is a balanced AVL tree. However, this one, which looks more symmetrical and pleasant, is actually not a balanced tree.

[00:03:52] Cuz if you look at this, this has a height of 3 and a height of 0. Sorry, actually, this node right here actually is balanced, this one is not. Cuz this one has a balance of 2 and a balance of 0. Same thing on the other side, right, this one is a balance of 2 and this is a balance of 0.

[00:04:11] Okay, do you follow that? And this one is also balanced as well. You can ignore the skewed part of it right now. We'll talk about that in just a second, but that's also balanced. So any questions about what an AVL tree looks like, like what are we chasing?

[00:04:30]
>> Brian Holt: Okay, so hopefully you can identify what an AVL tree looks like. So again, the extra effort here is worth it because these trees become much flatter and much easier to search. And it's actually not that much computation to get them in balance. So our worst case, we'll never hit the n cases for lookup.

[00:04:51] So for example for up here, the worst case scenario of a BST for a lookup is n, that we have to go through all of the the other nodes to get to 5, right. And this will never get that out of balance, ever. So the worst case is always a O(log n).

[00:05:06] That's why AVL trees are good. So let's look at the hardest part of the AVL trees. Like I said, adds are mostly the same, but we're gonna do it recursively.
>> Brian Holt: But the rebalances just tend to be a little crazy, in fact a lot crazy, so