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