Trees 10 Rotations

all right so where we left off is we were looking at imbalance in trees okay and we were looking at a situation for example if we had a tree and we started with the number 4 and then we added a 6 that's ok and then we added an 8 so 6 is bigger than 4 so it goes to the right-hand side 8 is bigger than 4 so it goes the right-hand side 8 is bigger than 6 so it goes the right-hand side okay and so now we have an imbalance in our tree and we need to do something to correct that imbalance and what we need to do is we need to rotate the 4 around the 6 okay and so that's called a left rotation and I want to point out that the tree was quite happy when it was just the for the tree was quite happy when it was the 6 but when we added the 8 the 8 is the node that caused the imbalance so when we added the 8 we got an imbalance and we do the rotation on the grandparent okay it's the grandparent of the node that we have that causes the imbalance that we have to fix so we do a left rotation of the 4 around the 6 and we end up with a balanced tree 4 6 and 8 that's a left rotation in contrast in contrast if we have the situation where we have the eight the six and the and then the four again the 8 and the six are quite happy the node that caused the imbalance is the four and the node that has to pay is the grandparent okay and in this case we do a right rotation of the eight and we end up again with our balance to tree looking like this now in both these cases in both these cases what we're looking at is where the median value is so here's the median value and here's the median value and after we've done the rotation we want to end up with the median in the middle okay the median in the middle so what happens if instead of having this situation we have for example we have it start with a four and then we add an eight eight is bigger than four so it becomes fours right child and then after adding the eight we add the six six is bigger than four so it has to be on fours right-hand side and six is less than 8 so it has to be down here okay so now we have an imbalance and I'll talk about how we measure imbalance in just a minute but now we have an imbalance so how can we correct this imbalance can we do a left rotation or can we do a right rotation so no single rotation will fix this if we do left rotation it won't fix it if we do a right rotation it won't fix it what we actually need is a combination of two rotations the first rotation is to take the median value the six and put it in the middle and so what we're going to do is first of all we're going to do a right rotation and what we want to end up with is the six in the middle between the four and the eight so we want to end up with this situation so we're going to do a right rotation of the eight around the six okay once we're in this situation this is one we've already seen we know how to fix that we can do a left rotation and so here we do a left rotation of the four and so in this case the note that caused the imbalance is the six and this time both the grandparent and the parent have to pay for that imbalance so first of all we do a right rotation of the eight around the six that's the parent so our first rotation our right rotation is of the parent and our second rotation the left rotation is the grandparent okay similarly if we have an 8 a 4 and a 6 we're in the same situation no single rotation can fix this the first thing we need to do is we need to move the median value which is the 6 and so in this case we're going to do a left rotation of the four around the 6 so again it's a left rotation of the parent which is the 4 and that ends up with the 8 the 6 and the 4 we've seen how to fix that that's a right rotation and so we do a right rotation of the grandparent and that's the eight and then we end up with our balanced version of our tree okay so notice that when we look at the grandparent the imbalance here is in the right child's right subtree it's a right child right subtree and we do a left rotation when we look at the grandparent here the imbalance is in the left child's left subtree and we do a right rotation when we look at the the the grandparent here the imbalance is in the right child's left subtree the right child's left subtree and we do a right left rotation and here the imbalance is in the left child's right subtree then we do a left-right rotation okay so identifying where the imbalance occurs identifying which node caused the problem and then looking at its grandparent and saying where does the imbalance occur tells you how to fix that particular imbalance

Channel: RobEdwards

Views: 30,917

Rating: 4.9835167 out of 5

Keywords: data structures, computer science, cs310

Id: NczBLeco6XA

Length: 8min 13sec (493 seconds)

Published: Mon Nov 14 2016