Hey everyone, in this video we break down the four types of rotations you need to know for AVL trees – self-balancing binary search trees.
We cover single right rotations, single left rotations, double right rotations, and double left rotations with clear diagrams and explanations of the input patterns and how they become the balanced output pattern.
If you’ve been learning about binary search trees and want to understand how AVL trees maintain their balance through rotations, this is the perfect next step. We look at the trinode subtrees, balance factors, and exactly how to rearrange the pointers for each case.
Great for computer science students, coding interviews, or anyone building their data structures knowledge.
Watch the full series on binary search trees and AVL trees for more.
00:00 Introduction to AVL Tree Rotations
00:14 Previous Videos Overview
00:28 Balance Factors and Trinode Subtrees
00:50 Identifying Imbalance
01:56 When to Rotate
02:20 Four Input Patterns
02:41 Target Balanced Pattern
04:18 Single Right Rotation
04:33 Single Left Rotation
08:44 Double Rotations
11:51 Remembering Rotation Types
13:04 Wrapping Up Rotations
13:27 Thanks 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
Hey there, let’s talk about rotation types in an AVL tree, which is a self-balancing binary search tree.
Okay, so hopefully you’ve watched my previous videos. If you have not, you probably want to check them out first,
where we talk about what is a binary search tree, how to build one, how to define one,
terminology, searching through it, all that stuff. And then we talked about an introduction to AVL trees,
trees which are self-balancing binary search trees this video is going to be
about the types of rotations that you can perform in an AVL tree what do I
mean by rotation well the basic idea that we talked about in the last video
was that throughout your tree you’ll notice that different nodes have
different balance factors which means how imbalanced or balanced they are when
we identify a node that has a balance factor that’s too bad then we consider
AVL tree and we have to stop and rotate a couple of nodes you know kind of rearrange them to make
them better before we have a valid AVL tree so we have four different input patterns that we can
have so imagine you know this little trinode subtree up on the top left that could be you know
three nodes that we found somewhere in our tree that had a bad balance if you just quickly compute
the balance factor for this trinode subtree you’ll notice actually let me just do it real fast for fun
that the 65 node has a balance factor of 2 because its left subtree has a height of 2
and there is no right subtree. The 55 has a balance factor of 1 and 48 being a leaf, at
least in terms of this trinode subtree, has a balance factor of 0. All of these trinode
subtrees are going to have the same situation. The one on top is going to be 2 and so forth.
So you can imagine that you were going through the whole tree, computing balance factors like
And you found a two, which remember we said in our last video, two or worse, meaning two or higher,
if we’re using balance factors that are absolute or negative two and also positive two or worse,
if we’re not using absolute balance factors, means you got to stop and try to rebalance that trinode subtree.
So we found a node that had a balance factor of two and we realized we have to stop and rotate.
The pattern of the trino subtree before we perform the rotation could be one of these four things.
It could be the thing on the left on top, the thing on the right on top, the thing on the bottom left, and the thing on the bottom right.
And all four of these patterns should end up becoming, after we do our rotation, they should end up becoming the pattern in the middle.
So this is always going to be the target pattern.
Let me draw some arrows real fast.
pattern is going to end up looking like the output pattern in the middle.
Why is that?
How is that possible?
Well, we only have three nodes.
If you look at all the input patterns, they’re all the same numbers.
What we’re really doing is disconnecting all the pointers, disconnecting the parent child
relationships and then reconnecting them in the best possible way to make, you know,
the most balanced trinode subtree.
Notice how the height of all of these input trees is always three, right?
because it’s a trinode subtree that’s really really bad and out of whack so we’ll you know
like one two three one two three right height of three we’ll do a rotation rearrange the pointers
rearrange the parent-child relationships so that the final height ends up being actually just two
and if you think about reducing the height we’re making the tree better we’re making it more
balanced we’re making it faster to search through and add and remove things from so we’re making a
So we’re making a better tree by reducing the height a little bit.
If you had a really, really, really bad tree and you just went around to all the bad nodes
and just started rotating them all, you’re reducing the height by one for each rotation.
Eventually, when you get up to the top of the tree, you’ll have an overall AVL tree,
which is pretty fast.
We should say now that AVL trees are always going to be log time trees because the imbalance
factor is limited by a constant number.
We’ll say that again in a future video.
in a in a future video so anyway i’m going to label these trees now
i’m going to say that the one on the top left is a single right rotation
and the uh the tree on the top right you can probably imagine is a single left rotation
let me just duplicate this real fast so i can come on man can i duplicate this yeah so i can
edit the text real fast. This is going to be a single left rotation. And then the trees at the
bottom, those are going to be double rotations. Let me just write over here, maybe next to that
one, double right rotation. And then I’ll duplicate this. And this one over here is going to be a
these on different sides than I usually do because I was trying to make it look a little more tricky
but it’s really not that bad. So how do we know that the top pattern is a single right rotation
and not a double right rotation or it’s a single right rotation and not a single left rotation?
The first thing to try to understand is what’s going to happen between the input pattern and
the output pattern. So if you look at the input pattern here we’ve got like a straight line and
And the output pattern is like a perfectly balanced trinode subtree.
Notice how the 55 is the new parent.
And it’s also in the middle for the output pattern.
And then for the input pattern, the 55 is also in the middle, but it’s not the new parent.
But it is the parent already of the 48 node.
Notice how it’s the parent already of one node, the 48 node.
So that means its relationship to the 48 node, the left child, doesn’t actually change.
bit more you’ll realize that only one node actually needs to be moved into position so we’ll call this
a rotation try to imagine visualize maybe like your point your left pointer finger being placed
on the 55 node and your right pointer finger being placed on the 65 node and then just rotate
the 65 node downward we rotate that clockwise and the physics people out there love to say that
are right rotations.
At least as far as I remember.
Not totally sure about that,
but I’m just going to say it anyway.
So notice how the 65 needs to be rotated
to the right or clockwise.
And only one node actually needs to be rotated
to produce that final output pattern.
That’s why we call this a single right rotation
because there’s only one node to rotate.
The next thing I’ll do is just try to give you
a few extra ways of being able to remember
being able to remember whether it’s a left or a right so for starters one node needs to be rotated
so it’s a single rotation and we’re rotating clockwise so it’s a right rotation but you can
also do this you can think of it like can i get rid of that real fast you can think of it like
well there is a bunch of empty space kind of sitting here on the right side so that could be
another way to remember that this is a right rotation also if you were to start at the node
and work your way to the node at the top,
you know, the Z node,
then we’re kind of going up and to the right.
So that’s another way to remember
that this is a right rotation.
Single, you can remember that also
by just the fact that this is a straight line.
Like notice how the nodes are kind of in a straight line.
They don’t do a zigzag or a bounce.
So single rotations are rotations that look straight at first,
or I guess input patterns that look straight
and only one node actually needs to be rotated.
um right versus left is there’s a pocket of empty space on the right side and you go up and to the
right for the right rotations similarly you can probably already figure out by now that
the left rotation just means well we’re going let’s see we’re going up and to the left to get
to that top node or the only node that has to be rotated is that 48 node and it’s going to be
rotated counterclockwise which is left so again only one node needs to be rotated and we’re going
to be rotated and we’re going to rotate it counterclockwise which is a left rotation so
one node rotated single counterclockwise left or just like a pocket of empty space sitting on the
left side okay so then for the double rotations the first thing you can look at is the idea that
there’s a little bit of a bounce you know there’s like a angle bounce there if you see a bounce or
sick a couple weeks ago then that’s a double rotation another way you can try to remember it
as two nodes need to be moved into position so if I maybe I should copy this to another slide real
fast let me copy this and we’ll do another slide okay so you know which nodes need to be moved into
position let me copy also the output pattern just as a quick reminder if we wanted to make that
If we wanted to make that output pattern, let me put it up here maybe,
then obviously the 55 still has to be in the middle
because it was already in the middle before we rotated.
That means both the 48 and the 65 need to be rotated underneath the 55.
So that means we’re going to do the 65, we’re going to rotate it clockwise underneath the 55.
So I’m going to do like a little circle here, a connector, and then I’ll do like 65 there.
65 there and then after we do that rotation we have to rotate the 48
underneath the 55 so that’s going to be a rotation that is counterclockwise so
I’m going to do this circle that there and then do a 48 notice how when we’re
done doing the rotations we have a valid binary search tree you should always
check your rotated pattern your output pattern to make sure it’s actually in
binary search tree because if it’s not let’s say the numbers are out of order for some reason from
left to right then you have rotated incorrectly and you have to double check yourself so two nodes
need to be rotated into position therefore it’s a double rotation or you see a diagonal input pattern
double rotation how do you remember the difference between left and right well um if you start at the
node in the middle just like we did in the last slides we start at the node in the middle and go
and go to the node at the top, the Z node,
we’re going up and to the right.
And so this is a right rotation.
So it’s a double right rotation.
Another way to remember it is you should probably try to rotate the Z node first.
The node that’s on very top is the 65.
Rotate that first and then call that the direction of the rotation.
So, you know, we rotate the 65 first.
That’s a clockwise.
So that’s why it’s a right rotation.
Then just ignore the direction of the other node that you rotated.
you can also kind of imagine taking the original node if you don’t if you don’t
want to think of like actually rotating let me just kind of erase this real fast
you can kind of imagine that you are you’re sort of taking the new parent
that’s supposed to be the new parent and just sort of pulling it up
I draw a picture of Batman and he shoots a batarang at it and he sounds like Christian
Bale and he’s like, where is the rotation?
I’m not going to do that.
Maybe if there are enough comments, I’ll do a special video just for my really, really
bad drawing.
But imagine the 55 is getting pulled up and it’s getting pulled up past two other nodes.
So that’s why it’s a double rotation.
Another way to remember.
The 55 would be the mob boss that’s hanging by his ankle.
anyway so uh we we kind of know how we can remember the difference between uh single and
double rotations uh we’ve got a single right rotation a single left a double right a double
left there’s only going to be four possible input patterns and they’re all going to look like this
one output pattern because really what we’re doing is we’re just we’re not you know creating
any nodes or removing any nodes we’re just disconnecting pointers we’re disconnecting
just get this over here we’re saying okay input pattern I disconnect the pointers I’m saying the
65 no longer has a left child the 48 no longer has a parent the 55 no longer has a parent and
the 48 no longer has a right child and then when we’re done with that we just kind of like reconnect
the relationships we’re like okay you know what just kidding you all have parents and children
again we’re just rearranging them okay let me check out my thing real fast here
I’m going to cut the video here because this is the basic idea for the different types of rotations that you could use.
In the next videos, we’re going to actually start rotating bad trees to make them work.
So thanks for watching this video.
I hope you learned a little bit of stuff and had a little bit of fun.
I’ll see you in the next video.
Okay.
Hey, everybody.
Thanks for watching this video again from the bottom of my heart.
I really appreciate it.
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, or just I’ll be able to keep making videos in
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 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
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 just send me a comment whatever i also wake up for
the night I get I wake up in a cold sweat 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 um enjoy
the cool music as as I fade into the darkness which is coming for us all
Thank you.
Hello there.
Let’s talk about rotation types in an AVL self-balancing binary search tree.
