- 2 days ago
In this video we walk through a real example of maintaining an AVL tree by performing a rotation. We start with an unbalanced tree, compute balance factors, identify the Z Y and X nodes, and apply a double right rotation to restore balance. Perfect follow-up if you've seen the basics of binary search trees and AVL trees.
Watch as we turn an invalid AVL tree into a perfectly balanced one with clear step-by-step instructions.
If you're learning data structures and algorithms, this practical example will help you understand when and how to rotate.
00:00 Introduction to AVL Tree Rotation
00:14 Prerequisites and Previous Videos
00:36 AVL Trees Overview
00:40 Types of Rotations and Balance Factors
01:01 Examining the Example Tree
01:24 Confirming Binary Search Tree Properties
01:27 Computing Balance Factors
01:39 Identifying Imbalance at Node 65
02:01 Locating the Z Node
02:54 Finding Y and X Nodes
04:08 Assigning X Y Z Values
04:33 Creating ABC In-Order Representation
04:58 Drawing the Target Rotation Pattern
05:34 Updating Node Values in Pattern
06:04 Checking Unaccounted Children
07:00 Reattaching Nodes and Performing Rotation
07:56 Recomputing Balance Factors
08:24 Updating Root Balance Factor
08:41 Resulting Perfectly Balanced Tree
08:48 Identifying Double Right Rotation
09:06 Explaining the Rotation Process
10:16 Conclusion and Next Video Teaser
11:56 Channel Promotion and Outro
15:48 Final Hello and Recap
avl tree, avl tree rotation, binary search tree, data structures, self balancing tree, tree rotation, double rotation, balance factor, avl tree example, computer science, algorithms, bst, coding tutorial
=-=-=-=-=-=-=-=-=
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
Watch as we turn an invalid AVL tree into a perfectly balanced one with clear step-by-step instructions.
If you're learning data structures and algorithms, this practical example will help you understand when and how to rotate.
00:00 Introduction to AVL Tree Rotation
00:14 Prerequisites and Previous Videos
00:36 AVL Trees Overview
00:40 Types of Rotations and Balance Factors
01:01 Examining the Example Tree
01:24 Confirming Binary Search Tree Properties
01:27 Computing Balance Factors
01:39 Identifying Imbalance at Node 65
02:01 Locating the Z Node
02:54 Finding Y and X Nodes
04:08 Assigning X Y Z Values
04:33 Creating ABC In-Order Representation
04:58 Drawing the Target Rotation Pattern
05:34 Updating Node Values in Pattern
06:04 Checking Unaccounted Children
07:00 Reattaching Nodes and Performing Rotation
07:56 Recomputing Balance Factors
08:24 Updating Root Balance Factor
08:41 Resulting Perfectly Balanced Tree
08:48 Identifying Double Right Rotation
09:06 Explaining the Rotation Process
10:16 Conclusion and Next Video Teaser
11:56 Channel Promotion and Outro
15:48 Final Hello and Recap
avl tree, avl tree rotation, binary search tree, data structures, self balancing tree, tree rotation, double rotation, balance factor, avl tree example, computer science, algorithms, bst, coding tutorial
=-=-=-=-=-=-=-=-=
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 maintain and rotate an avl tree which is a self-balancing binary search tree
00:15okay all right so hopefully by now you've seen my other videos if you haven't you probably won't
00:20understand this unless you've seen other videos elsewhere uh but uh in my previous videos we
00:27talked about what is a binary search tree how to make one how to define one how to know you're
00:30looking at one how to build one search insert remove all the operations and time complexities
00:35and then we talked about avl trees which are a self-balancing binary search tree
00:40and we talked about what are the different types of rotations you can do why would you rotate
00:44how do you compute balance factors how do you know when it's time to rotate you know how do you
00:48do
00:48the rotation stuff like that so this is just going to be one example tree and we're just going to
00:52try
00:53to burn through it if you want to learn more about avl trees see my previous videos
00:58okay so supposing now that you have a tree that looks like this let's confirm that this is a valid
01:03avl tree uh this seems to be a tree it's a connected graph it's uh got no cycles it's a
01:09rooted tree
01:10it's a binary tree there are no there are no more than two children per every single node
01:15and the data is in order so 14 22 36 41 48 55 65 so this is a valid binary
01:22search
01:22tree now to determine if it's a valid avl tree we just have to compute balance factors so
01:27in my previous videos we talked about doing this so i'm just going to try to burn through this quickly
01:32i want to put zeros on all the leaves because that's pretty easy this 48 gets a one
01:37uh the 65 actually gets a two so at this point already we know there's something wrong with our
01:42tree we need to rotate it this is not a valid avl tree because we see a balance factor that
01:47is worse
01:48than you know plus or minus one so uh the 41 is going to have a balance factor of let's
01:54see just a
01:55one and so really the only thing that we need to rotate is going to be this 65 note this
02:00is the node
02:00that's out of whack sometimes you see you know the bad balance factor in other areas of the tree maybe
02:05like a little bit higher and also a little bit lower you want to rotate as low as possible first
02:09because sometimes when you rotate low it fixes stuff that's higher this is this is actually only true if
02:17the thing that you're rotating is a direct descendant not necessarily a direct child but
02:21just a descendant of the thing that you see that is higher if you have two different nodes that are
02:26unrelated uh in terms of uh you know they're not uh direct descendants or ancestors of one another
02:32they're sort of like siblings or cousins uh then it doesn't really matter so much which one you rotate
02:37first because they're not really going to affect each other but uh in this case if we rotate uh you
02:43know
02:43starting with this 65 there's a chance that the 41 will get fixed up a little bit
02:48i haven't tried this yet so i don't know for sure but i have a feeling it might let's see
02:52what happens
02:54so we know that the first node that is out of balance we'll call the z node so i'm just
02:58going
02:58to put a z here let me just duplicate this and we'll say z uh hang on a second i
03:04got some dashes
03:05in my pen there we go i will make this the z node and then we have to find uh
03:11x and y we'll do that
03:12backwards we'll find the y first and then the x we find them by going down one level at a
03:18time so the
03:18y node will be a child of z and we'll have to find the child that has the taller subtree
03:24in this case
03:25there's no choice because there's no subtree on the right side of 65 so we can only go left but
03:30just keep in mind if there was a subtree let's say like that then we would still go to the
03:35left and
03:35select that 48 as the y node let me just write down y node here because it would have a
03:39taller subtree
03:40notice the left subtree in this little example has a height of 2 and the right subtree has a height
03:44of 1
03:44so let's just get rid of that little extra thing same thing for the x we want to find a
03:49child of y
03:50and we'll always take the taller subtree so you know if there was a subtree over here uh and maybe
03:56like another like node down there then we would still go to the right to get the 55 because it
04:00would have the taller subtree in this case there's only one choice so the x node is just going to
04:05be
04:06this 55 and that's it so let me just put x right here so now that we know which nodes
04:11are x and y and z
04:14i'm just going to write that down real fast x equals 55 i'm going to probably change the
04:21color here y is equal to 48 uh z is equal to 65
04:28um
04:31and then we want to make an in-order representation of uh xyz and just call it abc so i'm
04:37going to say a is
04:37equal to something b is equal to something and so is c
04:40so a is going to be the least value the value that belongs on the left because again
04:44these are supposed to have ordered data like binary search trees so i'm going to put 48 here
04:50and 55 there and then 65 here now abc is the in-order representation of xyz
04:57now that we've done that i'm going to draw our target pattern here so let's see i'm going to do
05:02i'm going to do a trinode subtree uh just kind of very quickly going to draw it over here
05:07and then uh connect with some blue lines because that's just like such a cool connection hang on a
05:16second i put that a little bit too far down okay so we'll do that and then i'm going to
05:21do another
05:22connected in line okay i had to make a little edit there um so i'm going to just continue making
05:29this
05:29blue line so i'm going to do this
05:34and uh i have to update the the values now so this 14 on the left that should be the
05:38a node
05:39so we're going to see 48 and then the new parent is going to be 55 and then the right
05:45child is going
05:46to be 65. always after you fill in these values ask yourself have i actually drawn a valid binary search
05:51tree if you haven't meaning if the data is out of order in some way then you haven't drawn a
05:57valid
05:57binary search tree and you probably need to try again so we've got 48 and 55 and 60. the next
06:02thing we should take into account is are there any any children that are unaccounted for in terms of
06:08the uh the input nodes to the pattern that we've just drawn down here the output pattern so let me
06:13just kind of remind you that there could have been you know potentially some some nodes right like we
06:18could have had a right child of 65 we could have had a left child of 48 and we could
06:22have had two
06:23children of 55 so there's always a potential for four nodes that are unaccounted for uh we'll just
06:28check them one by one real fast here so we'll say um look at the 48 first the 48 had
06:35a right child of
06:3655 but that's already taken care of in the output pattern so we don't have to worry about that
06:40now we look at the 55 we could go xyz if we wanted to but i like looking at the
06:44output pattern
06:45uh 55 had no children so that's fine and then we look at the 65 the 65 had a left
06:51child of 48 but
06:52that's already in the output pattern so at this point all uh children are accounted for we don't
06:57really need to do that much if there were any children that were unaccounted for they would
07:01need to be attached under the 48 and 65 somewhere and each child would only go in one place without
07:08there's only one place that the child could go without invalidating the binary search tree
07:13um but that'll be i'm going to make a harder example in the next video
07:17so now that we've done this we're ready to reattach all the nodes are accounted for that
07:23we're about to remove from the diagram we're not actually going to be deleting nodes or creating
07:28nodes or anything like that in the code we're really just disconnecting pointers and reattaching
07:33them so i'm going to just erase this from the diagram but keeping in mind that the nodes are not
07:38really being recreated and i'll just put the 55 over here uh where the old trinode subtree was
07:45and then i'm going to recompute the balance factors for all of the nodes involved
07:50so uh you know i just moved uh the 65 that was one in the output pattern so i'm going
07:56to put a zero
07:5748 also zero because they're leaves the 55 it's a zero it's perfectly balanced that's pretty sweet
08:03and now that we're done with the nodes that we touched we have to work our way up to the
08:07root node
08:08we don't have to worry about anything over here on the left because those nodes couldn't possibly be
08:13affected uh by uh by by the rotation we just did because only nodes that are above the rotation
08:19will be affected so uh the last one we you know looked at was this 55 so i'm just basically
08:24going
08:24to say all right 55 let's look up one more parent it's going to be the root node the 41
08:29so what's the
08:30new balance factor of the 41 node it's actually going to be better it's going to be a zero
08:37so with that in mind we've actually created a perfectly balanced binary search tree this is
08:42definitely a log time tree super super fast and super super cool um and what type of rotation did
08:48we actually end up performing let's see let me go back a slide here so we had xyz uh if
08:54you don't
08:54have the rotations memorized keep in mind my previous videos explain all of that with some fun ways to uh
09:02help you remember hopefully maybe maybe some un-fun ways um so i'll just kind of like reiterate real fast
09:09here uh there are two nodes that need to be moved into position notice how 55 is supposed to be
09:14the new
09:14parent node which means the 65 needs to be rotated under the 55 and so does the 48 so the
09:2148 and the
09:2165 both are going to be rotated into position that means two nodes are rotated which means it's a double
09:28rotation not a single rotation uh which node was rotated first i always rotate the z node first you
09:34know the node on very on the very top and so i'll just use the rotation direction of that z
09:39node so
09:39that's a counter sorry that's a regular clockwise rotation and that's a right rotation so this is a
09:45double right rotation another thing you can do to remember is if you go from y to z you're going
09:50up
09:51into the right so that's a right rotation you could also imagine that uh there is some negative space
09:57kind of sitting here on the right side a little right pocket so that's a right rotation and
10:05i'm sure there were some other ways that i added in the other video but i can no longer remember
10:09them so i'll just move on we'll say we did a double right rotation in order to get this uh
10:14this
10:14perfectly balanced binary search tree so i'm going to cut the video here in the next video we're going
10:20to i think probably rotate a linear tree you can kind of see i've already started to draw one here
10:25in
10:26the next video we're going to look at this like giant gnarly linear tree and we're going to pretend that
10:31we
10:32have the avl rotating disabled for a while while we built this tree and then all at once we're going
10:36to turn it on and do like a whole bunch of rotations and see what the tree is going to
10:40end up looking
10:40like it's going to be pretty ugly and fun anyway thank you so much for watching this video i hope
10:47you
10:47learned a little bit of stuff and you had a little bit of fun i'll see you in a moment
10:53hopefully hey
10:56everybody thanks for watching this video again from the bottom of my heart i really appreciate it
11:00i do hope you did learn something and have some fun if you could do me a please a small
11:06little favor
11:06could you please subscribe and follow this channel or these videos or whatever it is you do on the
11:12current social media website that you're looking at right now it would really mean the world to me
11:17and it'll help make more videos and grow this community so we'll be able to do more videos longer
11:22videos better videos or just i'll be able to keep making videos in general so please do do me a
11:28kindness
11:29and uh and subscribe you know sometimes i'm sleeping in the middle of the night and i just
11:33wake up because i know somebody subscribed or followed it just wakes me up and i get filled
11:37with joy that's exactly what happens every single time so you could do it as a nice favor to me
11:42or you
11:42could you could troll me if you want to just wake me up in the middle of the night just
11:44subscribe
11:45and then i'll i'll just wake up i promise that's what will happen
11:49also uh if you look at the middle of the screen right now you should see a qr code which
11:53you can
11:54scan in order to go to the website which i think is also named somewhere at the bottom of this
11:58video
11:59and it'll take you to my main website where you can just kind of like see all the videos i
12:03published
12:03and the services and tutorials and things that i offer and all that good stuff and uh
12:10if you have a suggestion for uh uh clarifications or errata or just future videos that you want to see
12:17please leave a comment or if you just want to say hey what's up what's going on you know just
12:21send me
12:22a comment whatever i also wake up for those in the middle of the night i get i wake up
12:26in a cold sweat
12:26i'm like it would really it would really mean the world to me i would really appreciate it so again
12:32thank you so much for watching this video and um enjoy the cool music as as i fade into the
12:39darkness
12:40this which is coming for us all
13:12so
13:23so
13:25so
13:25so
15:47Hello there.
15:49Hi there.
15:53Let's maintain a self-balancing ABL tree, which is recursive.
15:58Hello there.
16:00Let's...
Comments