AVL Tree 7 complete example of adding data to an AVL tree.

all right today we're going to look at AVL trees and AVL trees are a type of tree where you maintain balance by ensuring the difference in height of the left subtree and the right subtree is never more than one we're going to go through an example which is one of the questions in the reader and is likely to be one of the questions that you might be asked on an exam so you probably should practice this kind of thing okay and what I'm going to do is we're just going to add a bunch of numbers to the AVL tree we're going to draw our sub trees that's important if I ask you to add numbers to an AVL tree make sure that you draw the sub trees and you explain what's going on we're going to draw our sub trees and then and we're going to also say whether we have to do a left rotation a right rotation a left right or right left rotation so we're going to start with 43 that's our first number to add we've got root there's nothing to do now we're going to add 18 is 18 bigger than 43 or smaller than 43 hopefully it's smaller than 43 so it goes on the left then we add 22 the 22 is smaller than 43 so it goes on the left but it's larger than 18 and it goes on the right so now we have to calculate the difference in Heights and so we always start with a node that we've just added on the right side of the 22 we have a height of 0 and on the left side of the 22 we have a height of 0 on the right side of the 18 we have a height of 1 and on the left side of the 18 we have a height of 0 1 and 0 that's okay the trees once there for the 43 on the right side we have a height of 0 and on the left side we have a height of 2 our left side is greater than more than one above a right side so we have to rebalance our tree what kind of rotation do we need to do to rebalance this tree the imbalance is in the left child's right subtree so we have to do a left-right rotation so make sure that you specify that we're doing the left right rotation when we do that we bring the 22 up to be the root the 18 on the left child of the 22 the 43 on the right child of the 22 now our tree is balanced next we add a 9 nine is less than twenty two is less than eighteen and it goes to be a left child is this tree balanced a nine has zero and zero are eighteen has one child on the left and zero children on the right that's okay our 22 has two children on the left and one on the right so that's also okay so this tree is still balanced for an AVL tree now we add a 21 21 is less than 22 so it goes on the lap on the left and 21 is more than 18 so it goes on the right child of the 18 is this tree balanced our 18 has one node on either side or 22 the longest path is still two and one on the right so it's still balanced now we add a six here's our tree we add a six is this tree still balanced a nine has one and zero are 18 has two and one so that's balanced and our 22 the longest path from from 22 from the root to any leaf is height of 3 so height of 3 here and a height of 1 for the 43 so now our tree is unbalanced the imbalance occurs in the left child's left subtree and so we do a right rotation the right rotation is going to bring the 22 down around the 18 there we go right rotation make sure you note what kind of rotation we have to do so just like we've seen before we're going to end up with our 22 being the right child of the 18 the 21 becomes 22s new left child and 43 is the right child and the six now is the left child of the 9 where it should be so is this tree balanced we've got from on the 9 we've got 1 & 0 that's okay on the 18 we've got 2 and we can either go 1 2 or 1 2 & 2 and so we've got a balanced tree next we add the 8 here's our tree the 8 is less than 18 it's less than 9 but it's more than 6 and so the 8 comes in here is the tree balanced the 6 has zero on one that's ok the 9 has the longest path to a leaf from the 9 has two edges on the left and zero edges on the right and so this tree is imbalanced at the 9 how do we fix it the imbalance is in the left child's right subtree so we need to do a left right rotate our left right rotate is going to bring our six and make it the left child of the 8 and it's going to bring our 8 and make it the right child sorry online and make it the right child of the 8 so we're going to end up after doing the left right rotate we're going to end up with a balance tree again make sure you note what kind of rotation you have to do make sure that your tree is balanced here are 18 our longest path is two on the left and two on the right now next we add a 20 and our 20 is bigger than 18 it's less than 22 and it's less than 21 and so we're going to end up with our tree looking like this is this balanced again we start counting from the bottom the 21 has 1 and 0 the 22 has 2 and 1 that's okay and the 18 the longest path is 3 edges on the right and 2 edges on the left and so that's balanced as well so this is still a balanced tree next we add 6363 is bigger than 18 it's bigger than 22 is bigger than 43 and so we end up with our tree looking like this we're adding 63 is this tree balanced we've added our 63 now 43 has one and zero that's okay our 22 has two and two two left children to write children and our 18 has three and there's two different paths we can have three edges down here or we can have three edges one two three here two different paths but still the same number of edges so our height here is three and our height on the left is 2 again there's two different ways that we can get it but it's also 2 and so this tree remains balanced next we add a 50 and I'm going to erase this so that I can add my 50 my tree is going to grow to be and beyond the height of my screen so here's our tree before we add the 50 we're adding 50 50 is bigger than 18 it's bigger than 22 it's bigger than 40 3 is less than 63 and so it comes down here what's our height now a height for the 63 is 1 and 0 our height for the 43 is 2 and 0 and so we have an imbalance in the 43 our imbalance is in the right child's left subtree so we have to do a right left rotate when we do that we're going to bring the 43 down to be the left child of the 50 the 63 will be the right child of the 50 so our tree will end up looking like this a 50 is the median value 43 is the left child and 63 is the right child let me rewrite that let's put it up here so that we can keep adding more numbers we have our 18 is our root 8 6 & 9 22 21 and 20 then we have our 50 which is our median value of 43 and our 63 is that tree balanced for an AVL tree is that balance for an AVL tree our height here is one and one our height that the 22 is two on the right and two on the left that's okay our height here is one two three on the right and two on the left and so that's okay we're still balanced for an AVL tree now we're going to add sixty two sixty two is bigger than eighteen it's bigger than twenty two is bigger than fifty it's smaller than sixty three so our tree becomes like this is this balanced for an AVL tree a height at the 63 is one and zero that's okay our height at the 50 is two on the right and one on the left so that's okay our height of the 22 is one two three on the right and two on the left so that's okay and our height at the 18 is one two three four on the right and two on the left and so that's not okay so we're imbalanced our imbalance is in our right child's right subtree and so we're going to do a left rotation and we're going to do a left rotation of the 18 around the 22 so just like we've seen before the 18 will come around the the 22 will be the new route 22s left child will be a teens right child and we'll go from there okay so our tree ends up becoming 22 is the root 18 is 22s new left child and the 21 and the 20 r18s right child the 8 the 6 and the 9 stay the same as they were and are 50 60 362 and 43 also remain the same is that a balance tree we've got 1 and 0 here we've got 2 & 1 here we've got 1 2 3 on this side on the left tree we've got 1 and 1 we've got 2 & 2 and we've got one two three and three and so now we remain balanced finally we're going to add a fifty-one to the tree here's our tree we're going to add 5151 is bigger than 2251 is bigger than 50/50 one is smaller than fifty three and fifty one is smaller than sixty two so it becomes our new 62 s left is this a balance tree we've got a height of one and zero we've got a height of two and zero here and so we have an imbalance of the sixty-three the imbalance is in the left trees left sub child so we're going to do a right rotation notice that we always mark our rotations here we did a left rotation so that we know what's going on and in this case we have 18 eight six and nine are 21 and 20 remain the same 50 43 and here we end up with 62 51 and 63 after this rotation are we a balanced tree let's test we've got a height of one and one that's okay we've got a height of two and one that's okay we've got a height of three up here on the left tree we've got a height of one and one a height of two and two and a height of one two three and three here and so we end up with a balanced AVL tree at no point is any difference in height greater than one for any node and so we've balanced our AVL tree when you do this in an exam when you do this in an interview make sure that at the end your tree looks balanced make sure that you note whether you do a left rotation a right rotation a left right or right left and make sure you draw out all of the intermediate trees it's really easy to get lost when you're building all of these trees and there's plenty of paper available so just make sure that as you're going through you write out all of the intermediate trees

Channel: RobEdwards

Views: 73,783

Rating: 4.9165506 out of 5

Keywords: computer science, data structures, cs310

Id: 7m94k2Qhg68

Length: 20min 47sec (1247 seconds)

Published: Thu Nov 10 2016