As someone mentioned below, the last example is incorrect. But when we think about why, or how it should be done, we shouldn't start at the top and go down. We should think recursively, based on how node insertion works. Node insertion starts at the top of the tree and recursively descends until it finds the place to add the new node. Then, after adding the node, we unwind the recursion, returning back up the tree, updating the height as we go, checking each time whether the tree is unbalanced. In the example the tree is not unbalanced until we get back up to the root node, 4. That's why the (double) rotation should be centered on 4 (right on 10 and then left on 4, as mentioned below).
5:36 - What he means is he has a height of 3 children on the right of the four. This is why AVL trees call them 'heights' and not 'children', because it can be very confusing otherwise. Here, the four seems to have 4 children, but what the teacher means is that the height of its children is 3.
@RobEdwardsSDSU , there are several mistakes 1. Minor, there are number 8 written as 6. 2. Major - you are rotating wrong numbers near 6:00. You should rotate right and get 8 parent of 10 and 10 parent of 9 and 12 ( 9/10\12 ) and then rotate left and make 8 root.
Agree, around 6:00, the violation node is 4, we should do a right left rotate on the subtree of 4 - 10 - 8, www.cs.usfca.edu/~galles/visualization/AVLtree.html this helps me
how come first time 9 is considered to be the violating node and not 8. And later after left right, 10 is considered the violating node and not 12. How do we select the violating node ?
This last example is incorrect. Even though inserting 9 caused the violation, you only go down the tree 2 nodes from where the violation of rules occurs towards the violating node and choose that node's parent and grandparent for the rotations. In this case, the violation of rules occurs at node 4, so we go down the tree two nodes towards 9 and end up at 8. Then we perform a right rotation on 10 (the parent of 8) and a left rotation on 4 (the grandparent). This balances the tree in one set of rotations.
Hi so those super-scripts next to the node represent the height of the sub tree right? When you say children on the left or right you mean “generations” right ?
@@ginicholas4322 I like how we are all watching CS videos and you're the only person who used logic to determine the video is mirrored. -_- our future is doomed.
The second example is wrong unless there are multiple ways of balancing an AVL tree--it's suppose to be a right-left rotation (not a left right rotation)
I’ve been trying to figure that out, too. But I have a theory: Most people are right-handed. But he appears to be left-handed. So maybe he records them and flips the video afterwords. Or maybe he’s just left-handed and this is a live recording of a lecture. I couldn’t say for sure.
Hi, I've a problem with creating a Balanced AVL tree . In the following there is a sequence to create. The issue is I can not create a Balanced tree with a difference of 1. If you try to rotate the nodes in my understanding I am entering to an endless loop. I'l appreciate very much if someone can explain me on how to create from this sequence a balance tree.
Looks like he is writing on the glass and the video is flipped so that it doesn't appear backwards. Note the flipped image of the Nike logo on his shirt!
That is not called two children on the left and one on the right, each node has a maximum of 2 children! You should say the height of the left subtree is two and the height of the right subtree is one.
this guy is insane the way it was explained it made so much sense
As someone mentioned below, the last example is incorrect. But when we think about why, or how it should be done, we shouldn't start at the top and go down. We should think recursively, based on how node insertion works. Node insertion starts at the top of the tree and recursively descends until it finds the place to add the new node. Then, after adding the node, we unwind the recursion, returning back up the tree, updating the height as we go, checking each time whether the tree is unbalanced. In the example the tree is not unbalanced until we get back up to the root node, 4. That's why the (double) rotation should be centered on 4 (right on 10 and then left on 4, as mentioned below).
I wish I had Teatchers like him in my university.
Thanks a bunch. The best explanation ever.
Breaks down the problem properly. Love it
5:36 - What he means is he has a height of 3 children on the right of the four. This is why AVL trees call them 'heights' and not 'children', because it can be very confusing otherwise. Here, the four seems to have 4 children, but what the teacher means is that the height of its children is 3.
thank you, that had me very confused
You are doing awesome lectures! Thanks so much!
"so my tree is happy"
This is the best explaination of avl trees, I have ever heard. Thank you for being so clear and concise.
Thank you so much! Your videos on avl trees are great!
Great videos. Balancing makes a lot more sense, now.
Great explanation, thank you Rob
Excellent explanation!
Thanks. Great explantaion!
Thanks very much Dr. Rob, extremely well articulated information! Love the analogies. Home-wrecking single parents lol
@RobEdwardsSDSU
, there are several mistakes
1. Minor, there are number 8 written as 6.
2. Major - you are rotating wrong numbers near 6:00. You should rotate right and get 8 parent of 10 and 10 parent of 9 and 12 ( 9/10\12 ) and then rotate left and make 8 root.
Agree, around 6:00, the violation node is 4, we should do a right left rotate on the subtree of 4 - 10 - 8, www.cs.usfca.edu/~galles/visualization/AVLtree.html this helps me
great job explaining this! thank you
Well explained!!
Excellent video, helped me so much. Thanks!
This was exactly the instruction that I needed to understand height better, and to understand rotations. Thank you.
Would it be wrong if we balance the tree even if the height is less than or equal to 1. It might not be useful but would it be wrong?
how come first time 9 is considered to be the violating node and not 8.
And later after left right, 10 is considered the violating node and not 12.
How do we select the violating node ?
This last example is incorrect. Even though inserting 9 caused the violation, you only go down the tree 2 nodes from where the violation of rules occurs towards the violating node and choose that node's parent and grandparent for the rotations. In this case, the violation of rules occurs at node 4, so we go down the tree two nodes towards 9 and end up at 8. Then we perform a right rotation on 10 (the parent of 8) and a left rotation on 4 (the grandparent). This balances the tree in one set of rotations.
diese ubung ist nicht richtig
hello sir, does Red Black Trees and AVL Trees have different rotation method?
Hi so those super-scripts next to the node represent the height of the sub tree right? When you say children on the left or right you mean “generations” right ?
Best expalination I learnt very easily
Nice explanation, thank you!
very useful video now i understood thanks
I love your EKIN t-shirt
perfect Explanation
Awesome explanation
Ok the video might be flipped....but what about him looking around like there are students in front of him?
awesome explaination. ..but how is he writing those letters on glass.
My mind is fucked rn. Is he writing backwards?? Is the footage mirrored? I must know
@@natecolbert959 Yeah, he's writing with the left hand and since most write with the right hand, I'd guess it's mirrored :D
He's wearing a nike shirt, so yeah it's mirrored
Sujay S Shenoy check his shirt, the nike logo is reversed.
@@ginicholas4322 I like how we are all watching CS videos and you're the only person who used logic to determine the video is mirrored. -_- our future is doomed.
The second example is wrong unless there are multiple ways of balancing an AVL tree--it's suppose to be a right-left rotation (not a left right rotation)
Are you writing in mirror image? If so, that is impressive.
I’ve been trying to figure that out, too. But I have a theory: Most people are right-handed. But he appears to be left-handed. So maybe he records them and flips the video afterwords. Or maybe he’s just left-handed and this is a live recording of a lecture. I couldn’t say for sure.
exercise 3 can be resolved with right-rotation(10) and left-rotation(4) ?
Not sure why he is talking about the number of children. What is important is the height of the nodes, not the number of children.
this, confused me so much
the height of the node is the number of children of the node
thats the same thing
@@jozicar Me too. It seemed like he had 3 children on the left of the 10 and he was saying 2 children. Thanks @Cosmin for explaining this.
@@chanpreetsingh5054 it is not, at 5:42 he says that the 4 has 3 children, but it has 4. What he means is the height/depth of the node.
Does anyone have an idea where and how he is writing? It's definitely not glass! Is he using a software?!
Hi,
I've a problem with creating a Balanced AVL tree . In the following there is a sequence to create. The issue is I can not create a Balanced tree with a difference of 1. If you try to rotate the nodes in my understanding I am entering to an endless loop. I'l appreciate very much if someone can explain me on how to create from this sequence a balance tree.
Sorry here is the sequence.
Thanks
vector v = { 43, 18, 22, 21, 9, 6, 8, 27, 4, 2, 13, 7, 10, 16, 3, 15, 1, 11 };
do you mirrow writing? how is it possible that I can write the letters on the glass XD
2:40 you write 6 instead of 8
Should be an 8
at 5:53 ... why isn't the root the violation? can't you just do one rotation of the root to its left child from the start to fix it?
it's cool. How to write on a blackboard like through a glass?
Looks like he is writing on the glass and the video is flipped so that it doesn't appear backwards. Note the flipped image of the Nike logo on his shirt!
His left hand is actually his right hand.
@@DevinSamarin mate you smart, i didn't notice that. Anyways I wish you a good day sir.
Does he have an audience?
who cares about the trees
that dude is writing like backwards, teach me that instead
lol, I was thinking the same, but he is probably writing normally, then the video is flipped :)
I think maybe there is a mirror somewhere lolz
Just look at the nike symbol on his shirt. It looks like he is writing with his left, but it's actually his right.
The picture is simply flipped
No he is writting so he can see it. He then mirros the image in a video editing package.
give ariel a job at google
That is not called two children on the left and one on the right, each node has a maximum of 2 children! You should say the height of the left subtree is two and the height of the right subtree is one.
Nice visuals, but you lost me when you did the left right rotation, that's why in the end the vid, as nice it may looks, doesn't really help me...
first example, from where did you get 6?
That's 8, either it looks like 6 or he wrote it by mistake.
Yes, he made a mistake.
The nike logo is reversed, hence this is mirrored.
@5:45 4 children at the right of 4? right?
Why does his Nike shirt backward
At first, I thought that he used Bunshin no Jutsu.
Wait! He doesn't write backwards, it's Nike logo is reversed. The video is mirrored!!
A legend has fallen...
wait, are you writing backwards?
What Hank would've looked like if he hadn't become a police officer and decided to be a college professor.
at first i was like whaaaat this guy write backward then i got it
r you writing backwards?
there is a mistake in 3:09 the number is 8 not 6
Look closer its 8
@@zbynekjuros5139 the left child in the left rotation must be 8, not 6. But it doesn't change anything.
@@thrakiamaria so one more time? Its 8. Zoom in.
Are you sure its definitely a 8? it looks like a 6
@@adityamehta2819 it looks like 6, I zoomed in, except if you have 4k screen.
thanos: perfectly balanced :D
This dude looks like how the villain from Riddick moves
he should have said 'max subtree height' instead of 'child'
horrible...not explained why the 10 is the one violatiing, how you decide the rotation? how you decide ll rotation vs l rotation? horrible.
writing backwards??? yo...
you write 8 like a 6