- 2 days ago
Learn AVL trees in this beginner-friendly introduction. We cover balance factors, why regular BSTs get slow, and how AVL trees stay balanced with rotations. Great for coding interviews and data structure understanding.
00:00 AVL Trees Introduction
00:00:28 Problems with Regular BSTs
00:00:56 AVL Tree Balance Rule
00:02:10 Balance Factor Explained
00:02:48 Computing Balance Factors
00:03:11 Example Tree Analysis
00:04:40 Imbalance at 65 Node
00:05:08 Invalid AVL Tree
00:06:18 Linear Tree Problem
00:06:50 Trinode Subtree
00:07:40 Selecting Z Y X Nodes
00:09:20 Rotation Overview
00:10:03 Next Videos Preview
00:11:09 Thank You and Subscribe
AVL tree, AVL trees, self balancing binary search tree, binary search tree, BST, data structures, balance factor, tree rotation, computer science, algorithms, coding tutorial, programming tutorial, AVL tree rotation, balanced binary tree
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main "pinned" video of this channel for offers and extras
00:00 AVL Trees Introduction
00:00:28 Problems with Regular BSTs
00:00:56 AVL Tree Balance Rule
00:02:10 Balance Factor Explained
00:02:48 Computing Balance Factors
00:03:11 Example Tree Analysis
00:04:40 Imbalance at 65 Node
00:05:08 Invalid AVL Tree
00:06:18 Linear Tree Problem
00:06:50 Trinode Subtree
00:07:40 Selecting Z Y X Nodes
00:09:20 Rotation Overview
00:10:03 Next Videos Preview
00:11:09 Thank You and Subscribe
AVL tree, AVL trees, self balancing binary search tree, binary search tree, BST, data structures, balance factor, tree rotation, computer science, algorithms, coding tutorial, programming tutorial, AVL tree rotation, balanced binary tree
=-=-=-=-=-=-=-=-=
Thanks for watching!
Find us on other social media here:
- https://www.NeuralLantern.com/social
- Twitter / X: https://x.com/NeuralLantern
- Rumble: https://rumble.com/c/c-3696939
- BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt
- Daily Motion: https://www.dailymotion.com/neurallantern
- Minds: https://www.minds.com/neurallantern/
- Odysee: https://odysee.com/@NeuralLantern:5
Please show your support!
- Buy me a coffee: https://ko-fi.com/neurallantern
- Subscribe + Sharing on Social Media
- Leave a comment or suggestion
- Subscribe to the Blog: https://www.NeuralLantern.com
- Watch the main "pinned" video of this channel for offers and extras
Category
🤖
TechTranscript
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