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