- 2 days ago
Watch me build an AVL tree step by step with linear data that would normally create a terrible unbalanced BST. See insertions, balance factor calculations, and rotations in action.
Perfect follow-up to my BST and AVL intro videos.
00:00 Introduction to AVL Tree with Bad Data
00:14 Previous Videos on BST and AVL Trees
00:28 Practice Example Building Step by Step
00:50 Adding First Node 12
01:11 Adding Node 21
02:10 Adding Node 30 and First Rotation
04:03 Recomputing Balance Factors
05:08 Adding Node 38
08:03 Adding Node 42 and Second Rotation
12:51 Recomputing Balance After Rotation
14:09 Adding Node 55 and Third Rotation
18:55 Placing Unaccounted Nodes
19:21 Final Tree and Balance Factors
20:07 Conclusion and Thanks
AVL tree, AVL trees, binary search tree, self balancing tree, tree rotations, data structures tutorial, binary search tree insertion, AVL rotation example, computer science, programming tutorial, balance factor, BST, data structures
=-=-=-=-=-=-=-=-=
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
Perfect follow-up to my BST and AVL intro videos.
00:00 Introduction to AVL Tree with Bad Data
00:14 Previous Videos on BST and AVL Trees
00:28 Practice Example Building Step by Step
00:50 Adding First Node 12
01:11 Adding Node 21
02:10 Adding Node 30 and First Rotation
04:03 Recomputing Balance Factors
05:08 Adding Node 38
08:03 Adding Node 42 and Second Rotation
12:51 Recomputing Balance After Rotation
14:09 Adding Node 55 and Third Rotation
18:55 Placing Unaccounted Nodes
19:21 Final Tree and Balance Factors
20:07 Conclusion and Thanks
AVL tree, AVL trees, binary search tree, self balancing tree, tree rotations, data structures tutorial, binary search tree insertion, AVL rotation example, computer science, programming tutorial, balance factor, BST, data structures
=-=-=-=-=-=-=-=-=
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:00Hey there, let's build an AVL self-balancing binary search tree with some really bad data.
00:05It's all going to work out, trust me.
00:13Okay, so hopefully by now you've seen my other videos where we talked about how to define
00:17binary search trees, how to build them, search through them, add, delete, all that stuff.
00:21And also AVL trees, what are rotations, why do we rotate, how does the AVL tree maintain
00:25itself and so forth.
00:27And this is just going to be a practice example.
00:30In the previous video that I recorded regarding AVL trees, I started off with a really long
00:35and gnarly linear tree and then I suddenly turned on AVLness and we rotated the crap out
00:42of it for about 30 minutes until it was really, really good.
00:46So now I'm just going to build a tree one step at a time.
00:48Suppose for the sake of argument that you have some really bad data.
00:52You know, a long time ago, I love telling this story.
00:54I think I've told it already.
00:55A long time ago, you know, my grandma, before she passed on, she was kind of bitter and she
01:00had some enemies in the neighborhood.
01:01She used to call the cops on her neighbors for gossip.
01:06She had a neighbor who kind of feuded with her.
01:09And at one point, according to my grandma anyway, my neighbor like didn't like my grandma's tree.
01:14And so one day when my grandma was looking out into the backyard through the back window because
01:20she likes to yell at ducks who are swimming in her pool, she noticed that the other little
01:25old lady's arm just kind of went over my grandma's fence with a spray bottle and then sprayed
01:30her tree.
01:30And then my grandma's tree died.
01:33So this kind of thing I like to call, you know, tree poisoning or data poisoning or bad
01:38data, it can affect the binary search tree and make it really, really, really slow.
01:42But in AVL trees, if we have bad data, it should actually end up being fine.
01:46So I'm just going to say we're poisoning our grandma's tree here.
01:49You like that story?
01:51Poisoning our grandma's tree with some bad data.
01:54I'll just do maybe five pieces of data.
01:57We could go further than that, but it's going to be a super long video if we do.
02:02So we're going to add these pieces of data one by one.
02:05So that means the first thing I'm going to do, remember, we are kind of just regularly,
02:09you know, building a regular binary search tree.
02:11It's just that the difference is after we modify the topology in some way, we'll just
02:16check to see that it satisfies the rules of an AVL tree.
02:19And if it doesn't, then we're going to start performing rotations to make sure that it's
02:23self-balancing.
02:24So we'll add the 12 first.
02:26So let me see if I can draw a little arrow just indicating, yeah, we're going to add
02:31this number right now.
02:34Well, I'm going to do an ellipse for a node.
02:37And you know, like for binary, what is that flying saucer for binary search trees?
02:43It's like, well, if there is no data already, if the tree is empty, then the first piece
02:48of data you add is going to end up being the root node.
02:50So that's it.
02:51We have our root node here.
02:55See my other videos if you want more practice on building trees.
02:59So we're just going to call that the root node.
03:01And then we're going to compute its balance factor, which is obviously just going to be
03:05a zero.
03:06So that was super easy.
03:08Now we're going to move on to adding the next piece of data.
03:13Things are getting a little bit worse.
03:15This is going to be a linear tree.
03:17If it weren't for our trusty, I guess, AVL functionality.
03:22So the 21, I'm going to maybe just duplicate this node right now and set that to a 21.
03:29And then we'll figure out where does the 21 go?
03:31Well, it can't be the root because the root is already occupied.
03:3421 is larger than 12, so it's got to be on the right side.
03:37So the 21 is going to be the right child of the root node.
03:40So I'm just going to do my connecting line.
03:44Connecting line right here.
03:48And then we have to recompute balance factors.
03:51So the 21 is the thing we just added.
03:53We have to compute that.
03:54Then we have to work our way up the tree until we hit root.
03:57So we see the root node.
03:59It now has a balance factor of one.
04:00So it got a little bit worse.
04:03But we don't see two or worse.
04:05So that means this is currently a valid AVL tree and we don't have to do any rotations.
04:10So now it's time to add the 30.
04:16Just realized I could just upload like 100 videos like this and I think you'd all be pretty happy.
04:20Or some people would be pretty happy.
04:23I don't know if I want to do that to myself.
04:25Maybe I will.
04:26So we're going to add the 30 node.
04:27So first I'm just going to duplicate some node.
04:30And I'm going to call it 30.
04:33Then we have to figure out where the 30 node belongs.
04:36It's not going to be the root node that's already occupied.
04:3830 belongs on the right side of 12.
04:40But we can't use that right child.
04:42It's occupied.
04:4330 belongs on the right side of 21.
04:45So, you know, it makes sense.
04:47We called this linear data that would make a linear tree.
04:50So everything ended up being on the right side.
04:53So far it's just getting worse and worse.
04:55But now the AVL-ness is going to kind of come to the rescue.
04:58We have to recompute the balance factors.
05:00So the 30 has a 0.
05:01The 21 ends up having a 1.
05:03Again, if you want practice computing balance factors, see my other videos.
05:07The 12 has a balance factor of 2.
05:09And now we know right away this is not a valid AVL tree anymore because we have a balance factor
05:15that is bad.
05:15It's too bad.
05:17So we have to now select an XYZ trinode subtree so we can perform a rotation.
05:23I'm sure you can imagine it's just going to end up being three nodes that are perfectly balanced like that.
05:27But let's do it one step at a time.
05:31So the Z node is going to be the 12.
05:33That was the first node that we noticed that was out of whack or like I guess the highest node
05:37of the lowest nodes.
05:40And then we have to find Y by taking a child of Z.
05:43There's only one possible child we could choose.
05:45So that's going to be Y.
05:46And then we find X by taking a child of Y.
05:49There's only one choice again.
05:50So it's just going to be there.
05:51Now we have XYZ.
05:54And I'm going to write it down real fast.
05:56Let me just put this in black ink.
05:58So X is 30 and Y is 21 and Z is 12.
06:04Then we're going to do A and B and C which are going to be just in order representations of
06:09XYZ.
06:10So again think in your code you would be doing pointers.
06:13You'd probably want to make three more pointers.
06:15Call them ABC.
06:16If you had a rotation function, the rotation function after you selected three nodes to rotate it would receive XYZ.
06:23And then you say let's reorder it.
06:24You know XYZ and call them ABC.
06:27So A is going to be 12 and B is going to be 21 and C is going to be
06:3130.
06:31It should, you know, ascend from left to right if we're not supporting duplicates in our tree.
06:37And then I'm going to just, you know, make some nodes for our target pattern here, our output pattern.
06:44So I'm going to like make some nodes here, kind of place them in the perfect AVL tree output pattern.
06:56A perfectly balanced tri-node subtree.
06:58I'm just going to reconnect this.
07:00The output pattern is always the same.
07:02You know, it always starts this way because this is better than the linear pattern that we have above.
07:06And then I just have to update the numbers.
07:08So the left child is going to be 12, the right child is going to be 21, sorry, the center
07:13is going to be 21, the new parent.
07:15And the right child is going to be 30.
07:16Okay.
07:17Now we look for any nodes that are children of the input nodes that have been unaccounted for.
07:22You can tell easily that all nodes are being used.
07:26So we don't even have to worry about that step.
07:28So now that we have our tri-node subtree, which is perfectly balanced, we are ready to just sort of
07:33override it into the diagram.
07:35And since the diagram only has the three nodes to begin with, I could pretty much just like erase everything,
07:40call it a day, and say this is the new tree, the new rotated tree.
07:45So I'm just going to maybe put this in the middle, I guess.
07:50I'm going to delete this over here and recompute the balance factors.
07:54So the leaves get a zero, get zeros, and this 21 also gets a zero because it's perfectly balanced.
08:03Next thing is, let's move on to adding the number 38.
08:06So we'll add the 38 here.
08:09And same thing that we did before.
08:11Let's make a copy of one of the nodes for our diagram.
08:14Let's call it the 38.
08:17And then let's figure out where it belongs.
08:19It's not going to be the new root node because that's occupied.
08:22It belongs on the right side.
08:23It's not going to be the right child because that's occupied.
08:25It belongs on the right side of the 30.
08:27It couldn't go on the left.
08:28That would be an invalid binary search tree.
08:30So I'm just going to stick it right there and do a connection.
08:38And then we're going to update the balance factors.
08:40So the 38 is a leaf.
08:41It gets zero.
08:42The 30 gets a one.
08:44And the 21 also gets a one because its left subtree is a one and its right subtree is two
08:50or height.
08:51And the difference is just one.
08:53Remember we don't really need to update the 12 or any nodes that are not directly above the node that
08:57we just added or removed.
09:00So if you look at this tree, there's a little bit of imbalance, but nothing is two or worse.
09:05So we don't actually need to perform a rotation.
09:08This is already a valid ABL tree.
09:10So I'm going to move on to adding the next number.
09:12Let's add a 42.
09:15Same thing.
09:16We're going to, you know, duplicate a node for our diagram and we're going to call it the 42.
09:23Where does it belong?
09:24Well, we start by looking at root.
09:27That's occupied.
09:2842 belongs on the right side of 21.
09:30The right child is occupied.
09:3142 belongs on the right side.
09:33Belongs on the right side.
09:34I mean, it's always going to be on the very right of the diagram because that's the poison data that
09:38we received.
09:40So I'm going to put it over there and then connect the child pointer indicating line, the parent-child relationship.
09:48And then let's update the balance factor.
09:51So 42 gets a 0.
09:5338 gets a 1.
09:54And 30 gets a 2 now because it's got 2 height of subtree on its right side and no subtree
10:01on its left side.
10:02The 21 we should update.
10:04Left subtree is a 1.
10:05Right subtree is a 3.
10:06Oh, it's actually going to be 2.
10:09So we have two instances of the number 2.
10:14And again, which one do we actually want to rotate?
10:16By the way, here's how I like to eyeball it.
10:17You can kind of see, oh, there's two levels of difference in terms of the root node.
10:21Which one do we rotate first?
10:23Well, as low as possible because if we rotate the 30, it might end up fixing the 21.
10:28So we don't want to do any more work than we have to.
10:31So I'm just going to maybe move this over here a little bit and select our XYZ.
10:37Hang on a second.
10:38I think I just like didn't do a snap to grid when I was doing that.
10:44Okay, hang on.
10:47Okay, so we've got to choose our XY and Z.
10:49We're going to say that the 30 is Z, the lowest node possible that is out of whack.
10:55And then we hop down to a child of Z to find Y.
10:58We hop down to a child of Y to find X.
11:01And so now we have our XYZ.
11:03I'm just going to write them down real fast.
11:05X is 42, Y is 38, Z is 30.
11:11And then I'm going to change the ink real fast.
11:14And then we have to get ABC.
11:16So A is the least value, B is the one that belongs in the middle, and C is 42.
11:23Now we have our ABC.
11:25We're ready to draw our output pattern, our target pattern.
11:28So I'm just going to put like some nodes up here.
11:33Duplicate that a couple times.
11:40All right.
11:42Not the prettiest, but I'll take it.
11:44I'm going to do my connecting lines.
11:51And then I have to update the numbers.
11:54So A is 30, and then B is 38.
11:59And C is 42 still, so we'll just leave that as is.
12:03Now we have to look for children of any of the output pattern nodes that are unaccounted for.
12:08So we'll first look at the Z node here, the 30.
12:11It had a write child of 38.
12:12That's already handled as the Y node.
12:15So we don't need to worry about the 38.
12:18Okay.
12:19Next we look at the Y node.
12:21It had a write child of 42.
12:22That's also handled in the output pattern.
12:25So we don't have to worry about that.
12:27Then the 42 had no children, so we don't need to really do anything.
12:30This is going to be super easy.
12:33Again, we could have found up to four unaccounted for children.
12:36Just as a reminder, the Z could have had a left child.
12:38The Y could have had a left child.
12:40And the X could have had two children, at least in this particular pattern.
12:46Oh, I think in my previous video, I didn't name off all the rotation types.
12:49Whoops.
12:51Okay.
12:53So now I'm ready to just kind of like move this into the diagram.
12:56So the 30 and 38 and 42, we can just kind of get rid of that.
13:01And move it into the, move the, move the rotated output pattern into the diagram.
13:07Like this.
13:08We'll make the 38 the right child of 21.
13:10I want to make it go a little bit more to the right so that we have a nicely drawn
13:13diagram.
13:15So that all the nodes have space.
13:17So it's easy to debug visually.
13:19It's easy to just kind of eyeball it.
13:22Then I'm going to update the balance factors.
13:24So the 42 has 0.
13:25The 30 has 0.
13:26The 38 has 0.
13:27Nice.
13:28The 21, hopefully that improved.
13:30The left subtree has a height of 1.
13:32The right subtree has a height of 2.
13:33So actually the balance factor of the 21 node improved to 1.
13:39We are now done rotating and we have a valid AVL tree.
13:43And we could have had, you know, a tree that was just totally linear all the way down to the
13:48right.
13:49It could have worked out that way if we weren't using AVL trees.
13:54And we would have had a really slow binary search tree.
13:56But with AVL trees, this is like, you know, a lot faster reasonably.
14:00And you can imagine if I added some more data.
14:02Let's see.
14:03How long is this video?
14:04Oh, it's this video.
14:06It's already 15 minutes.
14:09Let's add one more piece of data.
14:10Just for fun, Zars.
14:12I'm going to add 55.
14:14Anybody remember that old song, I Can't Drive?
14:1655.
14:18So we're going to add the 55.
14:22I'm going to say, here it is.
14:24And then I'm going to do just like a new node duplicate.
14:29I'm going to stick a 55 in there.
14:33And then where does the 55 belong?
14:35Well, it's not going to go at the root node.
14:36It belongs on the right side.
14:38Not going to go there.
14:38It belongs on the right side.
14:39Not going to go there.
14:40It belongs on the right side.
14:40We just end up going all the way to the right.
14:43Pretty much.
14:44Okay, so I'm going to say it belongs there.
14:47And I'm going to connect it.
14:51And then we update the balance factors.
14:54So 0 here.
14:55And then the 42 becomes a 1.
14:57And the 38 becomes a 1.
14:59And the 21 becomes a 1 on the left and 3 on the right.
15:04Which means we have a balance factor of 2.
15:06So now the 21 node is imbalanced.
15:08This is no longer a valid ABL tree.
15:10We've got to rotate to make it better.
15:13So once again, we look at the first node that's out of whack.
15:16Or the lowest node that's out of whack.
15:17It's going to be the 21.
15:18We call it our Z.
15:19And then we find a child of Z with the tallest subtree.
15:23So is it going to be the 12 or the 38?
15:25It's definitely going to be the 38.
15:27Because 38 is the taller subtree.
15:30Same thing to find X.
15:31It's got to be a child of Y.
15:32Should we go left or should we go right?
15:34We have to go right because that's the taller subtree.
15:37So now we have our X, Y, and Z.
15:42I think I've been forgetting to like delete stuff.
15:45Let me type that up over here.
15:47We'll say X and Y and Z.
15:49X is 42.
15:51Y is 38.
15:53Z is 21.
15:55X, Y, and Z.
15:58And then we do A and B and C.
16:02So A is the least value, 21.
16:04B is the one that belongs in the middle.
16:06C is the one that belongs on the right side.
16:10Now we're ready to draw our target output pattern.
16:13So I'm going to do this.
16:14A little duplication.
16:20Do you like when I say, oh, we're going to do this.
16:22We're going to do this.
16:23We're going to do this.
16:23Because sometimes I just go, I don't like it.
16:25And I don't think people like it when I say that.
16:29Okay.
16:33I'm going to connect these real fast and then change the numbers to match.
16:37I think I made that one.
16:39I think it's okay.
16:40I can never tell if it's perfectly symmetrical.
16:43I can't do it perfectly symmetric.
16:47All right.
16:48So A is going to be on the left.
16:49That's 21.
16:50B is in the middle.
16:51That's 38.
16:52C is on the right.
16:53That's 42.
16:55Then we have to look for children of the output pattern that are unaccounted for.
16:59So we're going to do a look at the Z node.
17:03The Z node had 12, which is unaccounted for as a left child.
17:07So I'm going to copy the 12 somewhere.
17:10We'll deal with it in a second.
17:12Then we look for the right child of 21.
17:16That's a 38.
17:16That's already in the output pattern.
17:18So we don't have to worry about that anymore.
17:20And then we look at the Y node.
17:22So Y had left child was 30.
17:25That's not accounted for.
17:26So I'm going to copy that.
17:28Put it somewhere else.
17:30And then its right child was 42.
17:32That's already handled in the output pattern.
17:34So we're done there.
17:35I'm going to duplicate this.
17:37And then we look at the X node.
17:40The 42, it had a right child of 55.
17:42That also was not accounted for.
17:44So I'm going to just copy it over here and we'll do something with it.
17:48Okay, we're done looking for unaccounted for children.
17:52Again, if you were just rearranging pointers, you don't really have to worry about this in
17:56your code.
17:56But since we're doing a diagram, we have to double check that none of these nodes at the
18:00bottom here, the unaccounted for children, have children of their own.
18:03If they did, the children would have to come with them.
18:06So 55, no children.
18:0912, no children.
18:1030, no children.
18:12So those are fine.
18:13If there were any children underneath, they would just stay on those nodes.
18:17So now we have to figure out who goes where.
18:19So the 12 is the least value.
18:21That means it's going to go probably in the leftmost position compared to the other ones.
18:26But if we figure out like where does this belong in the binary search tree, it belongs
18:30right here as the left child of 21.
18:33The 30 node, same thing.
18:34Where does it belong?
18:35It belongs between the 21 and 38.
18:37That's the only place it could possibly go.
18:41And then the 55, it belongs on the right side of 42 for the same reason.
18:48Okay, I'm going to do my connecting lines real fast.
18:55If I don't do my connecting lines, then I don't like it.
19:02So now we have how many nodes in the output pattern?
19:04We have 1, 2, 3, 4, 5, 6.
19:06And then in the input pattern, there's also just 6.
19:09Which means the final tree after rotation is just everything that we've written on the right
19:17side.
19:17So I'm just going to erase all of this stuff.
19:19Get rid of that too.
19:20And then move all of this nodes over to the left and then move all of this nodes over to
19:24the left.
19:25Call that the tree.
19:27This is now the tree.
19:29And then I just have to recompute the balance factors to make sure that everything is okay.
19:33So the leaves get 0, 0, 0.
19:38The 42 gets a 1.
19:40The 21 is perfectly balanced.
19:41So that gets a 0.
19:42The 38 is also perfectly balanced.
19:45Again, it's not about weight or mass.
19:47Even though there are more nodes on the left subtree, it's all about the height.
19:50Height of the left subtree is 2.
19:52Height of the right subtree is 2.
19:53So 38 is actually perfectly balanced.
19:57Because there are no nodes that have a balance factor of 2 or worse, we are done rotating
20:03this tree.
20:03This is a valid ABL tree.
20:06And it's pretty fast.
20:07So I think that's pretty much it.
20:09That's all I wanted to go through today for this video.
20:12Thank you so much for following along.
20:14I hope you learned a little bit of stuff and had a little bit of fun.
20:17And I will see you in the next video.
20:19Have a great night and or day and or week and or weekend.
20:29Hey everybody.
20:30Thanks for watching this video again.
20:31From the bottom of my heart, I really appreciate it.
20:33I do hope you did learn something and have some fun.
20:36If you could do me a please, a small little favor, could you please subscribe and follow
20:41this channel or these videos or whatever it is you do on the current social media website
20:46that you're looking at right now.
20:48It would really mean the world to me and it'll help make more videos and grow this community.
20:52So we'll be able to do more videos, longer videos, better videos, or just I'll be able
20:57to keep making videos in general.
20:58So please do me a kindness and subscribe.
21:03You know, sometimes I'm sleeping in the middle of the night and I just wake up because I
21:06know somebody subscribed or followed.
21:08It just wakes me up and I get filled with joy.
21:10That's exactly what happens every single time.
21:12So you could do it as a nice favor to me or you could troll me if you want to
21:16just wake
21:16me up in the middle of the night.
21:17I just subscribe and then I'll, I'll just wake up.
21:19I promise that's what will happen.
21:22Also, uh, if you look at the middle of the screen right now, you should see a QR code,
21:26which you can scan in order to go to the website, which I think is also named somewhere at the
21:30bottom of this video.
21:31And it'll take you to my main website where you can just kind of like see all the videos
21:35I published and the services and tutorials and things that I offer and all that good
21:39stuff.
21:40And, uh, if you have a suggestion for, uh, uh, clarifications or errata or just future videos
21:49that you want to see, please leave a comment.
21:51Or if you just want to say, Hey, what's up, what's going on?
21:53You know, just send me a comment, whatever.
21:55I also wake up for those in the middle of the night.
21:57I get, I wake up in a cold sweat and I'm like, it would really, it really mean the world
22:02to me.
22:03I would really appreciate it.
22:04So again, thank you so much for watching this video and, um, enjoy the cool music as,
22:11as I fade into the darkness, which is coming for us all.
22:30And, um, enjoy the fun and enjoy the fun.
22:36Bye.
22:45Bye.
22:47Bye.
22:48Bye.
22:49Bye.
22:49Bye.
25:26It should all work out according to plan.
25:27Trust me.
25:29Anyway, um, sure.
Comments