AVL 1 Introduction

so I've talked about trees being imbalanced but I haven't really described what an imbalance actually means and so one of the trees that we're going to look at are called AVL trees the rule for an AVL tree is that the difference in height between left and right must always be less than or equal to one okay and if the difference in height is more than one then there's a violation of the tree so let me demonstrate an AVL tree and show you what I mean so if we start with a four yeah the difference in height between left and right is zero because there's no children now if I add a two I've got one child on the left and zero on the right so that's okay I'm still less than or equal to one if I add an eight I got one child on either side that's okay if I add a ten now I've got one child on the right of the eight and zero children on the left of the eight I've got two children on the right of the four and one child on the left of the four so that's okay I'm still in balance and then if I add a twelve now I've got one child on the right of the ten and zero on the left I've got two children on the right of the eight and zero on the left so my difference in Heights at the eight is bigger than one so I've got a violation of my tree and the node that caused the problems is the 12 so to fix the violation I rotate the grandparent so 12s grandparent is the 8th so I rotate the grandparent and I do a left rotation if I do a left rotation of the 8 I end up with a tree that looks like that I've rotated the 8 the left around the left of the 10 and I've used the 10 instead of the 8 now at the 10 I've got one child on either side so that's okay at the four I've got two children on the right and one on the left and so that's okay all right so I've restored balance to my tree let's take a look at another example let's say I start this time with the 10 and I add an 8 everything's good I added 12 I'm still good and add a 4 I've got two children on the left of the 10 and one child on the right of the 10 now if I add a 2 now I've got one child on the left of the 4 0 on the right of the four I've got two children on the left of the 8 and 0 on the right of the 8 and so I've got a violation of my AVL rules my violation is my node that caused the problem the two it's in the left child's left subtree so I have to do a right rotation of the 8 and so I'm going to end up with the 10 I'm going to put the 4 in place of the 8 I'm going to have the 8 and the 2 is the children of my 4 and my 12 so now I've got one child on either side I've got two children on the left of the ten and I've got one child on the right of the ten so my trees happy let's take a look at one more example of an AVL tree so I'm going to start with a four and I'm going to add a ten there are things okay I'm going to add a 2 everything's still good I'm going to add a 12 I've got two children on the right of my four I've got one child on the left of my four I'm okay I'm going to add an 8 and so now I've got either two children going for ten eight or two children going for ten twelve one child on the left so I'm still good and now if I add a nine now my longest path is going to be through four ten eight nine right so my nine I've got one child on the right of my eight and zero on the left of my 8 I've got two children on the left of my 10 and one child on the right of my 10 so that's okay I've got one two three children on the right of my four and one child on the left of my four okay so we've got a violation the node that caused the violation was the nine and if I go to the 9 s grandparent and ask what's going on the violation is in the left child's right subtree so the way to fix that is to do a left-right rotation of the ten so to do a left right rotation of the ten the first step is a left rotation of the parent which is the eight okay so I end up with my for my to my ten stays where it is I do a left rotation of the eight so the eight goes around the nine so nine comes in the middle and then eight goes there and then when I do that left rotation I use them nine instead of the eight and now from this step I have to do a right rotation of the ten so let me redraw that tree over here just so I can annotate it as we do the rotation and I'm going to do a right rotation of the ten so what I'm going to do is I'm going to rotate the ten around the nine and the nine is going to go in place of the ten okay and remember that tenth the twelve is tens right child when we end up after doing the rotation the twelve is going to stay where it is relative to the ten right that doesn't move the 10 comes down here and the twelve stays as the tens right child so now we're going to end up with a 4 the 9 the 8 the 10 and the 12 and the 2 here okay that's the outcome of our right rotation of the 10 when we look at this tree we've got one child on the right of the 10 zero on the left we've got two children on the right of the 9 and one on the left and we've got three children on the right of the 4 and one on the left and so we've got a violation of our AVL rules now the node that caused the violation is our 10 here's our 10 that's the one that causes the problem the form was quite happy it was just hanging out had its children it was totally fine the 10 comes along does a rotation messes everything up so the node that causes the violation is the 10 and so the node that has to pay for it is not the parent but the grandparent of the 10 the violation is in the right child's right subtree so we do a left rotation so we're going to do a left rotation of the 4 so remember our rules for a left rotation we set a temporary pointer to our node that we're rotating in this case the 4 we set a temporary pointer to the nodes right child and then we set nodes right to temps left ok so let me just sketch that out we start with this situation we just set a temporary pointer to nodes right and then we set nodes right to temps left here's our temporary pointer is our 9 or 10 and a 12 and then we set temps left to the parent that we're rotating Tim's left to here and we use our temporary node in place of our parent so after our rotation we end up ok like this in this case our 4 has one child on either side our nine has two on the left our 10 has one and zero and our 9 has two on the right and so we've brought balance and harmony back to our tree and everybody's happy so sometimes when you do rotations to fix a problem like in this case that creates a new problem further up the tree and as well see when we're looking at the trees whenever we do a rotation to fix the balance we have to go all the way back to the root then make sure that the rotation that we did doesn't introduce a new problem further up the tree that we then need to go and fix okay

Channel: RobEdwards

Views: 75,783

Rating: 4.8817892 out of 5

Keywords: data structures, computer science, cs310

Id: -9sHvAnLN_w

Length: 11min 14sec (674 seconds)

Published: Thu Nov 10 2016