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.
@@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.
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 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 ?
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)
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!
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.
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.
Best explanation i've come across so far. Brilliant and simple. Wonderful vid! Thank you so much for this!
This is the best explaination of avl trees, I have ever heard. Thank you for being so clear and concise.
I wish I had Teatchers like him in my university.
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.
thank you, that had me very confused
this guy is insane the way it was explained it made so much sense
"so my tree is happy"
@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
This was exactly the instruction that I needed to understand height better, and to understand rotations. Thank you.
Breaks down the problem properly. Love it
Thanks a bunch. The best explanation ever.
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
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
@@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.
You are doing awesome lectures! Thanks so much!
Thanks very much Dr. Rob, extremely well articulated information! Love the analogies. Home-wrecking single parents lol
Thank you so much! Your videos on avl trees are great!
Excellent explanation!
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.
Great videos. Balancing makes a lot more sense, now.
Excellent video, helped me so much. Thanks!
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 ?
Great explanation, thank you Rob
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?
Ok the video might be flipped....but what about him looking around like there are students in front of him?
I love your EKIN t-shirt
great job explaining this! thank you
Nice explanation, thank you!
hello sir, does Red Black Trees and AVL Trees have different rotation method?
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)
Awesome explanation
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.
exercise 3 can be resolved with right-rotation(10) and left-rotation(4) ?
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
very useful video now i understood thanks
Thanks. Great explantaion!
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.
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?
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 };
Well explained!!
2:40 you write 6 instead of 8
Should be an 8
Does anyone have an idea where and how he is writing? It's definitely not glass! Is he using a software?!
perfect Explanation
do you mirrow writing? how is it possible that I can write the letters on the glass XD
Does he have an audience?
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?
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.
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.
What Hank would've looked like if he hadn't become a police officer and decided to be a college professor.
r you writing backwards?
Why does his Nike shirt backward
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...
At first, I thought that he used Bunshin no Jutsu.
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.
@5:45 4 children at the right of 4? right?
at first i was like whaaaat this guy write backward then i got it
he should have said 'max subtree height' instead of 'child'
This dude looks like how the villain from Riddick moves
thanos: perfectly balanced :D
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