In this video we walk through a complete example of maintaining an AVL tree. Starting with a valid AVL tree, we insert a new node that breaks the balance rules, then recompute balance factors up the tree until we find the imbalance.
Watch as we identify the X, Y, and Z nodes and perform a double right rotation to restore the AVL property while keeping it a valid binary search tree.
Perfect for students learning data structures, computer science fundamentals, or anyone preparing for coding interviews.
Previous videos cover binary search trees, AVL basics, rotations, and balance factors.
00:00 Intro to AVL Tree Rotation
00:20 Prerequisites and Previous Videos
01:06 Initial AVL Tree Example
01:18 Computing Balance Factors
03:44 Adding Node 54
04:31 Recomputing Balance Factors
06:08 Detecting Imbalance at Node 78
07:20 Identifying X Y Z Nodes
08:36 Labeling X Y Z and Trinode Pattern
10:09 Output Pattern and BST Ordering
11:03 Handling Extra Children Nodes
14:50 Reattaching Rotated Subtree
15:24 Recalculating Balance Factors
17:05 Double Right Rotation Explained
19:18 Final Verification and Outro
=-=-=-=-=-=-=-=-=
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 maintain an AVL tree by rotating some nodes after we add a new node that messes up the whole tree.
Okay, I hope that before you watch this video you’ve seen my other videos where we talk about what is a binary search tree, how to define it, terminology, how to build a tree, search through the tree, all the stuff for the tree.
the tree all the stuff for the tree the binary search tree and then my other videos where we
talked about what is an avl tree what is a rotation what are the different types of rotations why would
you want to rotate how do you do the balance factors all that stuff happens in previous videos
so uh search the video history anyway so for now i’m going to assume that you know all that because
you watch the videos and now we’re looking at an a we’re looking at an avl tree maybe first we’re
a valid AVL tree and then we will add a new node which will probably mess the whole thing up
and force us to do a rotation to get the tree back in balance.
Okay so the first thing I’m going to do is just this is an example tree, it’s got some nodes
and I’m going to compute the balance factors for every single node just to double check.
Remember the rule that we’re using is if an AVL tree has a balance factor of two
for any node, then it’s considered invalid.
The tree itself is just a binary search tree,
not an AVL tree, until we fix the imbalance.
So the 44 node, wait, hang on, that’s actually wrong.
I don’t know why I even typed that number there.
Oh, because I was saying two.
First thing I want to do is do the balance factors
for the leaves, because they’re the easiest.
All the leaves have a balance factor of zero,
because they have no difference in left subtree
versus right subtree height.
The 50 node is also kind of easy,
because it’s left subtree and right subtree
left subtree and right subtree have the same height so that’s just a zero 17 is a little bit
more tricky it’s got one node hanging off the right side so its right subtree height is one
its left subtree height is zero so absolute value of zero minus one is just going to be one
so that’s not perfect but at the same time that’s acceptable we can just sort of move on remember
only two or worse is going to make us stop we look at the 78 again let me just uh or for the first
or for the first time we look at the 78 let me just do this the hard way to make sure everybody’s
on the same page uh for the for the balance factor of the 78 node we look at the height of the left
subtree uh which is two and then we look at the height of the right subtree which is one
and so if you take the absolute value of two minus one that’s going to be one
so actually the balance factor of the 78 node is okay this is maybe a good time to point out the
We don’t care that there are more nodes on the left. We just care about the height of the left subtree
So I’m going to duplicate this slide to continue so far so good every node seems to be okay
We’ll look at the 44 node. You can probably eyeball it because
Well, I mean for me when I want to eyeball a balance factors
I just look at the left subtree versus the right subtree notice how there’s like one level of difference
in height we could do it the hard way if we wanted to and
do it the hard way if we wanted to um so like the left subtree has a height of two right subtree has
a height of three so two minus three absolute value that’s going to be one or just that one
line that i drew before which was the the difference so that means this whole tree is
actually okay it is a valid avl tree nice video over i’m just kidding uh let’s add a node that
So I’m going to add the number 54.
Let me just try to select an existing node here, duplicate it.
I’ll change this to a 54.
Then we’ll figure out where the 54 node actually belongs.
Hopefully you’ve already become an expert at binary search trees.
So I’m just going to do it real quick.
We show up top here, 54 belongs on the right.
We look at the 78, it belongs on the left.
We look at the 50, it belongs on the right.
We look at the 62, it belongs on the left.
right there as the left child of the 62 node. So I’m going to go ahead and do my little connecting
line indicating that the nodes are now pointing to each other. The 54 thinks its parent is 62.
The 62 thinks its left child is 54. And now we have to recompute the balance factors.
So obviously the node we just added, it doesn’t have a balance factor, so we have to recompute
way up the tree until we hit the root node, recomputing all balance factors along the way.
We don’t actually, I’m going to do marks here to make sure that I don’t forget.
We don’t actually have to recompute, you know, the 17 or the 32 or the 88 because those nodes
are not possibly going to, or actually even the 48, because those nodes are not possibly going
to be affected by the 54 node because balance factors are only affected by nodes that are
or even nodes below wouldn’t be affected. So we’re only going to compute the 62, the 50,
the 78, and the 44, working our way up to the root node. Soon as we hit root, then we’re done
recomputing. So the balance factor for the 62, I’m going to eyeball that. That’s going to be a one
because left subtree height is one, right subtree height is zero. So far, so good. As soon as we
away. Again as I said in a previous video we probably will see that the root
nodes balance factor is bad but if we if we compute the whole tree and then just
decide I don’t know like the root node is going to be rotated we’ll probably
rotate incorrectly you want to rotate as low as possible first because rotating
lower in a tree is probably going to fix nodes that are higher. So recomputing the
balance factor for the 50 that’s going to be a 1 because left subtree height of
right subtree height of 2, take the absolute value of the difference there.
We go up to the 78 node and this one is going to be bad because you can see that the left subtree
has a height of 3 and the right subtree has a height of 1 so the bounce factor is going to be
a 2. It’s at this point since we just started by inserting the 54 and worked our way up that I
would stop and do a rotation but just for the purposes of this tutorial I’m going to compute
just to show you what’s going on.
The height of the left subtree off the root node is two,
the height of the right subtree is one, two, three, four.
So that means the balance factor of the 44 node
also has a two.
So at this point, it might be a little confusing
if you don’t remember that you kind of have to stop
as you’re working your way up
or at least rotate the lowest possible node first.
You might be confused, you know, which one do I rotate?
Do I rotate the 78 first or do they rotate the 44?
If we were to rotate the 44 first, the root node, you know, we could do it.
But at the same time, there’s a chance that it won’t actually fix the 78 node.
And there will be other stuff underneath that is bad.
And so it’ll cost us more work to do it that way.
So instead, we’re going to stop at the 78 and do our rotation.
So remember we said in a previous video that we’ll choose the first node that is out of whack as the Z node.
We’re looking for X, Y, and Z.
I’m going to write X, Y, and Z here.
X, Y, and Z.
Now, how do we choose Y?
We go down to a child of Z,
and it has to be the child that has the taller subtree.
Notice how the left subtree of the Z node has a height of 3,
and the right subtree has a height of 1,
which means we definitely need to go left to find the Y node.
So I’m going to put Y right here.
If the left and the right subtree had the same height,
then it doesn’t really matter which one you choose.
matter which one you choose. Maybe try to be consistent, but definitely we have to go left
this time because that’s the taller subtree. Again, look how tall it is. Okay, now we need to look for
the X node. Again, we have to take the left or the right child of the Y node, or just like a grand
child of the Z node. That is definitely a child of the Y node. We have to choose the taller subtree,
so we could not put X as 48. We can’t do that because that’s not the taller subtree. Instead,
Instead, the X is going to be the 62 node because that’s the taller subtree.
Now we have chosen our X, Y, and Z node,
which means I’m going to just type some stuff up here real fast.
I’m going to do X is equal to 62, Y is equal to 50,
and Z is equal to 78, just as a reminder.
And this is kind of similar to what you would do in the code.
I mean, on these diagrams, us humans,
we have to like rearrange things and name the types of rotations and so forth in the code it’s
actually really easy uh in comparison because all you have to do is produce an in-order representation
of the three node pointers that you received x y and z let’s say we have a function called rotate
we don’t even have to remember the types of rotations you just grab xyz and then you order
them and call them a b and c let’s do a equals something b equals something c equals something
So A is going to be the least value because again, this has to be a binary search tree
before it can be an AVL tree.
So 50 is going to go on the left.
That’s the only place that it could go.
And then 62 in the middle and then 78 on the right side.
And then I’m going to just, maybe I’ll copy and paste this here.
This little trinode subtree.
Was that, will that work?
Yeah.
So I don’t have to draw this again.
I’m going to erase some of this stuff.
Oh, come on, man.
I’m going to erase some of this stuff just to make it a little more neat.
just to make it a little more neat.
Then I’m going to replace the values in these nodes with just X, Y, and Z.
So, sorry, ABC.
So A is going to be 50.
That’s the leftmost node or the least value.
And then B is going to be 62.
And then C is 78.
Before you continue, make sure you’ve actually drawn a valid binary search tree,
because if you haven’t, then your AVL tree is not going to end up being valid either.
not going to end up being valid either it always has to be a valid binary search tree so the order
has to be correct so if you were thinking about well how can we can’t put the 78 in the middle
or how come we can’t put the 62 on the left what would have happened well it would have been invalid
or you would have ended up with like a straight line or something that wasn’t the target pattern
for a rotation which is supposed to be a perfectly balanced trinode subtree okay so now we’ve got x y
here which is going to basically take away from these three nodes the next thing we need to do is
take into account any nodes that come underneath nodes from the output pattern so our xyz i guess
you could say input pattern too let’s look at uh you know x for example so like the 62. did it have
any children that are not accounted for in the output pattern actually yes it has a 54 node so
this 54 needs to go somewhere we can’t just like erase it from the tree so i’m going to move it
to move it down here just so I don’t forget it. Then we look at the Y node. What children did the
Y node have? It had a 48 as a child and a 62 as a child. The 62 is actually already handled in the
output pattern so we don’t need to worry about that but the 48 was not handled so we got to put
that somewhere too. So I’m going to move that down here. Now we look at the Z node. The Z node
had 50 as a child, as a left child. That’s already handled in the output pattern so we don’t need to
don’t need to worry about that it also had 88 and that is not in the output pattern so we have to
do something with 88 so i’m going to move that down here too i should also point out um i think
in a future video i’m going to do a more complicated example where some of these nodes that are
children of the uh the output pattern they might have children of their own or descendants of their
own if they do don’t rearrange any of the descendants so anything that was below 54 just
hanging exactly where it was already off of the 54.
Same thing for the 48.
If it had any children of its own,
just leave them in place.
Don’t touch them.
Don’t touch any descendants.
So now that we’ve done this, whoops, dang it.
Let me copy this in a good way instead of a bad way.
Okay, let me erase this real fast.
X, Y, and Z.
Nope, that’s going to screw me up.
I’m going to forget.
Okay, now we have to place these nodes
nodes of the output pattern in their appropriate position like where do they
actually belong well remember this is supposed to be a binary search tree so
there’s actually only one place that the 54 node could ever go and still give us
a valid binary search tree so I mean think about it for a second could it go
on the left of 50 no could it go on the right of 62 no it has to go in between
the 50 and the 62 otherwise we wouldn’t have a valid binary search tree so I’m
there maybe a little bit lower to make this a more beautiful diagram then I’m going to do my
connecting line real fast so I’m going to do this so it’s the right child of the 50 now notice how
before it was the left child of the 62 so then you know again we’re just really disconnecting
pointers and then rearranging them so this 48 it can’t be on the right side of 62 it has to be on
the left side it can’t be on the right side of the 50 it has to be on the left side so the 48 must be
side so the 48 must be the left child of the 50. again you must end up with a valid binary search
tree or you’ve done something wrong so i’m going to just kind of do this here
um and then same thing for the 88 node there’s only one place this could go it can’t go on the
left of 62 it has to go on the right of the 78 it couldn’t go on the left of the 78 that would be bad
news so i’m just going to place this here and then uh just make a little connecting line okay
Okay, now I’m going to double check to make sure that I didn’t forget any other nodes
because when you’re working with a diagram, you might forget a couple of nodes and just
sort of like erase too many nodes without putting them in the output pattern.
If you’re rearranging pointers, it’s fine.
You wouldn’t have to worry about any nodes that came underneath these nodes because they
would just remain attached in place.
But I just want to double check real fast.
So we got X, Y, and Z.
So that’s three nodes and then four, five, six.
So we’ve got six nodes total if we include the XYZ nodes and all nodes that are direct children of those and even underneath.
So how many do I have in the output pattern?
1, 2, 3, 4, 5, 6.
So I’ve got the same number of nodes.
I’m ready to erase all this stuff up top and reattach.
1, 2, 3, 4, 5, 6.
Yeah, reattach this into the diagram.
So I’m literally just going to erase all this stuff right here.
Then I’m going to select all the nodes in the output pattern.
the output pattern and i’m going to move them up to be the new right child of the 44 because that’s
where originally the z was so i’m just going to maybe move these up here real fast and then get
that 32 back down where it belongs dang you 32 uh actually it’s a little bit too low get that
So the last step is we have to recalculate the balance factors to make sure that we have a valid AVL tree.
Maybe we have to do another rotation, maybe not, I don’t know.
Kind of looks like maybe not, but I’m not going to take any chances.
So let’s do the leaves first.
Remember, we have to recompute the balance factors for every node that we just moved.
So all the nodes in the output pattern and their immediate children, not anything lower.
all the leaves are just going to have a balance factor of zero that’s pretty easy.
The 50 is perfectly balanced nice so it’s going to have a balance factor of zero.
The 78 has one node hanging off the right and nothing on the left so it’s got a one there.
The 62 again we’re not looking at mass we’re not looking at weight we’re looking at the height of
the left subtree versus the height of the right subtree so this is actually perfectly balanced
because the height of the left subtree is 2 and so is the height of the right subtree.
we’re done with all the nodes that we just moved we should recursively or just kind of like walk
our way up the tree and recompute all balance factors until we find the root node. Okay so
there’s the root node only one more thing left to do. The balance factor of the root node is let’s
see left subtree has a height of two right subtree has a height of three so the balance factor for
the root node is going to be a number one. Notice how the 44 the root node got fixed because we
we rotate it a little bit lower.
And this is not the fastest tree in the world,
but it is considered a log tree
because the imbalance is only scaling
with a constant factor because we’re limiting
the balance factors to just the number one basically
before we rotate.
So what type of rotation did we actually perform?
If you looked at my previous video,
you should know this already,
but maybe I’ll duplicate this here
sort of start to maybe annotate it. I’m going to do…
Okay, so what is the rotation we did? Well, if we look at the ZYX here, the XYZ,
there’s a little bit of a bounce. Actually, let me do orange. There’s a little bit of a bounce,
right? So that’s going to be a double rotation. Or you can imagine that we had to move two nodes
and the 50 on the left and the 78 on the right. Notice how the 78 had to be rotated first.
So it’s like under the 62. And then the 50 was rotated second underneath. I mean,
we snipped off that 54 elsewhere. But long story short, there are two nodes that need to be rotated
into position for output pattern. So that’s a double rotation. So diagonal bounce or two nodes
means a double rotation and then is it a left or a right rotation well if you
think about the first node that we rotated it was the 78 what’s going on my
computer the first node that we rotated was 78 the Z node so what direction did
we rotate that that was clockwise so that’s a right rotation so a double
right rotation another way of looking at it is if we only look at the input
look at the input pattern we just look at you know these nodes right here there was kind of a
pocket of empty space on the right side wasn’t there so that’s why it’s a double right rotation
another way to think of it is I’m running out of colors if we started at the y node and worked our
way up to the z node we went up into the right so that’s a double right rotation also either way you
cut it we performed a rotation and now we have a pretty good tree okay let me just double check
Okay, let me just double check.
This is a valid BST.
Doop, doop, doop, doop, doop, doop, doop, doop, doop.
And it’s a valid AVL tree
because all the balance factors are okay.
Yeah, and in future videos,
we’re going to do more rotations.
I’m probably going to do at least like,
you know, two or three more videos
where we just simply rotate, you know, some tree
and explain it and work our way through it.
If you have an idea for a really gross tree
that you want me to rotate in front of you,
leave a comment.
leave a comment if i get enough comments maybe i’ll do it um otherwise thanks for watching this
video i’ll see you in the next one i hope you learned a little bit of stuff and had a little
bit of fun i’m outie i’m just simply outie hey everybody thanks for watching this video again
from the bottom of my heart i really appreciate it i do hope you did learn something and have some
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 or just i’ll be able to keep making
videos in general so please do do me a kindness and uh and subscribe you know sometimes i’m
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, which I think is also named somewhere at the bottom of this video.
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 if you have
a suggestion for 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 just send me a comment whatever I also wake up for
those in the middle of the night I get I wake up in a cold sweat I’m like this
It would 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.
Hey there, let’s uh…
Bart on ourselves.
Hello there, let’s rotate an AVL tree because it’s frickin invalid.
No.
Hey there, let’s uh maintain an AVL tree.
and eh.
