00:01Hello there! Let's talk about a type of self-balancing binary search tree called an AVL tree.
00:13Okay, so by now I hope you've seen my other videos that I've posted previously where we talked about binary
00:19search trees, how to define them, terminology, how to know you're actually looking at one, how to build them, insert,
00:25remove, modify, all that stuff, time complexity.
00:28If you finish those videos already with me, then you know that binary search trees can actually get slow sometimes
00:34because if we have bad data, regular binary search trees don't really know how to rearrange themselves.
00:39They just might become slow depending on how good or bad the data is.
00:43The data is totally random, then on average the trees will be log time, but that's not always the case.
00:49Maybe sometimes you have bad data, sorted data, poisoned data, whatever kind of data.
00:55So the secret to AVL trees is we're going to start with a binary search tree.
01:00And so first it has to satisfy all the rules of a binary search tree.
01:04And then we add on another rule.
01:06The rule is going to be that we don't have a valid AVL tree if the balance factor for any
01:12of the nodes, we'll talk about balance factors in a second,
01:14if the balance factor for any node is two or worse, meaning if we think the tree is too imbalanced
01:21at any node, it's not a valid AVL tree.
01:24And therefore we must rebalance the tree with something called a rotation.
01:29After we do enough rotations and we see that the tree is balanced again, then it'll be valid.
01:33And so AVL trees sometimes are invalid in some intermediate state.
01:39Like if you have an AVL tree and you add some data into it for a moment, it might be
01:44an invalid AVL tree.
01:46And then internally, it's sort of just like rotating itself and rebalancing itself.
01:49Then when the tree is done, you'll have a valid AVL tree again, if that makes sense.
01:55So suppose this tree here, we can tell this is a valid binary search tree because it follows all the
02:01rules that we talked about before.
02:02So let's start implementing the first rule of an AVL tree, which is let's compute the balance factors for every
02:09single node.
02:09How do we compute balance factors?
02:11The basic idea is, I want to say BF for balance factor is going to be the absolute value of
02:18the difference of the left subtree height minus the right subtree height.
02:27If you don't know what a subtree or height is, you should probably check out my other videos right now.
02:32But basically, we're just going to take the absolute value just to get the difference in the height of the
02:36left and the height of the right.
02:40So if you know binary search trees already, then you know that the leaves, they don't have any subtrees.
02:45So their balance factor is going to be pretty easy to compute. It's just going to be a zero.
02:49I should also point out that some other tutorials out there use positive and negative numbers for the balance factor.
02:55That's okay. I'm just going to use absolute values here because it's a little bit more simple.
03:00So all the leaves get a balance factor of zero, which is fine.
03:03We're looking to see if we can find a balance factor of two or worse to indicate to us that
03:08we have an invalid AVL tree.
03:09So far, so good. Let's look at the 22 node.
03:13So for the 22 node, we'll compute the height of the left subtree versus the height of the right subtree.
03:20So, you know, I'm going to highlight its left subtree.
03:24That's just the 14 node that has a height of one.
03:26And then its right subtree is just the 36 node that also has a height of one,
03:30which means the balance factor for the 22 node is the absolute value of one minus one is zero.
03:38So actually the 22 node is perfectly balanced.
03:41If you think about it, that makes sense.
03:43Left and right subtrees have the same height. No problem.
03:45So I'm going to move on.
03:47Let's compute the balance factor for the 48 node.
03:50This is a little trickier.
03:51Notice how the right subtree has a height of one and there is no left subtree,
03:56which means its height is zero.
03:58So for the 48 node, it's actually going to be the absolute value of zero minus one or just one.
04:07So we find our first node that's a little bit out of whack.
04:10It's a little bit of an imbalance here, but AVL trees tolerate imbalances of one.
04:16They don't really care.
04:17We sort of try to make a trade-off between constantly always rotating every single time anything happens,
04:23which would perhaps burn a little too much CPU,
04:26versus letting the tree just be imbalanced to a reasonable amount,
04:31so we could still call this a log tree in the end.
04:33So we consider this to be okay. So far this is a valid AVL tree.
04:38Let's go up to the 65 node and compute the balance factor.
04:42So 65 node has no right subtree, so the height is zero there,
04:46and its left subtree is those two nodes on the left, so that has a height of two,
04:51which means the balance factor for the 65 node is going to be the absolute value of two minus zero
04:59is two.
05:00At this point we are already certain that this is not a valid AVL tree,
05:04and it would need to be rebalanced or rotated before we could, you know,
05:08consider it a valid AVL tree in the future.
05:10So invalid AVL tree, still a valid binary search tree.
05:14Something has to be done.
05:16Normally what I would say is if you find some nodes way down lower in the tree that are imbalanced,
05:21then just go ahead and perform a rebalancing or a rotation immediately,
05:25because sometimes when you rotate lower in the tree,
05:28you'll end up fixing nodes that are a little higher.
05:31But since we started with this tree, and we're not kind of, you know, building a tree step by step,
05:35I just want to compute the balance factor for all of the nodes at the same time.
05:39So we'll do the same thing for the 41 node, the root node.
05:43Its left subtree has a height of two, and its right subtree has a height of three,
05:47so its balance factor is the absolute value of two minus three is one.
05:58So actually the root node is okay.
05:59If it was only up to the root node, we would say this is a valid AVL tree,
06:03and we don't really need to do anything.
06:05However, we've already seen that the 65 node is invalid.
06:10So again, we need to do something.
06:14Here's another quick example before we move on to actually identifying which nodes to modify and rotate.
06:20Just real fast, I want to show you.
06:23You know that a binary search tree could actually end up being a linear tree.
06:26If you had really, really, really bad data, the binary search trees don't self-balance.
06:31So it could get this bad.
06:32This is slow because this is a linear tree.
06:35The time complexity of searching through this tree is linear time.
06:38It scales linearly with the number of nodes in your data set.
06:41That's really far away from log time, which is supposed to be lightning fast.
06:46So an AVL tree will fix this kind of bad data.
06:50Let's take a step back here and focus your attention for a second on these three nodes.
06:55We noticed that there is one node that's actually out of whack.
06:57It's the 65 node, right?
06:59What we're going to do is we're going to find a trinode subtree that starts with the first node
07:04or the lowest node we can find that's out of whack.
07:07It's the 65 node.
07:08And you can tell that if we just kind of go down a level and down another level
07:13to select the other two nodes, it's just going to be this little, you know,
07:17subtree of three nodes or otherwise known as a trinode subtree.
07:21So here's kind of a diagram for that.
07:24Whoops, forgot to delete that earlier.
07:26Let me get rid of that.
07:28So this is the trinode subtree that we selected, right?
07:31So we've got the 65 and the 48 and the 55.
07:34How did we actually select this?
07:36So what you kind of want to do is the first node that is out of whack,
07:40you want to call that Z.
07:41So I'm going to write a Z here.
07:43What we're looking for is a trinode subtree, which we'll first call X and Y and Z.
07:50And then we'll end up reordering the nodes and then rearranging all the pointers to the nodes
07:54so that the trinode subtree is a little bit more in balance.
07:58So we see the Z node.
08:00We have to find the Y node next to find the Y node.
08:04What's going on with my computer?
08:05Oh, there we go.
08:06We have the Z node to find the Y node.
08:08Really, we're just going to take the child of the 65 node that has the taller subtree.
08:14So there's only one subtree, you know, on the left.
08:17There's no subtree on the right of the 65 node.
08:19So the choice is obvious.
08:20But just so you know, if there was, you know, another, you know,
08:24child hanging off of the right for some reason, we would still choose the number 48 node as the Y
08:31node
08:31because it has the taller subtree.
08:33Notice how the subtree on the left is two and the subtree on the right has a height of one.
08:38So always take the taller subtree when you're looking for a Y and then X.
08:44So then we do the same thing.
08:45We go down to the grandchild of the Z node.
08:48And if we had a choice to go left or right again, we would always choose the taller subtree.
08:52In this case, there's only one choice.
08:54So that X node is going to be the 55.
08:59Now in this next slide, I've kind of redrawn this in a little bit different of a way.
09:04Notice the trinode subtree that we just selected here, the 65, 48, 55 subtree.
09:09It has a height of three.
09:12I mean, that should be obvious, right?
09:13It's just got a height of three.
09:15We could redraw this subtree in a way that has a shorter height.
09:20Notice on the left, these are the same three nodes.
09:24Exactly.
09:2548, 55, and 65.
09:27That's the same three nodes that we originally had.
09:29But notice how the height is two.
09:31So the basic idea for ABL trees is, you know, compute the balance factors.
09:35And as soon as you identify a node that's out of whack, you grab a trinode subtree starting at the
09:40node that's out of whack, the Z node.
09:43And then we'll perform, quote unquote, a rotation where we just kind of smoosh it to be a little bit
09:48more balanced and a little bit more, a little bit shorter.
09:51So the height goes from three to two.
09:53Once we do that, the rest of the tree is going to get a little bit better.
09:56You'll notice that this will end up sometimes completely, but sometimes partially fixing bad balance factors in the tree.
10:05So this is the end of the intro.
10:06I only wanted to spend a little time just kind of like warming you up to the idea.
10:10In the next videos, we're going to actually look at performing rotations, identifying the four different types of rotations that
10:18you could see and like how to do them.
10:20We'll talk more about the idea that we're really just rearranging pointers here.
10:23If you're thinking about code, you're thinking about, oh, I've got some pointers between these nodes.
10:27We're not going to delete any nodes or add any nodes.
10:29We're just going to like rearrange who is a parent of who, who is a child of who.
10:35And then eventually we'll, we'll deal with some really bad trees and we'll become experts at just like maintaining ABL
10:41trees.
10:43And we'll talk about ways to visualize the rotations, which makes it a little bit easier to remember these patterns
10:49and stuff.
10:50Okay. So thank you for watching this video.
10:53I hope you learned a little bit of stuff and had a little bit of fun.
10:56And the next one, we're going to, we're going to get started.
10:58We're going to, we're going to go deep.
11:01I'm going to get my gear.
11:04Sorry.
11:09Hey everybody.
11:10Thanks for watching this video again from the bottom of my heart.
11:13I really appreciate it.
11:14I do hope you did learn something and have some fun.
11:16If you could do me a please, a small little favor, could you please subscribe and follow this channel or
11:23these videos or whatever it is you do on the current social media website that you're looking at right now.
11:28It would really mean the world to me and it'll help make more videos and grow this community.
11:33So we'll be able to do more videos, longer videos, better videos, or just, I'll be able to keep making
11:38videos in general.
11:39So please do, do me a kindness and, and subscribe.
11:43You know, sometimes I'm sleeping in the middle of the night and I just wake up because I know somebody
11:47subscribed or followed.
11:48It just wakes me up and I get filled with joy.
11:50That's exactly what happens every single time.
11:53So you could do it as a nice favor to me or you could, you could troll me if you
11:56want to just wake me up in the middle of the night, just subscribe.
11:58And then I'll, I'll just wake up.
12:00I promise that's what will happen.
12:03Also, if you look at the middle of the screen right now, you should see a QR code, which you
12:07can scan in order to go to the website, which I think is also named somewhere at the bottom of
12:11this video.
12:12And it'll take you to my main website where you can just kind of like see all the videos I
12:16published and the services and tutorials and things that I offer and all that good stuff.
12:21And, uh, if you have a suggestion for, uh, uh, clarifications or errata or just future videos that you want
12:29to see, please leave a comment.
12:31Or if you just want to say, Hey, what's up, what's going on?
12:34You know, just send me a comment, whatever.
12:36I also wake up for those in the middle of the night.
12:37I get, I wake up in a cold sweat and I'm like, it would really, it really mean the world
12:43to me.
12:43I would really appreciate it.
12:44So again, thank you so much for watching this video and, um, enjoy the cool music as, as I fade
12:52into the darkness, which is coming for us all.
13:15Bye.
13:16Bye.
13:44Bye.
13:45Bye.
14:20Bye.
14:45Bye.
14:46Bye.
15:14Bye.
15:15Bye.
15:43Bye.
15:45Bye.
Comments