AVL Tree Rotations Practice: Balancing a Huge Linear Tree Step by Step

Neural Lantern

In this hands-on AVL tree tutorial, we take a massive unbalanced linear binary search tree and perform multiple rotations to turn it into a properly balanced AVL tree. Watch as we identify imbalance, label X Y Z nodes, determine A B C, handle outstanding children, and reattach subtrees step by step.  Perfect for computer science students learning data structures, self-balancing trees, and AVL rotations. We go through several rotations on the same tree to show the full process from start to finish.  If you've seen the basics, this is the practice video you've been looking for. Timestamps and clear diagrams included.  Like and subscribe for more data structures content!  00:00 Introduction to AVL Rotations Practice 00:22 Previous Videos Overview 00:56 Understanding the Linear Tree Problem 01:24 Why Balance This Tree 02:20 Computing Balance Factors 03:16 First Rotation Setup XYZ 04:04 In-Order ABC Pattern 05:50 Reattaching Subtree 07:17 Recompute Balance Factors 08:06 Second Rotation Setup 09:20 XYZ and ABC for Second Rotation 10:08 Drawing Output Pattern 11:40 Placing Outstanding Children 13:32 Third Rotation Setup 14:28 XYZ for Third Rotation 15:02 Output Pattern and Children 18:28 Recompute Balance Factors 19:28 Fourth Rotation Setup 20:04 XYZ for Final Rotation 20:32 Handling All Outstanding Children 23:20 Reattaching Final Subtree 24:50 Last Rotation Setup 25:48 XYZ and ABC Final 26:38 Output Pattern and Children Placement 30:16 Final Balance Factors Check 30:52 Valid AVL Tree Achieved 31:07 Conclusion and Thanks  AVL tree, AVL rotations, binary search tree, self balancing tree, data structures, tree rotations, AVL balance factor, computer science tutorial, BST, algorithms, coding interview, rotation examples, balanced binary 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:00Hello there!

00:01Let's practice AVL rotations with a big ugly gross linear tree that for some reason hasn't

00:06been rotating up to this point, but we're going to rotate it all at once to make it

00:10nice and balanced per the rules of AVL trees, just for practice.

00:22Okay, so first off, you should have hopefully seen my previous videos.

00:26We talk about binary search trees, how to define them, how to build them, search through

00:30them, add, remove stuff, all that stuff.

00:33And then we talked about AVL trees, which are really just self-balancing binary search trees

00:37with some extra special rules on top.

00:39We talked about the types of rotations, how to do the rotations, when to rotate, how to

00:45detect whether a tree is actually a valid AVL tree and all that stuff.

00:48So if you don't know what I'm talking about, see my previous videos.

00:52Otherwise, we're just going to practice on this one tree right now.

00:55We're just going to do a practice run.

00:57Okay, so you would never, I mean, you would hopefully never see an AVL tree that looks

01:01like this.

01:02This is way too imbalanced for an AVL tree.

01:06An AVL tree would have started rebalancing itself a long time ago, but let's just pretend

01:10for the sake of argument that you disabled the balancing feature of your AVL tree.

01:15You maybe like have a Boolean inside of your class that you've written in your program called,

01:20Am I behaving like an AVL tree, true or false?

01:23And you set it to false for a while.

01:24Then you started throwing nodes at the tree.

01:27After you ended up with this giant linear tree, then we're going to suddenly turn on

01:31the AVLness bool and start rotating.

01:35This tree sucks.

01:36This is a valid binary search tree, but like if you notice, it follows all the rules of

01:41a binary search tree and the data is in order.

01:44But this is definitely not a valid AVL tree.

01:47The time complexity of searching through this tree would be O of H. And since O of H is actually

01:52the number of nodes in the entire tree, the time complexity of searching through this particular

01:57tree is O of N. So this is a linear tree.

02:00It's no faster to search through than a linked list, at least in terms of scalability.

02:06So this is bad.

02:07We need to fix this.

02:09So now let's turn on the AVLness.

02:12We'll say, okay, now you're no longer pretending to be a regular binary search tree.

02:16You're an AVL tree.

02:17Let's do some rotations.

02:19The first thing we should do if you're presented with a tree like this all at once is just

02:22compute the balance factors for every single node.

02:24So I'm going to say the 55 is a leaf.

02:27It has a balance factor of zero.

02:29The 42 has a balance factor of one.

02:31And really, the balance factors just increase by one for every level up we go.

02:36So the balance factor of the 15 node is horrible.

02:39It's really, really, really bad.

02:41Now that we've done this, we could rotate anywhere we wanted to.

02:44I mean, it's valid to rotate starting with the 34 or the 27 or 22 or 15.

02:50You wouldn't want to rotate the 42 because that's not imbalanced enough for an AVL tree.

02:55But really, the smartest thing to do is rotate as low as possible because when you rotate

03:01stuff that's lower, it tends to fix stuff that's higher.

03:04So then you'll end up doing less work and probably end up with a tree that matches what

03:08someone else expected.

03:11Okay, so we're going to rotate as low as possible.

03:13That means I'm going to find the lowest node that is out of whack, and I'm going to say

03:16it's the 34 node.

03:1734 node, and I'll label that as Z.

03:20That's bad.

03:21Let me try again.

03:2234 is Z.

03:24Okay, then we find the A child of the Z node.

03:28And we have to find the child that has a taller subtree, but there's only one choice.

03:32We can only go to the right.

03:34There's nothing on the left.

03:35So that means Y is the 42 node.

03:38Same thing for the X node.

03:40We're labeling for X, and we have to find a child of Y.

03:43We have to look at the taller subtree, but there is no other choice.

03:47This suite can only go down and to the right.

03:48So now we know our X, Y, Z.

03:50I'm just going to place these labels up here at the top.

03:53I'm going to say X is 55, Y is 42, and Z is 34.

03:59And maybe I'm going to change that text color real fast.

04:04Then we want to produce an in-order representation of X, Y, Z.

04:07This step, I think it helps people with diagrams, but it also helps you a lot when it comes time

04:12to code.

04:13Because coding for these rotations is way easier than diagramming these rotations.

04:18You pretty much just have to come up with three new pointers, A and B and C.

04:24And all they are is the ordered version of X, Y, Z.

04:27So, you know, which node belongs on the very left?

04:29That's going to be 34.

04:30Which node would belong in the middle?

04:32That's going to be 42.

04:33Which node would belong on the right side?

04:35That's going to be 55.

04:3655.

04:36And so now we're ready to come up with our output pattern.

04:40So I'm just going to take one of these nodes and copy it.

04:42Maybe get rid of that little stem there.

04:46And then I'm going to just, you know, copy paste this a couple times as quickly as I can.

04:51It doesn't need to be perfect.

04:53It doesn't need to be perfect.

04:54But if it's not, they'll laugh at you.

04:59So we'll do this and we'll draw some connecting lines.

05:04So we've got like three nodes here, a perfect little trinode subtree because we picked X

05:08and Y and Z and that became A and B and C can't get that line right.

05:15I'm going to give up.

05:16So then we, I'm going to fix the labels here.

05:18So what is A belonging on the left?

05:20That's 34.

05:21What is B, which belongs in the middle?

05:23It's 42.

05:24What is C, which belongs on the right?

05:26That's 55.

05:27So now we have a perfectly balanced trinode subtree.

05:30Notice how this is a valid binary search tree.

05:32If the numbers were in a different order, this wouldn't be a valid binary search tree.

05:37And you'd have to try again with your ordering.

05:39And also this has to be a perfectly balanced trinode subtree.

05:42Otherwise, this probably wouldn't actually help if we, if we did a different output pattern,

05:46it wouldn't help the tree.

05:48So then the next thing we need to do is just double check that we don't have any nodes that

05:52are unaccounted for from the input pattern, the X, Y, Z nodes.

05:55So if we look at the, the 34 node, let's look at Z first, I guess we'll look at the

06:0134 node.

06:0334 had 42 as a child, but 42 is already handled.

06:06So that's actually okay.

06:08Then we look at the Y node.

06:10That's 42.

06:10It had 34 and 55 as children.

06:14The 34 was handled here and the 55 is handled here.

06:19So we actually are fine.

06:20We don't need to worry about that.

06:22Now we'll look at the X node.

06:24X node had no children.

06:25So we're pretty much done again.

06:28Like I said, in previous videos, there could have been up to four outstanding children.

06:32You know, each of these X, Y, Z nodes could have had its own children.

06:35Notice how 34 could have had one, 42 could have had one, 55 could have had two.

06:39So there would be four outstanding children.

06:42So we're actually done at this point with the outstanding children.

06:46There are none.

06:46So I'm ready to reattach this tree, I guess the rotated subtree into the regular tree.

06:52So these three nodes can just go away from our diagram.

06:55In code, you're not actually removing these nodes.

06:58You're just sort of, you know, reattaching pointers, but I'm going to redraw this in a

07:02way that looks kind of nice.

07:05And I'll just maybe redo this line real fast.

07:09So I'm going to do a blue line here.

07:14Okay.

07:15Now we have to recompute the balance factors.

07:18So I'm going to say that the 34 is a leaf.

07:24It's got balance factor of zero.

07:25Same for the 55.

07:26The 42 is perfectly balanced.

07:28And then we have to work our way up until we reach the root node.

07:31So the 27 node, it's got two nodes hanging off the right side and nothing on the left.

07:36So it's new balance factor is two.

07:38So it actually improved a little bit.

07:40The 22 node, one, two, three, it's got three nodes hanging off the right side and nothing

07:45on the left.

07:45So it improved a little bit to three.

07:46And I'm guessing that the 15 also improved to four and see the height on the left subtree

07:51of 15 is one, two, three, four, nothing on the left, which would mean zero.

07:56So we're done with this particular rotation, but because we see a node that has a balance

08:02factor of two or worse, we're not actually done rotating.

08:06This is still an invalid AVL tree.

08:08And under the hood, we would continually just, you know, rotate up and up and up the tree until

08:13everything looked like it was fixed.

08:15So again, the first node that's out of whack, or I guess the lowest node that's out of whack,

08:20we'll call that our Z node.

08:21So we're going to put a Z here.

08:23Let me get rid of this little piece of text.

08:26And then we have to find a child of Z with the tallest subtree.

08:30So there's no child on the left, which means we have to go to the right to find our Y

08:33node.

08:34Okay.

08:36Then we have to go find X through a child of Y, and we have to find the child with

08:42the taller

08:42subtree.

08:43Actually, the left child and the right child have the same height of their trees, of their

08:47subtree.

08:48So it doesn't actually matter which way we go.

08:50So let's, I don't know, for fun, let's just go to the left because it'll probably be harder.

08:55We'll say that the X node is 34.

08:59Be consistent.

09:00If you always, whenever you see like subtrees that are equal height, I don't know, maybe

09:05try to be consistent going left or right.

09:06But in this case, it doesn't really matter.

09:08Whatever.

09:09So we have XYZ.

09:11I'm going to type them up again right here.

09:13We're going to say X equals 34, Y is equal to 42, and Z is equal to 27.

09:19Let me just double check that 34, 42, 27.

09:23And then we'll produce ABC, which are the in order representations of XYZ.

09:29Again, imagine you're using pointers if you're doing this in code.

09:33So we have like A is equal to the least value, the one that would belong on the left.

09:37That's the 27.

09:39B should be 34, and C should be 42.

09:44And then, you know, just visually check.

09:46This is why I like to draw diagrams this way, so that all the nodes have their own space.

09:50The one that's furthest on the left is Z, and that ends up being A.

09:54The one in the middle is X.

09:55That's B.

09:56And the one on the right is C.

09:58That's 42.

09:58Why?

10:01Right.

10:02Yeah.

10:02Okay.

10:02So now that we've selected our ABC, we can start drawing the output pattern.

10:08So I'm going to like make a little copy of this.

10:11And I'm just going to very quickly try to draw a trinode subtree that is perfectly balanced.

10:17Maybe a little bit lower.

10:19They'll laugh at you.

10:21They won't.

10:22They will.

10:23I'm just kidding.

10:24Okay.

10:25Let me finish this line.

10:30All right.

10:32Fix the numbers real fast.

10:33So A is supposed to be on the left.

10:35So that's 27.

10:36That's already good.

10:37B is 34.

10:40C is 42.

10:41So now we have to just worry about the unaccounted for children of ABC or XYZ.

10:47So first, I'm going to look at X.

10:50Whoops.

10:52We look at X.

10:53It's 34.

10:54It had no children of its own.

10:56So we don't even have to worry about any of its children.

10:58So we're done.

10:59We look at Y.

11:00Y had two children.

11:01It had 34.

11:02But 34 was already handled up here.

11:05And it had a right child of 55.

11:07Oh, so we have a child that is unaccounted for now.

11:10So I'm going to grab this 55 and duplicate it over here.

11:13We got to put it somewhere.

11:14I don't know where just yet.

11:15You can probably figure it out.

11:16But I'm just going to put it over there.

11:18Now we're done looking for the Y.

11:21And then next we'll look at the Z node.

11:24So I'm going to do the Z node is 27.

11:28It had a 42 as a right child.

11:30But 42 was already handled in the output pattern.

11:33So we're done looking for outstanding children.

11:37So the next thing I'm going to do is figure out where the heck does that 55 go?

11:41Remember, we're trying to make valid binary search trees,

11:43which means there's only one place where this 55 node could actually go.

11:48If you stuck it on the left side, a greater value on the left of 27,

11:52that's invalid.

11:53That wouldn't work.

11:5555 is greater than 34.

11:56So it can't go on the left.

11:59It's greater than 42.

12:00So actually 55 belongs all the way on the right side.

12:03Because again, that's the only place it would actually work

12:05to allow us to still have a valid binary search tree when we were done placing it.

12:09So double check the subtree that you have written down after you're done doing all this stuff

12:14and make sure that the whole entire tree is a valid binary search tree.

12:18If not, you probably have to try again.

12:21Okay.

12:21So I'm going to duplicate this slide right here.

12:24And we're going to say that we've got four nodes ready to be inserted

12:27in place of these four nodes over here.

12:29One, two, three, four.

12:30So I'm going to just select all four of these nodes and just delete them.

12:37And reinsert the rotated, you know, the rotated nodes, which are the same nodes,

12:43but they're just, you know, they're drawn differently with, you know, different connections.

12:49And then I'm going to fix this connection over here.

12:52So that's 34 is now the right child of 22.

12:55Then I have to do the balance factors for all of the nodes that we rearranged.

13:00So the leaves are easy.

13:02As usual, they're just zeros.

13:04This 42 has a balance factor of one.

13:06And this 34 has a balance factor of also one.

13:09It's not perfect, but it's okay.

13:12Then we work our way up the tree until we find the root node.

13:15So now we're going to recompute the balance factor for the 22.

13:18Actually doesn't improve.

13:20If you notice, the right subtree has a height of one, two, three.

13:23There is no left subtree.

13:24So the balance factor is three.

13:26Same thing for this 15 nodes.

13:27So we made a little progress, not much.

13:30We have to keep going.

13:32So, you know, once again, I'm going to select the lowest node that's out of whack.

13:36Or I guess as I work my way up the subtree, I can see that three node is still out

13:40of whack.

13:41So I'm going to call that Z.

13:45Nope.

13:45Somebody remind me to do what types of rotations to talk about the rotation types.

13:51Somebody send me an email or a comment.

13:55I'm going to do it at the end of this video, but send me a comment anyway.

13:59So the Z node is the 22 node to find the Y node.

14:01We have to take a child of Z with the tallest subtree, but that's obviously going to be 34.

14:05There's no other choice.

14:07And now we actually do have an interesting choice to find the X node.

14:10It has to be a child of Y, but it's got to be the child with the tallest subtree.

14:14So for the first time we can kind of see that we, you know,

14:17we might've wanted to put X on the left or right, but it has to be on the right.

14:22We're not allowed to put it on the, on the left, at least for this method.

14:28So there we go.

14:29We have our X, Y, Z.

14:31I'm going to go ahead and do X is equal to 42 and Y is equal to 34 and Z

14:40is equal to 22.

14:41And then A, B and C are going to be the in order representations.

14:46Oops.

14:48A is going to be the least value.

14:49I can eyeball that.

14:50It's going to be 22 and I can look up at the texts, uh, and, and know that that's what

14:54it's going to be.

14:55So then 34 comes in the middle, 42 goes on the right.

14:58So now I'm ready to draw my output pattern.

15:01So I'm going to like select this real fast, duplicate it up here, make some copies.

15:09Making copies.

15:11Anyone?

15:12No.

15:13Okay.

15:13Just make, just wondering.

15:15Okay.

15:16I'm going to do this, do some connecting lines.

15:24So A is supposed to be on the left.

15:26That's 22.

15:27And then B is going to be, uh, 34 and C is going to be on the right.

15:33That's going to be 42.

15:34So we have a perfectly balanced trinode subtree.

15:37Now we've got to double check for outstanding children.

15:39So we start by looking at the Z node.

15:44Oh my God.

15:47Not as skilled as I think I am.

15:49We look at the Z node.

15:50Uh, it had a right child of 34, which is already handled over here.

15:53So we're fine that way.

15:55Uh, then we'll look at the Y node.

15:57The Y node was 34.

15:59It had a left child of 27 that is not accounted for in the output pattern.

16:03So I'm going to grab it.

16:04And then also, you know, when you're grabbing these unaccounted for children, double check

16:07that they might also have children of their own.

16:09If they do, we have to take them with the node that we're moving.

16:12So if 27 had any children, we would not be, you know, removing or rearranging connections.

16:18We would just take all of 27's children and just kind of, you know, let them stay in their

16:23position underneath 27.

16:25You know, we would not rearrange pointers that are further down, but in this case, what have

16:30I done?

16:31In this case, 27 doesn't have any, uh, children.

16:34Oh, I have to do a copy.

16:35That's why make a copy, put it somewhere.

16:38So now we're done with the 27 on the right side of 34.

16:42It had a child of 42, but that's already handled in the output pattern.

16:45So we don't need to worry about it.

16:46So 42, and then I'll just put like an arrow here.

16:52Now we're ready to look at the X node's children.

16:55So the X is 42.

16:57It had a right child of 55, which is also not accounted for in the output pattern.

17:01So I'm going to just move that over here.

17:06Okay, now we have to place these children in their appropriate positions.

17:11So the 55, if you think about it, there's only one position that the 55 could ever go

17:16to produce a valid binary search tree.

17:18So it can't go there.

17:19It's got to go all the way on the right side.

17:22So that's where we'll put it.

17:23Same thing for the 27.

17:25There's only one place it could go.

17:26It can't go here because it's less than 34.

17:29So it can't be on the right side of 34.

17:31It's going to be on the left side of 34.

17:33And if you look at where is it going to go with respect to 22, it can't go on the

17:37left.

17:37It has to go on the right because again, we need a valid binary search tree.

17:44So I'm just going to connect this line right here.

17:50And now we're done making our little output tree, subtree.

17:55So how many nodes did we have in the input tree?

17:57It was 22, 34, 42, and 55.

18:00So like five nodes.

18:01And if you look at the output pattern here, there's also five nodes.

18:03So we're pretty much ready to just kind of remove all of these nodes all the way up to that

18:1015.

18:10And we'll take 34 and make it the right child of 15.

18:14So I'm going to select all of this stuff, make it the right child of 15.

18:21And then I guess I'll just redo that line real fast.

18:25So this is a nicely formatted diagram.

18:28So we'll do what's going on with my computer.

18:32Okay, sometimes it lags.

18:35I'm going to, well, I guess I have to recompute all the balance factors now.

18:40So I'm going to do balance factors for the leaves.

18:43Pretty easy.

18:44The 22 and the 42 have a balance factor of one.

18:47Again, if this is confusing, see my previous videos.

18:51We practiced a lot of that.

18:52The balance factor for the 34 is going to be a zero.

18:54Remember, it's about the height of the left subtree versus the right subtree,

18:58which there's no difference, actually.

18:59They both have a height of two.

19:01It's, you know, just because there's a little diagonal bounce there on one side

19:04doesn't mean it counts against the height.

19:06So this subtree is awesome.

19:08Not perfect, but it's pretty good.

19:10We look at the 15.

19:12What's the new balance factor of the 15?

19:14It's actually three now because the height of its right subtree is three

19:17and the height of its left subtree is zero.

19:20So its balance factor improved to three.

19:22So we are making, you know, a little bit of progress.

19:25Now we know that the only node that's out of whack in the whole tree is the 15.

19:29So we're just going to call that our Z node for another rotation.

19:32So I'm going to put Z right here.

19:34And then we go down to find a child of Z, which would be Y.

19:37And there's no other choice.

19:39And then once again, we have to find a child of Y to find X.

19:43And we have to take the child that has the taller subtree.

19:45But both of these subtrees are equal.

19:47So I'm just going to go to the right for fun.

19:49I don't know.

19:50I'm going to do X over here on the on the right side.

19:55Hang on.

19:55Have I been doing this the easy way?

19:58Oh, yeah, let's let's go to the left just to make it more fun.

20:00I like a little bit of a bounce sometimes.

20:04Okay, so now we have X, Y, Z.

20:06I don't know why I say these things.

20:08We'll do X, Y, Z.

20:10X equals 22.

20:12Y is equal to 34.

20:13I say them for fun.

20:15Z is equal to 15.

20:17And then we're going to do A and B and C.

20:20So A is going to be the least value.

20:22So that's 15.

20:23B is going to be 22.

20:25C is going to be 34.

20:26Now we have a plan for our trinode subtree, our balanced trinode subtree.

20:32So I'm going to copy this over here a couple more times.

20:35This tree is probably going to be huge.

20:38I'm probably going to have to rearrange this a few times.

20:41Just do this over here.

20:43Make another copy over here.

20:45There's a lot of nodes that are going to be unaccounted for here.

20:48I think this was the example where we ended up just replacing the entire tree.

20:52Let's see.

20:53All right.

20:53I guess that's good enough.

20:56So I'm going to do the connecting lines.

21:00And then I'm going to update the numbers.

21:02So A is 15.

21:06And B is 22.

21:08And C is 34.

21:10So now one by one we have to look for any outstanding children of the nodes in the output pattern.

21:16So we look at, let's say, the Z first.

21:20The Z had a right child of 34, but that's already taken care of in the output pattern.

21:25So we don't have to do anything.

21:27Now we look at the Y.

21:29The Y had a left child of 22, but that's already taken care of in the output pattern.

21:33So we don't have to worry about that.

21:34It also had a right child of 42.

21:39So we don't have to worry about that.

21:41Sorry.

21:41We do have to worry about that.

21:42So I'm going to copy the 42 over here.

21:46And we're going to have to do something with it eventually.

21:48Now we're ready to look at the X node.

21:53So let me get rid of these lines real fast.

21:56If we're looking at the X node, X node is 22.

22:00It had a right child of 27.

22:01That is not in the output pattern.

22:03So that's something that's unaccounted for.

22:05I'm going to place it over here.

22:07Okay.

22:08Now we're ready to attach the nodes in the output pattern.

22:11Let me just bring something to your attention real fast.

22:15Notice how the 42 node, which was an outstanding child of one of the output pattern nodes,

22:20it had a child of its own, right?

22:21We said before, if any of these nodes on the bottom here, below the output pattern,

22:26if they had any children of their own, we would not change their topology.

22:31We would not assign them to different parents.

22:33They would just stay exactly where they are, which means just for the purposes of this diagram,

22:37I should probably also bring the 55 down as the right child of the 42.

22:41So I can remember, you know, that it was there and not totally forget it and ruin the tree.

22:4727 had no children, so it's fine.

22:49The 27 should be a left child of 34 because it's greater than 22 and it's less than 34.

22:55So I'm going to stick it right there.

22:57And then where would the 42 go?

22:59Well, it would be a right child of 34 because it's greater than 34.

23:04So maybe I should make the 27 like just a little bit more to the left.

23:09Okay.

23:10Then I'm going to reconnect.

23:13So the 34's left child is 27.

23:15It's right child is 42.

23:17And then, you know, this is easy to get wrong.

23:20Like I make mistakes all the time too.

23:21So I just want to double check that this is a valid binary search tree

23:24because I could have, you know, done the numbers incorrectly.

23:27So we have 15, 22, 27, 34, 42, 55.

23:31It all increases.

23:33It is a binary tree.

23:35So it's also a binary search tree.

23:36And then it's like, it satisfies all the other properties.

23:39So now how many nodes did I actually remove?

23:41Four, five, six.

23:42And there were only six nodes in the entire tree before we did this rotation.

23:47You know, Z is kind of the culprit of why this happened.

23:50So that means the rotated pattern is actually the final binary search tree.

23:55So I'm just going to erase the whole entire tree and put the rotated pattern in the middle here.

24:01Then we just have to recompute all the balance factors to make sure that we're done or that we're not

24:05done.

24:06So the leaves get zero.

24:09And then the 42 gets a one.

24:10And then the 34 gets a one because it's got a height of one on its left subtree

24:15and a height of two on its right subtree.

24:17Take the absolute value.

24:19The 22 node, I don't think that's quite finished yet.

24:22It's got a balance factor of two because it's here.

24:24Let's just clarify to make sure everybody's on the same page.

24:27Anytime I feel that I had to think even a little bit,

24:30I'll sometimes just kind of take a little step back and make sure everybody's okay.

24:35So the left subtree has a height of one.

24:36You can see that I highlighted the left subtree.

24:38The right subtree has a height of one, two, three.

24:41So one minus three.

24:43Take the absolute value.

24:44That's going to be two.

24:45So the balance factor of the 22 node is two, meaning we're not done rotating our tree.

24:51It could be a little bit better, a little bit faster.

24:54So maybe I'm going to move this whole thing over to the left a little bit.

24:58And then we'll call the 22 node the Z node because it's the first node that's out of whack.

25:05Then we have some more interesting choices, right?

25:08Remember before, if we're going to go down and to the left or down and to the right, it always

25:11seemed obvious.

25:12But now to find our Y, we could go left or right, but we have to go to the right

25:17because 34 has the taller subtree.

25:2115, it's a tree of just one.

25:23It's a height of one.

25:24And 34, it's a tree of height three.

25:25So we go to the right to find Y.

25:28To find X, again, we need to look at a child of Y with the tallest subtree.

25:32So that's not going to be 27.

25:33That's a height of one.

25:34It's going to be 42 with the height of two.

25:37So the X node is this over here.

25:39And now we're ready to talk about what is X, Y, Z, and A, B, C.

25:43So X is...

25:46I always forget to change the color before I type this.

25:48Okay.

25:49X is 42.

25:51Y is 34.

25:53Z is 22.

25:55And then we get A and B and C.

26:00Okay, so A is the least value, the one that would belong on the left.

26:03I mean, you can just look visually on the diagram again.

26:06Look at X, Y, Z.

26:0722 is way on the left, right?

26:08So that would have to be A because anything that starts leftmost should end up leftmost

26:15in terms of a well-drawn diagram.

26:19So B is going to be in the middle.

26:20That's the 34.

26:21And then C is going to be the greatest value, which is 42.

26:24Again, C42 is the rightmost value both before and after we decided what is X, Y, Z, and A, B,

26:31C.

26:31So we've got that.

26:33I'm going to go ahead and start copying some nodes here for another new diagram.

26:38We're going to say...

26:40We got that.

26:42Give it a little copy.

26:45Give it another little copy.

26:47Give it a copy.

26:49Then I'm going to draw my connections.

26:52Dang, how long is this video?

26:53Man, I knew this was going to be a gnarly example.

26:57That's why I like doing it.

27:00Okay.

27:02Fix the numbers real fast.

27:04So the 27 is A.

27:06It's 22.

27:07And then this is going to be B, which is 34.

27:09And then 27 or the rightmost node is going to be the 42.

27:13Then we start looking at children that might be unaccounted for in our target pattern.

27:18So I'm going to duplicate this and we'll say start by looking at Z.

27:25It had a left child of 15, which is unaccounted for in the output pattern.

27:29So I'm going to move 15 over here somewhere.

27:31And then we look at the 34.

27:37That's already accounted for in the output pattern.

27:40So we're done looking at Z's children.

27:42So I'm just going to do this.

27:44Now we're ready to look at Y.

27:45Y had a left child of 27.

27:48That's actually unaccounted for.

27:50So I'm going to move the 20.

27:51I'm going to copy the 27 over here.

27:54And then we look at the 42.

27:57The 42 is already handled in the output pattern.

27:59So we don't have to worry about it.

28:01Okay.

28:02Now we're ready to look at the X nodes children.

28:05So we look at X.

28:06It had a right child of 55.

28:09That's also not accounted for in the output pattern.

28:11So I'm going to make a copy.

28:12So we have like three nodes to worry about.

28:14And then you know just for diagram purposes.

28:17In the code this would be easy to do.

28:18But for the diagram we have to make sure.

28:20Are we dragging any of these unaccounted for children away from.

28:24Their other children that they might have.

28:26So 55 it has no children.

28:2827 it has no children.

28:3015 also has no children.

28:32So these are pretty easy.

28:33So just visually.

28:36I'm going to rearrange.

28:38I lost my camera.

28:39What happened?

28:41Test test test.

28:41Whoa I'm tripping.

28:42So I had a technical issue with my camera.

28:45I had to edit out.

28:46I guess a little portion where I was super confused and screaming.

28:50And now I think we're okay.

28:51So we can continue the video.

28:53So we've just looked at all the children that are unaccounted for.

28:57And accounted for them.

28:59That's so nice of us.

29:01And we're going to have to place them somewhere.

29:03So this 15 again.

29:04It can't go anywhere over here on the right side.

29:06That would be an invalid binary search tree.

29:08It's actually got to go on the left of the 22.

29:11It's the only place it could possibly go.

29:14Same thing for the 55.

29:15Where is that going to go?

29:16I don't know.

29:16Maybe like all the way to the right.

29:18Because that's the only numerically valid place that it could go.

29:21To have a valid binary search tree.

29:23What about the 27?

29:24Can't go on the right of 34.

29:26It's too small.

29:27It ends up going on the right of 22.

29:29So now we've placed the children to account for them.

29:34And I'm going to just like draw my connecting lines real fast.

29:38And then.

29:41How many nodes do we have here?

29:43Let's see.

29:43The 22.

29:44One, two, three, four, five, six.

29:46One, two, three, four, five, six.

29:47Oh, actually that's every single node in the tree.

29:49Just like last time.

29:50We could probably again guess that that would have happened.

29:53Because it might be likely to happen.

29:56Because the Z node here.

29:57Was actually the root node of the tree.

30:00So.

30:02I'm just going to.

30:04You know replace the entire tree.

30:06And say that we're done rotating now.

30:08So we'll just do this.

30:10Put this in the middle.

30:12And then recompute all the balance factors.

30:14Just to check to see if we're done.

30:15You can probably tell already.

30:16This is a pretty decent tree.

30:18So.

30:19We might not have to rotate.

30:20But I'm going to go ahead and just double check anyway.

30:23So the leaves get zeros.

30:25And the 22 gets a zero.

30:27Because it's got left and right subtrees of equal height.

30:29The 42 has a one.

30:31And the 34 also has a zero.

30:33Because it's left and right subtrees are equal height.

30:36This is maybe another good opportunity for me to point out.

30:38That it's not about weight or mass.

30:41On the left versus right subtrees.

30:42It's just about height only.

30:44So.

30:44Even though there are less nodes in the right subtree.

30:48The fact remains that the heights are the same.

30:50So actually that's a zero for the root node.

30:52This is now finally a valid AVL tree.

30:55We have rotated it enough.

30:57It is now considered log time again.

31:00It's going to be fast to search.

31:02And insert and remove.

31:04And all that stuff.

31:05So.

31:05This is pretty great.

31:07We are now officially done with this example tree.

31:10So.

31:10Thank you so much for watching this video.

31:12I hope you learned a little bit of fun.

31:13And had a little bit of stuff.

31:17And I hope you enjoyed doing this tree with me.

31:20It's always a little stressful.

31:21Because it's like a half hour tree.

31:23And I always wonder like.

31:24Did I make a mistake five hours ago?

31:26I don't even know.

31:27So.

31:28I guess I'll see you in the next video.

31:29Thanks for hanging in there with me.

31:33Hey everybody.

31:34Thanks for watching this video again.

31:36From the bottom of my heart.

31:37I really appreciate it.

31:38I do hope you did learn something.

31:40And have some fun.

31:41If you could do me a please.

31:42A small little favor.

31:44Could you please.

31:45Subscribe.

31:45And follow this channel.

31:47Or these videos.

31:48Or whatever it is you do.

31:49On the current social media website.

31:51That you're looking at right now.

31:53It would really mean the world to me.

31:54And it will help make more videos.

31:56And grow this community.

31:57So we'll be able to do more videos.

31:59Longer videos.

32:00Better videos.

32:01Or just I'll be able to keep making videos in general.

32:03So please.

32:04Do me a kindness.

32:06And subscribe.

32:07You know sometimes.

32:08I'm sleeping in the middle of the night.

32:10And I just wake up.

32:11Because I know somebody subscribed or followed.

32:13It just wakes me up.

32:14And I get filled with joy.

32:15That's exactly what happens every single time.

32:17So you could do it as a nice favor to me.

32:19Or you could.

32:19You could troll me.

32:20If you want to just wake me up in the middle of the night.

32:22Just subscribe.

32:23And then I'll.

32:23I'll just wake up.

32:24I promise.

32:25That's what will happen.

32:27Also.

32:27If you look at the middle of the screen right now.

32:29You should see a QR code.

32:31Which you can scan.

32:32In order to go to the website.

32:33Which I think is also named somewhere at the bottom of this video.

32:36And it'll take you to my main website.

32:38Where you can just kind of like see.

32:40All the videos I published.

32:41And the services.

32:42And tutorials.

32:43And things that I offer.

32:44And all that good stuff.

32:45And.

32:48If you have a suggestion.

32:49For.

32:51Clarifications.

32:52Or errata.

32:53Or just future videos.

32:54That you want to see.

32:54Please leave a comment.

32:56Or if you just want to say.

32:56Hey what's up.

32:57What's going on.

32:58You know.

32:59Just send me a comment.

33:00Whatever.

33:00I also wake up for those.

33:01In the middle of the night.

33:02I get.

33:02I wake up in a cold sweat.

33:03And I'm like.

33:05It would really.

33:06It would really mean the world to me.

33:07I would really appreciate it.

33:09So.

33:09Again.

33:10Thank you so much for watching this video.

33:12And.

33:13Enjoy the cool music.

33:15As I fade into the darkness.

33:18Which is coming for us all.

33:20Thank you so much.

33:21Thank you so much.

33:29Thank you so much.

33:34Thank you so much.

33:35Thank you so much.

33:36Thank you so much.

33:38Thank you so much.

33:41Thank you so much.

33:42Thank you so much.

36:24Hey there.

36:25Let's rotate an ABL tree.

36:34Test, test, test.

36:35Whoa, I'm tripping.

Category

Transcript

Comments

Recommended