AVL Tree Rotations Tutorial: Fixing Imbalance After Adding a Node

Neural Lantern

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  avl tree, avl tree rotation, avl rotations, binary search tree, data structures tutorial, balance factor, tree rotation, double right rotation, avl insertion, avl tree example, computer science, algorithms, coding interview, bst, self balancing tree  =-=-=-=-=-=-=-=-=  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

Transcript

00:01Hello there! Let's maintain an AVL tree by rotating some nodes after we add a

00:06new node that messes up the whole tree.

00:20Okay, I hope that before you watch this video you've seen my other videos where

00:23we talk about what is a binary search tree, how to define it, terminology, how

00:27to build a tree, search through the tree, all the stuff for the tree, the binary

00:30search tree, and then my other videos where we talked about what is an AVL

00:34tree, what is a rotation, what are the different types of rotations, why would

00:37you want to rotate, how do you do the balance factors, all that stuff happens

00:41in previous videos, so search the video history. Anyway, so for now I'm going to

00:47assume that you know all that because you watch the videos and now we're looking

00:50at an AVL tree. Maybe first we're going to try to decide if it's a valid AVL

00:56tree and then we will add a new node which will probably mess the whole thing

01:00up and force us to to do a rotation to get the tree back in balance. Okay, so the

01:07first thing I'm going to do is just this is an example tree, it's got some nodes,

01:13and I'm going to compute the balance factors for every single node just to

01:17double check. Remember the rule that we're using is if an AVL tree has a

01:21balance factor of two or worse for any node then it's considered invalid. The

01:27tree itself is just a binary search tree not of AVL tree until we fix the

01:31imbalance. So the 44 node, wait hang on that's actually wrong, I don't know why I

01:35even typed that number there. Oh because I was saying two. First thing I want to do

01:39is do the balance factors for the leaves because they're the easiest. All the

01:43leaves have a balance factor of zero because they have no difference in left

01:47subtree versus right subtree height. The 50 node is also kind of easy because

01:51it's left subtree and right subtree have the same height so that's just a 0. 17 is

01:57a little bit more tricky it's got one node hanging off the right side so it's

02:02right subtree height is one it's left subtree height is zero so absolute value

02:06of zero minus one is just going to be one. So that's not perfect but at the same

02:11time that's acceptable we can just sort of move on. Remember only two or worse is

02:16going to make us stop. We look at the 78 again let me just or for the first time

02:21we look at the 78 let me just do this the hard way to make sure everybody's on

02:24the same page. For the for the balance factor of the 78 node we look at the

02:29height of the left subtree which is 2 and then we look at the height of the

02:33right subtree which is 1 and so if you take the absolute value of 2 minus 1

02:38that's going to be 1. So actually the balance factor of the 78 node is okay. This is

02:43maybe a good time to point out the fact that we don't really care about mass or

02:47weight. We don't care that there are more nodes on the left we just care about the

02:51height of the left subtree. So I'm going to duplicate this slide to continue. So far

02:58so good every node seems to be okay. We'll look at the 44 node you can

03:01probably eyeball it because well I mean for me when I want to eyeball balance

03:07factors I just look at the left subtree versus the right subtree notice how

03:12there's like one level of difference in height we could do it the hard way if we

03:17wanted to. So like the left subtree has a height of 2 right subtree has a height of

03:223 so 2 minus 3 absolute value that's going to be 1 or just that one line that I

03:28drew before which was the the difference. So that means this whole tree is

03:32actually okay it is a valid AVL tree. Nice video over I'm just kidding. Let's add a

03:39node that will screw everything up so that we're forced to do a rotation. So

03:45I'm going to add the number 54. Let me just try to select an existing node here

03:50duplicate it. I'll change this to a 54 then we'll figure out where the 54 node

03:55actually belongs. Hopefully you've already become an expert at binary search

03:59trees so I'm just going to do it real quick. We show up top here 54 belongs on the

04:04right. We look at the 78 it belongs on the left. We look at the 50 it belongs on the

04:07right. We look at the 62 it belongs on the left. So the 54 belongs right there as

04:13the left child of the 62 node. So I'm going to go ahead and do my little

04:19connecting line indicating that the nodes are now pointing to each other. The 54

04:24thinks its parent is 62. The 62 thinks its left child is 54. And now we have to

04:29recompute the balance factors. So obviously the node we just added it doesn't have a

04:34balance factor. So we have to recompute it. So I'm going to put a zero there. But we have to

04:39work

04:39our way up the tree until we hit the root node. Recomputing all balance factors along

04:44the way. We don't actually I'm going to do marks here to make sure that I don't

04:48forget. We don't actually have to recompute you know the 17 or the 32 or the 88

04:53because those nodes are not possibly going to or actually even the 48 because

04:58those nodes are not possibly going to be affected by the 54 node. Because balance

05:02factors are only affected by nodes that are underneath. So these nodes off to the

05:06side or even nodes below wouldn't be affected. So we're only going to compute

05:13the 62, the 50, the 78, and the 44. Working our way up to the root node. Soon as we

05:19hit root then we're done recomputing. So the balance factor for the 62 I'm going to

05:26eyeball that that's going to be a one because left subtree height is one right

05:29subtree height is zero. So far so good. As soon as we see a 2 we probably need to

05:34stop and rotate right away. Again as I said in a previous video we probably will

05:41see that the root node's balance factor is bad. But if we if we compute the whole

05:45tree and then just decide I don't know like the root node is going to be

05:48rotated we'll probably rotate incorrectly. You want to rotate as low as possible

05:53first because rotating lower in a tree is probably going to fix nodes that are

05:58higher. So recomputing the balance factor for the 50 that's going to be a one

06:02because left subtree height of one right subtree height of two. Take the absolute

06:06value of the difference there. We go up to the 78 node and this one is going to be

06:12bad because you can see that the left subtree has a height of three and the

06:16right subtree has a height of one so the balance factor is going to be a two. It's

06:20at this point since we just started by inserting the 54 and worked our way up

06:25that I would stop and do a rotation. But just for the purposes of this tutorial

06:29I'm going to I'm going to compute the root node just just to show you what's

06:32going on. The height of the left subtree off the root node is two the height of

06:37the right subtree is one two three four so that means the balance factor of the

06:4144 node also has a two. So at this point it might be a little confusing if you

06:46don't remember that you kind of have to stop as you're working your way up or at

06:50least rotate the lowest possible node first. You might be confusing you know

06:55which which one do I rotate? Do I rotate the 78 first or do they rotate the 44?

07:00If we were to rotate the 44 first the root node you know we could do it but at the

07:04same time there's a chance that it won't actually fix the 78 node and there will

07:09be other stuff underneath that is bad and so it'll cost us more work to do it

07:13that way. So instead we're going to stop at the 78 and do our rotation. So remember

07:21we said in a previous video that we'll choose the first node that is out of

07:25whack as the z node. We're looking for x, y, and z. I'm going to write x, y, and z

07:30here. X, y, and z. Now how do we choose y? We go down to a child of z and

07:38it has

07:38to be the child that has the taller subtree. Notice how the left subtree of the z

07:43node has a height of 3 and the right subtree has a height of 1 which means we

07:47definitely need to go left to find the y node. So I'm going to put y right here.

07:51If the left and the right subtree had the same height then it doesn't really

07:55matter which one you choose. Maybe try to be consistent but definitely we have to

08:00go left this time because that's the taller subtree. Again look how tall it is.

08:04Okay now we need to look for the x node. Again we have to take the left or the

08:09right child of the y node or just like a grandchild of the z node. That is

08:14definitely a child of the y node. We have to choose the taller subtree so we

08:18could not put x as 48. We can't do that because that's not the taller subtree.

08:23Instead the x is going to be the 62 node because that's the taller subtree.

08:28Now we have chosen our x, y, and z node. Which means I'm going to just type some stuff up

08:34here real fast. I'm going to do x is equal to 62, y is equal to 50, and z is

08:42equal to 78.

08:44Just as a reminder. And this is kind of similar to what you would do in the code. I mean

08:49on these diagrams us humans we have to like rearrange things and name the types of rotations

08:55and so forth. In the code it's actually really easy in comparison because all you have to do is

09:01produce an in-order representation of the three node pointers that you received x, y, and z.

09:07Let's say we have a function called rotate. We don't even have to remember the types of rotations.

09:11You just grab x, y, z and then you order them and call them a, b, and c. Let's do

09:16a equals something,

09:17b equals something, c equals something. So a is going to be the least value because again this has to

09:22be a

09:22binary search tree before it can be an avl tree. So 50 is going to go on the left. That's

09:27the only place

09:27that it could go. And then 62 in the middle and then 78 on the right side. And then I'm

09:34going to

09:35just, maybe I'll copy and paste this here, this little trinode subtree. Was that, will that work?

09:40Yeah. So I don't have to draw this again. I'm going to erase some of this stuff. Oh, come on,

09:45man. I'm going to erase some of this stuff just to make it a little more neat.

09:51Then I'm going to replace the values, uh, in these nodes with just x, y, and z. So, um,

09:58sorry, a, b, c. So a is going to be 50. That's the leftmost node or the least value. And

10:04then b is

10:05going to be 62. And then c is 78. Before you continue, make sure you've actually drawn a valid

10:12binary search tree, because if you haven't, then your avl tree is not going to end up being valid

10:17either. It always has to be a valid binary search tree. So the order has to be correct.

10:21So if you were thinking about, well, how can we can't put the 78 in the middle,

10:24or how come we can't put the 62 on the left? What would have happened? Well, it would have been

10:28invalid or you would have ended up with like a straight line or something that wasn't

10:32the target pattern for a rotation, which is supposed to be a perfectly balanced trinode subtree.

10:38Okay. So now we've got x, y, and z and a, b, c, and we have our output pattern here,

10:44which is going to basically take away from these three nodes. The next thing we need to do is take

10:49into account any nodes that come underneath nodes from the output pattern. So our x, y, z,

10:56I guess you could say input pattern too. Let's look at, you know, x, for example. So like the 62.

11:02Did it have any children that are not accounted for in the output pattern? Actually, yes, it has a 54

11:07node.

11:08So this 54 needs to go somewhere. We can't just like erase it from the tree. So I'm going to

11:12move it down here,

11:13just so I don't forget it. Then we look at the y node. What children did the y node have?

11:18It had a 48

11:19as a child and a 62 as a child. The 62 is actually already handled in the output pattern. So

11:25we don't

11:25need to worry about that. But the 48 was not handled. So we got to put that somewhere too.

11:29So I'm going to move that down here. Now we look at the z node. The z node had 50

11:35as a child,

11:36as a left child. That's already handled in the output pattern. So we don't need to worry about

11:40that. It also had 88 and that is not in the output pattern. So we have to do something with

11:4588. So I'm

11:48going to do a more complicated example where some of these nodes that are children of the output

11:57pattern, they might have children of their own or descendants of their own. If they do, don't

12:02rearrange any of the descendants. So anything that was below 54, just leave it in place, hanging exactly

12:09where it was already off of the 54. Same thing for the 48. If it had any children of its

12:13own, just leave

12:14them in place. Don't touch them. Don't touch any descendants. So now that we've done this, whoops,

12:21dang it. Let me copy this in a good way instead of a bad way. Okay. Let me erase this

12:27real fast.

12:29X, Y, and Z. Nope. That's going to screw me up. I'm going to forget. Okay. Now we have to

12:35place these

12:36nodes of the output pattern in their appropriate position. Like where do they actually belong?

12:42Well, remember this is supposed to be a binary search tree. So there's actually only one place

12:46that the 54 node could ever go and still give us a valid binary search tree. So, I mean, think

12:52about

12:52it for a second. Could it go on the left of 50? No. Could it go on the right of

12:5662? No. It has to go in

12:59between the 50 and the 62. Otherwise we wouldn't have a valid binary search tree. So I'm just going to

13:03stick

13:03it right there. Maybe a little bit lower to make this a more beautiful diagram. Then I'm going to

13:10do my connecting line real fast. So I'm going to do this. So it's the right child of the 50.

13:16Now notice

13:17how before it was the left child of the 62. So then, you know, again, we're just really disconnecting

13:22pointers and then rearranging them. So this 48, it can't be on the right side of 62. It has to

13:28be on the

13:28left side. It can't be on the right side of the 50. It has to be on the left side.

13:32So the 48 must be

13:33the left child of the 50. Again, you must end up with a valid binary search tree or you've done

13:39something wrong. So I'm going to just kind of do this here. And then same thing for the 88 node.

13:45There's only one place this could go. It can't go on the left of 62. It has to go on

13:50the right of the

13:5078. It couldn't go on the left of the 78. That would be bad news. So I'm just going to

13:54place this here

13:55and then just make a little connecting line. Okay. Now I'm going to double check to make sure

14:02that I didn't forget any other nodes because when you're working with a diagram, you might forget a

14:07couple of nodes and just sort of like erase too many nodes without putting them in the output pattern.

14:11If you're rearranging pointers, it's fine. You wouldn't have to worry about any nodes that came

14:15underneath these nodes because they would just remain attached in place. But I just want to double

14:20check real fast. So we got X, Y, and Z. So that's three nodes and then four, five, six. So

14:28we've got

14:28six nodes total. If we include the XYZ nodes and all nodes that are direct children of those and even

14:35underneath. So how many do I have in the output pattern? One, two, three, four, five, six. So I've

14:40got the same number of nodes. I'm ready to erase all this stuff up top and reattach. One, two, three,

14:47three, four, five, six. Yeah. Reattach this into the diagram. So I'm literally just going to erase

14:51all this stuff right here. Then I'm going to select all the nodes in the output pattern

14:57and I'm going to move them up to be the new right child of the 44 because that's where originally

15:06the

15:06Z was. So I'm just going to maybe move these up here real fast and then get that 32 back

15:13down

15:13where it belongs. Dang you. 32. Actually, it's a little bit too low. Get that maybe a little bit

15:21better. How about there? So the last step is we have to recalculate the balance factors to make

15:28sure that we have a valid AVL tree. Maybe we have to do another rotation. Maybe not. I don't know.

15:33Kind of looks like maybe not, but I'm not going to take any chances. So let's do the leaves first.

15:39Remember, we have to recompute the balance factors for every node that we just moved.

15:43So all the nodes in the output pattern and their immediate children, not anything lower,

15:49but so I'm going to say that this 48 node, all the leaves are just going to have a balance

15:53factor

15:54of zero. That's pretty easy. The 50 is perfectly balanced. Nice. So it's going to have a balance

15:58factor of zero. The 78 has one node hanging off the right and nothing on the left. So it's got

16:03a one

16:03there. The 62, again, we're not looking at mass. We're not looking at weight. We're looking at the

16:09height of the left subtree versus the height of the right subtree. So this is actually perfectly

16:14balanced because the height of the left subtree is two and so is the height of the right subtree.

16:19Now that we're done with all the nodes that we just moved, we should recursively or just kind

16:23of like walk our way up the tree and recompute all balance factors until we find the root node.

16:29Okay, so there's the root node. Only one more thing left to do. The balance factor of the root node

16:35is, let's see, left subtree has a height of two, right subtree has a height of three. So the balance

16:41factor for the root node is going to be a number one. Notice how the 44, the root node got

16:47fixed

16:47because we rotated a little bit lower. And this is not the fastest tree in the world, but it is

16:53considered a log tree because the imbalance is only scaling with a constant factor because we're limiting

16:59the balance factors to just the number one, basically, before we rotate.

17:05So what type of rotation did we actually perform? If you looked at my previous video,

17:09you should know this already, but maybe I'll duplicate this here and sort of start to maybe

17:17annotate it. I'm going to do, okay, so what is the rotation we did? Well, if we look at the

17:25ZYX here,

17:26the XYZ, there's a little bit of a balance. Actually, let me do orange. There's a little bit of a

17:32balance, right? So that's going to be a double rotation. Or you can imagine that we had to move

17:37two nodes into position in order to get the 62 to be the new parent and the 50 on the

17:45left and the 78

17:46on the right. Notice how the 78 had to be rotated first. So it's like under the 62. And then

17:54the 50

17:56was rotated second underneath. I mean, we snipped off that 54 elsewhere. But long story short,

18:02there are two nodes that need to be rotated into position for output pattern. So that's a double

18:08rotation. So diagonal bounce or two nodes rotated means a double rotation. And then is it a left or

18:14right rotation? Well, if you think about the first node that we rotated, it was the 78. What's going on,

18:23my computer? The first node that we rotated was 78, the Z node. So what direction did we rotate that?

18:32That was clockwise. So that's a right rotation. So a double right rotation. Another way of looking at

18:37it is if we only look at the input pattern, we just look at, you know, these nodes right here,

18:44there was kind of a pocket of empty space on the right side, wasn't there? So that's why it's a

18:48double right rotation. Another way to think of it is, I'm running out of colors. If we started at the

18:55Y node and worked our way up to the Z node, we went up into the right. So that's a

18:59double right

19:00rotation also. Either way you cut it, we performed a rotation and now we have a pretty good tree.

19:08Okay, let me just double check. This is a valid BST. Doop, doop, doop, doop, doop, doop,

19:14and it's a valid AVL tree because all the balance factors are okay. Yeah. And in future videos,

19:21we're going to do more rotations. I'm probably going to do at least like, you know, two or three

19:24more videos where we just simply rotate, you know, some tree and explain it and work our way through

19:30it. If you have an idea for a really gross tree that you want me to rotate in front of

19:35you,

19:35leave a comment. If I get enough comments, maybe I'll do it. Otherwise, thanks for watching this video.

19:41I'll see you in the next one. I hope you learned a little bit of stuff and had a little

19:44bit of fun.

19:47I'm outie. I'm just simply outie.

19:55Hey everybody. Thanks for watching this video again from the bottom of my heart. I really

19:59appreciate it. I do hope you did learn something and have some fun. If you could do me a please,

20:04a small little favor, could you please subscribe and follow this channel or these videos or whatever

20:10it is you do on the current social media website that you're looking at right now?

20:14It would really mean the world to me and it'll help make more videos and grow this community. So

20:19we'll be able to do more videos, longer videos, better videos, or just I'll be able to keep making

20:24videos in general. So please do me a kindness and subscribe. You know, sometimes I'm sleeping in

20:31the middle of the night and I just wake up because I know somebody subscribed or followed. It just wakes

20:35me

20:35up and I get filled with joy. That's exactly what happens every single time.

20:39So you could do it as a nice favor to me or you could, you could troll me if you

20:42want to just wake

20:42me up in the middle of the night, just subscribe and then I'll, I'll just wake up. I promise that's

20:47what will happen. Also, uh, if you look at the middle of the screen right now, you should see a

20:52QR code,

20:52which you can scan in order to go to the website, which I think is also named somewhere at the

20:56bottom

20:57of this video. And it'll take you to my main website where you can just kind of like see all

21:02the videos

21:02I published and the services and tutorials and things that I offer and all that good stuff.

21:07And, uh, if you have a suggestion for, uh, uh, clarifications or errata or just future videos

21:15that you want to see, please leave a comment. Or if you just want to say, Hey, what's up,

21:19what's going on? You know, just send me a comment, whatever. I also wake up for those in the middle

21:23of the night. I get, I wake up in a cold sweat and I'm like, it would really, it would

21:28really mean

21:28the world to me. I would really appreciate it. So again, thank you so much for watching this video

21:33and, um, enjoy the cool music as, as I fade into the darkness, which is coming for us all.

24:46Hey there, let's fart on ourselves.

24:56Hello there, let's rotate an AVL tree because it's fricking invalid.

25:01No.

25:05Hey there, let's maintain an AVL tree.

25:10Hey there, let's maintain an AVL...

25:12Hmm...

25:13Eh...

25:13Hey there, let's maintain an AVL tree.

Category

Transcript

Comments

Recommended