ROTATIONS IN AVL TREES - DATA STRUCTURES

[Music] hello folks welcome back to our Channel so in the previous session we have seen the AVL trees so in the interaction to email trees and today's session we will see the rotations involved in this inventories right so there are two operations that can be performed on avian tricks so before going to those operations we will see the property of immolated we will just recall the property of ability so AVL tree is a self-balancing binary search tree so it should obey the property of binary search tree as well as it should obey the balancing factors for every node so here there will be a balancing factor which is which can be a value of the minus one zero or one so we have to calculate this balancing factor for every node and it should be one among these three values so the balancing factor the calculation of balancing factor is the height of left subtree - height of right subtree so for every node we have to calculate and for every node the balancing factor should be either minus one zero or one so that is the property of AVL tree so in order to apply the operations that means if you apply the insertion operation or a deletion operation again if you insert any node after inserting the load again we have to calculate this balancing factor so that the it should obey the property of both the binary search tree as well as an AVL tree so it should not deviate from the property right so after insertion or deletion so if it doesn't satisfy this AVL tree I mean the property of AVL tree that is called an imbalance in node so that means if we any node is having a balancing factor which is greater than one and a less than minus one then that is called an imbalance in more so for that balancing node we have to balance the node by using a few rotations so first we have to apply the insertion or deletion and again and then again we have to check for the property of a real drink if it violates the property of AVL tree we have to convert it to acid balance your drink by using these rotations see there are mainly four rotations we can apply the first one is the first one is if the node see if the tree is like this if the tree is like this so now calculate the balancing factor for this you know I mean every go for this thing so for C there are no left change and branch a Lobel so the balancing factor is 0 for B there is a left change so then leaves left subtree and there is no right separating so the height of let left subtree is 1 and height of right subtree is 0 so that is equal to 1 minus 0 that is 1 and here 2 minus 0 that is equal to 2 so here the node a it violates the AVL tree property because the balancing factor for a is 2 which is not in a range of minus 1 0 and 1 so here this is called so why it became because after inserting C to the left of left subtree so insertion inserting load on left of left subtree left off left subtree so that's why this rotation is called yell L rotation so this is called a L rotation left of left rotation right so hope you understood this one now we have to rotate towards the right see for this condition with how to rotate towards alright so in order to keep this tree as a balance in it we have to rotate it towards the right so after rotation towards the right we get three as a root node lay as a left for see as a left yes right okay so here if you apply the again the AVL tree if you calculate the balancing factor for C it is a zero because I hiked the relief through the a is in front and be the height of the left subtree is one light up right subtree is 1 so 1 minus 1 which is equal to 0 so that means the values are in between minus 1 0 and 1 so that's why this tree is a balancing tree and this is not a balance and this is an imbalance tree because the high the balancing factor of a is 2 so this is how we can apply for elderly rotation left left rotation thanks the second condition second one similarly right skewed so previously we have seen the left Q naught X Q here also the same thing so the value of the balancing factor of node C is zero balancing back off node B is minus 1 because 0 minus 1 left 2 3 - right subtree so minus 1 here it is a minus 2 again the node a is having it violates the AVL tree property so here how it becomes a right skill inserting a node on right of kites entry that's what if we call it as our our rotation our rotation so in such case we have to balance the drilling by rotating on left-hand side rotating the three on left-hand side so that's one after rotating we will get at B yes the left side and C as a right shape so if you again apply the AVL tree that means if you are buying the balancing factor for this one it will be 0 0 and obviously it will disappear right so this is called our our rotation right right rotation next if the situation is like this a b c so b is a left child for a c is a right change different B now what's the balance to vector for this one it's a leaf node Susan role for be left is 0 right is 1 it will be minus 1 next right side and if our left side is 1 & 2 right side is 0 so 2 minus root 2 so here again at Laurier toilets because in our ammonia is in balance so now we have to balance it so this can be done so this happens when inserting a node on right of left sub-tree right of left sub-tree right so this is yes our rotation lr left sub-tree inserting an order right left the sub-tree inserting a node at right so left sub-tree inserting a node at right so don't get confused so inserting a node on right of left subtree so that is what we yell are left to subtree on right side right so this can be balancing in two steps in two steps so first step first step see consider this one right where we have an imbalance alone it is not at node a so just ignore the root node and from the next node you just rotate towards left rotate towards left so after rotating towards left what will be with getting so a B C right so this is the result we get after rotating the subtree or towards the left okay so there is the first step so now this is the left skewed so always in the left right rotation after applying the first step we'll get the left skewed three from the left stood in the step two in the step two what we have to do so this is nothing but e al rotation so after foster step we should not calculate the ballet factor right so this is a stew two-step process yellow rotation is a two-step process so far after the first step we have to consider I mean we get the left stood tree so this left skewed tree should be parented so by using the ll rotation so previously we have seen the daily relations so here we have to rotate towards left including the hoop datum including the root so after rotation towards the right we'll get a C so this is how we get them present so this one so this is a condition where inserting a node on a right side of left subtree right side of left subtree right so that's why we call it as an L our rotation you have two sub tree right right side left subtree right side so this process can be done that means this imbalances will be converted to the balance within the two-step process two-step process so first step other than the home fold rotate all the remaining rows towards the left side right so first apply the left then apply the rotation simple logic so first apply the left and second apply the rotation so simple logic first rotate all the lowers except the root so then obviously we will get the left skewed three left stood three and in the second step this is a left skewed we have seen the ll rotation been how to apply the ll rotation so once again I am saying that after the step one you should not calculate the balancing factor because this is a two-step process we have to complete the two steps and then only we have to calculate the balancing factor right so let's stood three so we have to apply the rotation in the second process so first step left second step right so right say rotation so we get this one so this is called a L R no tension right so similarly we have to go with the one more thing that is see there is a one more thing a B and C so this is the next condition so here we can see that this the balancing factor for C is 0 for B is minus 1 for a is minus 2 again for the load a it is it imbalance right so in such case this is also a 2 step process so here how will we got this imbalance after inserting the element towards left towards left of right sub left of right sub-tree so this is called right subtree left website right subtree left side so this is for L or RL rotation or L probation so this also the same process it's a two-step process after completion of the first step we should not calculate the balancing factor so they see so what's the first step what operation we have to perform in the first step we have to perform the right right operation right so by that means you have to rotate rotate towards the right side so exit the route except the except the roof front we have to apply the right operation I mean rotation operation towards right right so after applying the right we get the right skewed ring so one thing you have to remember that always after the first step of our El rotation we get the right skill drill and after of the first step on el our rotation will get the result has left center right then so we got this one after the first system and coming to the second step see consider this one right answer this one what you have to do in the second step we have to apply the left rotation including the right this we have to do so after playing the left left rotation so this is nothing but our rotation our of rotation so after playing this one we get B yes a left chain seniors mij now the balancing factor is zero for all these things so this is a balancing trick right so this is called our El rotation the first system will have to rotate towards the right except the root node and the second step will get the right sub right skewed tree so we have to apply them our rotation our rotation means we have to apply the left probation right so this is how we can apply the rotations and with the help of these rotations we can have the imbalance - tree - the balancing tree after performing the insertion or deletion so that means after performing the insertion or deletion if there is any change in our a beer tree that between infant is a while it's a military property then we have to apply these rotations and we have to reform the unbalanced - I mean imbalance of tree to balance of tree right so see rotations first point is we have seen Yeley l rotation yell and rotation which is a left skewed three and the second one we have seen on our rotation which is right skewed Thurman L R rotation on the left to say left to take a right-center and the fourth one is our El rotation right this is how this is the different rotations we have seen and these two will come under single rotations so that means we'll perform holy this small rotation single rotation and this is it will perform double rotation double rotation single rotation and the double rotation so this is a two-step process two-step process from the first step we have to apply the El and I mean we have to rotate towards the left and the second step will have to rotate the words right here in the first step we will rotate towards the right second step we will rotate towards the left right so in the lr after the first step we'll get the left skewed tree in the arm will get the result as rites tube right so this is how we have to apply rotations in order to change the imbalance condition to balance a condition right so if you are having any doubts regarding these patients feel free to post your doubts in the comment section so that definitely I will try to clarify all your terms and if you really understood my sessions like my sessions share my sessions with your friends and don't forget to subscribe to our channel thanks for watching thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 21,598

Keywords: sundeep, saradhi, kanthety, data structures, lists, trees, linear, non linear, linked lists, ds fundamentals, ds basics, nodes, parent, child, leaf node, sub tree, root node, tree terminology, TREES IN DATA STRUCTURES, binary trees, binary search trees, binary search, right subtree, left subtree, AVL TREE, BALANCING FACTOR, SELF BALANCING, HEIGHT OF LEFT SUBTREE, HEIGHT OF RIGHT SUBTREE, HEIGHT DIFFERENCE, ROTATIONS, RR ROTATION, LL ROTATION, LR ROTATION, RL ROTATION

Id: moTfpnEuhlg

Length: 20min 55sec (1255 seconds)

Published: Thu Aug 08 2019