- 2 days ago
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
avl tree, avl rotations, single right rotation, single left rotation, double right rotation, double left rotation, self balancing binary search tree, binary search tree, data structures, tree rotations, avl tree tutorial, balance factor, computer science, algorithms, coding interview, bst
=-=-=-=-=-=-=-=-=
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
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
avl tree, avl rotations, single right rotation, single left rotation, double right rotation, double left rotation, self balancing binary search tree, binary search tree, data structures, tree rotations, avl tree tutorial, balance factor, computer science, algorithms, coding interview, bst
=-=-=-=-=-=-=-=-=
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:01Hey there, let's talk about rotation types in an AVL tree, which is a self-balancing binary search tree.
00:14Okay, so hopefully you've watched my previous videos.
00:16If you have not, you probably want to check them out first, where we talk about what is a binary
00:20search tree, how to build one, how to define one, terminology, searching through it, all that stuff.
00:25And then we talked about an introduction to AVL trees, which are self-balancing binary search trees.
00:31This video is going to be about the types of rotations that you can perform in an AVL tree.
00:36What do I mean by rotation?
00:38Well, the basic idea that we talked about in the last video was that throughout your tree, you'll notice that
00:45different nodes have different balance factors, which means how imbalanced or balanced they are.
00:49When we identify a node that has a balance factor that's too bad, then we consider this to be an
00:55invalid AVL tree and we have to stop and rotate a couple of nodes, you know, kind of rearrange them
01:00to make them better before we have a valid AVL tree.
01:04So we have four different input patterns that we can have.
01:07So imagine, you know, this little tri-node subtree up on the top left.
01:11That could be, you know, three nodes that we found somewhere in our tree that had a bad balance.
01:16If you just quickly compute the balance factor for this tri-node subtree, you'll notice, actually, let me just do
01:21it real fast for fun.
01:23You'll notice that the 65 node has a balance factor of 2 because its left subtree has a height of
01:292 and there is no right subtree.
01:31The 55 has a balance factor of 1 and 48 being a leaf, at least in terms of this tri
01:36-node subtree, has a balance factor of 0.
01:40All of these tri-node subtrees are going to have the same situation.
01:44The one on top is going to be 2 and so forth.
01:46So you can imagine that you were going through the whole tree, computing balance factors like a giant tree, and
01:52you found a 2, which remember we said in our last video, 2 or worse, meaning 2 or higher,
01:58if we're using balance factors that are absolute or negative 2 and also positive 2 or worse, if we're not
02:07using absolute balance factors, means you've got to stop and try to rebalance that tri-node subtree.
02:12So we found a node that had a balance factor of 2 and we realized we have to stop and
02:18rotate.
02:20The pattern of the tri-node subtree before we perform the rotation could be one of these four things.
02:26It could be the thing on the left on top, the thing on the right on top, the thing on
02:29the bottom left, and the thing on the bottom right.
02:32And all four of these patterns should end up becoming, after we do our rotation, they should end up becoming
02:38the pattern in the middle.
02:41So this is always going to be the target pattern.
02:43Let me draw some arrows real fast.
02:46Every single input pattern is going to end up looking like the output pattern in the middle.
02:51Why is that? How is that possible?
02:53Well, we only have three nodes.
02:55If you look at all the input patterns, they're all the same numbers.
02:58What we're really doing is disconnecting all the pointers, disconnecting the parent-child relationships,
03:02and then reconnecting them in the best possible way to make, you know, the most balanced tri-node subtree.
03:08Notice how the height of all of these input trees is always 3, right?
03:15Because it's a tri-node subtree that's really, really bad and out of whack.
03:20So we'll, you know, like 1, 2, 3, 1, 2, 3, right?
03:22Height of 3.
03:25We'll do a rotation, rearrange the pointers, rearrange the parent-child relationships,
03:30so that the final height ends up being actually just 2.
03:34And if you think about reducing the height, we're making the tree better.
03:38We're making it more balanced.
03:39We're making it faster to search through and add and remove things from.
03:44So we're making a better tree by reducing the height a little bit.
03:47If you had a really, really, really bad tree and you just went around to all the bad nodes
03:50and just started rotating them all,
03:53you're reducing the height by 1 for each rotation.
03:55Eventually, when you get up to the top of the tree,
03:57you'll have an overall AVL tree, which is pretty fast.
04:03We should say now that AVL trees are always going to be log time trees
04:07because the imbalance factor is limited by a constant number.
04:11We'll say that again in a future video.
04:14So anyway, I'm going to label these trees now.
04:18I'm going to say that the one on the top left is a single right rotation.
04:27And the tree on the top right, you can probably imagine, is a single left rotation.
04:33Let me just duplicate this real fast so I can edit.
04:35Come on, man.
04:37Can I duplicate this?
04:38Yeah.
04:39So I can just edit the text real fast.
04:42This is going to be a single left rotation.
04:46And then the trees at the bottom, those are going to be double rotations.
04:50Let me just write over here, maybe next to that one, double right rotation.
04:55And then I'll duplicate this.
05:01And this one over here is going to be a double left rotation.
05:07I place these on different sides than I usually do
05:10because I was trying to make it look a little more tricky.
05:12But it's really not that bad.
05:15So how do we know that the top pattern is a single right rotation
05:20and not a double right rotation?
05:22Or it's a single right rotation and not a single left rotation.
05:26The first thing to try to understand is
05:27what's going to happen between the input pattern and the output pattern.
05:30So if you look at the input pattern here,
05:33we've got like a straight line
05:35and the output pattern is like a perfectly balanced trinode subtree.
05:41Notice how the 55 is the new parent
05:43and it's also in the middle for the output pattern.
05:47And then for the input pattern, the 55 is also in the middle,
05:49but it's not the new parent.
05:50But it is the parent already of the 48 node.
05:53Notice how it's the parent already of one node, the 48 node.
05:56So that means its relationship to the 48 node, the left child,
06:00doesn't actually change.
06:02So if you kind of think about it a little bit more,
06:05you'll realize that only one node actually needs to be moved into position.
06:10So we'll call this a rotation.
06:12Try to imagine, visualize maybe like your left pointer finger
06:16being placed on the 55 node
06:18and your right pointer finger being placed on the 65 node
06:21and then just rotate the 65 node downward.
06:24We rotate that clockwise.
06:27And the physics people out there love to say that
06:30clockwise rotations are right rotations.
06:33At least as far as I remember.
06:35Not totally sure about that, but I'm just going to say it anyway.
06:39So notice how the 65 needs to be rotated to the right or clockwise.
06:44And only one node actually needs to be rotated
06:46to produce that final output pattern.
06:48That's why we call this a single right rotation
06:51because there's only one node to rotate.
06:57The next thing I'll do is just try to give you a few extra ways
06:59of being able to remember whether it's a left or a right.
07:02So for starters, one node needs to be rotated.
07:04So it's a single rotation and we're rotating clockwise.
07:08So it's a right rotation, but you can also do this.
07:10You can think of it like, can I get rid of that real fast?
07:14Next, you can think of it like, well, there is a bunch of empty space
07:19kind of sitting here on the right side.
07:21So that could be another way to remember that this is a right rotation.
07:25Also, if you were to start at the node in the middle
07:27and work your way to the node at the top, you know, the Z node,
07:32then we're kind of going up and to the right.
07:34So that's another way to remember that this is a right rotation.
07:38Single, you can remember that also by just the fact that this is a straight line.
07:41Like notice how the nodes are kind of in a straight line.
07:44They don't do a zigzag or a bounce.
07:47So single rotations are rotations that look straight at first,
07:51or I guess input patterns that look straight.
07:53And only one node actually needs to be rotated.
07:56Right versus left is there's a pocket of empty space on the right side
08:00and you go up and to the right for the right rotations.
08:05Similarly, you can probably already figure out by now
08:07that the left rotation just means, well, we're going, let's see,
08:12we're going up and to the left to get to that top node.
08:15Or the only node that has to be rotated is that 48 node
08:18and it's going to be rotated counterclockwise, which is left.
08:22So again, only one node needs to be rotated
08:24and we're going to rotate it counterclockwise,
08:27which is a left rotation.
08:28So one node rotated, single, counterclockwise, left,
08:34or just like a pocket of empty space sitting on the left side.
08:39Okay, so then for the double rotations,
08:42the first thing you can look at is the idea that there's a little bit of a bounce.
08:46You know, there's like an angle bounce there.
08:49If you see a bounce or a diagonal,
08:51sorry, I was sick a couple of weeks ago,
08:53then that's a double rotation.
08:56Another way you can try to remember it as
08:59two nodes need to be moved into position.
09:01So if I, maybe I should copy this to another slide real fast.
09:06Let me copy this and we'll do another slide.
09:11Okay, so, you know, which nodes need to be moved into position?
09:14Let me copy also the output pattern just as a quick reminder.
09:19If we wanted to make that output pattern,
09:21let me put it up here maybe,
09:23then obviously the 55 still has to be in the middle
09:26because it was already in the middle before we rotated.
09:30That means both the 48 and the 65 need to be rotated underneath the 55.
09:37So that means we're going to do the 65.
09:39We're going to rotate it clockwise underneath the 55.
09:44So I'm going to do like a little circle here,
09:46a connector, and then I'll do like 65 there.
09:50And then after we do that rotation,
09:52we have to rotate the 48 underneath the 55.
09:55So that's going to be a rotation that is counterclockwise.
09:58So I'm going to do this,
10:00circle that there,
10:01and then do a 48.
10:05Notice how when we're done doing the rotations,
10:07we have a valid binary search tree.
10:09You should always check your rotated pattern,
10:12your output pattern,
10:13to make sure it's actually in order
10:15and it's a valid binary search tree.
10:16Because if it's not,
10:17let's say the numbers are out of order for some reason,
10:19from left to right,
10:20then you have rotated incorrectly
10:22and you have to double check yourself.
10:24So two nodes need to be rotated into position.
10:27Therefore, it's a double rotation
10:29or you see a diagonal input pattern,
10:31double rotation.
10:33How do you remember the difference
10:34between left and right?
10:37Well, if you start at the node in the middle,
10:40just like we did in the last slides,
10:42we start at the node in the middle
10:43and go to the node at the top,
10:45the Z node,
10:46we're going up and to the right.
10:47And so this is a right rotation.
10:49So it's a double right rotation.
10:51Another way to remember it
10:52is you should probably try to rotate the Z node first.
10:55The node that's on very top is the 65.
10:58Rotate that first
10:59and then call that the direction of the rotation.
11:04So, you know, we rotate the 65 first.
11:06That's a clockwise.
11:07So that's why it's a right rotation.
11:09Then just ignore the direction
11:10of the other node that you rotated.
11:13You can also kind of imagine
11:15taking the original node.
11:18If you don't want to think of like actually rotating,
11:21let me just kind of erase this real fast.
11:24You can kind of imagine that you are,
11:29you're sort of taking the new parent
11:31that's supposed to be the new parent
11:33and just sort of pulling it up.
11:38Sometimes when I teach this to people,
11:40I draw a picture of Batman
11:41and he shoots a batarang at it
11:43and he sounds like Christian Bale
11:45and he's like,
11:45where is the rotation?
11:47I'm not going to do that.
11:48Maybe if there are enough comments,
11:50I'll do a special video
11:51just for my really,
11:52really bad drawing.
11:53But imagine the 55 is getting pulled up
11:56and it's getting pulled up past two other nodes.
11:59So that's why it's a double rotation.
12:00Another way to remember.
12:03The 55 would be the mob boss
12:05that's hanging by his ankle.
12:09Anyway, so we kind of know
12:11how we can remember the difference
12:12between single and double rotations.
12:14We've got a single right rotation,
12:16a single left,
12:17a double right,
12:18a double left.
12:19There's only going to be
12:20four possible input patterns
12:21and they're all going to look like
12:22this one output pattern
12:24because really what we're doing
12:26is we're just,
12:27we're not creating any nodes
12:28or removing any nodes.
12:29We're just disconnecting pointers.
12:31We're disconnecting
12:31the parent-child relationship.
12:34We're saying,
12:35let me just get this over here.
12:37We're saying,
12:38okay, input pattern.
12:39I disconnect the pointers.
12:41I'm saying the 65
12:42no longer has a left child.
12:44The 48 no longer has a parent.
12:45The 55 no longer has a parent
12:48and the 48 no longer has a right child.
12:50And then when we're done with that,
12:51we just kind of like reconnect
12:53the relationships.
12:53We're like, okay,
12:54you know what?
12:54Just kidding.
12:55You all have parents and children.
12:56Again,
12:57we're just rearranging them.
13:00Okay, let me check out my thing
13:01real fast here.
13:03So I'm going to cut the video here
13:05because this is the basic idea
13:06for the different types of rotations
13:07that you could use.
13:09In the next videos,
13:10we're going to actually start
13:12rotating bad trees
13:13to make them work.
13:15So thanks for watching this video.
13:16I hope you learned
13:17a little bit of stuff
13:18and had a little bit of fun.
13:20I'll see you in the next video.
13:25Okay.
13:27Hey, everybody.
13:28Thanks for watching this video again.
13:30From the bottom of my heart,
13:31I really appreciate it.
13:32I do hope you did learn something
13:33and have some fun.
13:35If you could do me a please,
13:36a small little favor,
13:38could you please subscribe
13:39and follow this channel
13:41or these videos
13:42or whatever it is you do
13:43on the current social media website
13:45that you're looking at right now?
13:47It would really mean the world to me
13:48and it'll help make more videos
13:49and grow this community.
13:51So we'll be able to do more videos,
13:53longer videos,
13:54better videos,
13:54or just I'll be able to keep
13:56making videos in general.
13:57So please do me a kindness
14:00and subscribe.
14:01You know,
14:02sometimes I'm sleeping
14:03in the middle of the night
14:04and I just wake up
14:05because I know somebody
14:06subscribed or followed.
14:07It just wakes me up
14:08and I get filled with joy.
14:09That's exactly what happens
14:10every single time.
14:11So you could do it
14:12as a nice favor to me
14:13or you could troll me
14:14if you want to just wake me up
14:15in the middle of the night,
14:16just subscribe
14:17and then I'll just wake up.
14:18I promise that's what will happen.
14:21Also,
14:21if you look at the middle
14:23of the screen right now,
14:23you should see a QR code
14:25which you can scan
14:25in order to go to the website,
14:27which I think is also named
14:28somewhere at the bottom
14:29of this video
14:30and it'll take you
14:31to my main website
14:32where you can just kind of like
14:33see all the videos I published
14:35and the services
14:36and tutorials
14:36and things that I offer
14:37and all that good stuff.
14:39And
14:41if you have a suggestion
14:45for clarifications
14:45or errata
14:46or just future videos
14:48that you want to see,
14:48please leave a comment
14:49or if you just want to say,
14:50hey, what's up?
14:51What's going on?
14:52You know,
14:53just send me a comment,
14:53whatever.
14:54I also wake up for those
14:55in the middle of the night.
14:56I get,
14:56I wake up in a cold sweat
14:57and I'm like,
14:59it would really,
15:00it would really mean the world to me.
15:01I would really appreciate it.
15:03So again,
15:04thank you so much
15:04for watching this video
15:07and enjoy the cool music
15:09as I fade into the darkness,
15:12which is coming for us all.
18:18Hello there.
18:19Let's talk about rotation types in an AVL self-balancing binary search tree.
18:24Nope.
Comments