AVL TREE CONSTRUCTION | ELEMENT INSERTION - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous sessions we have seen the AVL trees and different rotations that can be performed upon aviatrix so first of all we recall the previous concepts so first one what is an AVL tree so AVL tree is a self-balancing binary search tree so that means it should obey the property of binary search tree as well as it should obey the property of a BLT so here the property of behavioral tree is every node should have a balancing factor with a value minus 1 0 or 1 so how to calculate this balancing factor so balancing factor can be calculated as the difference between the height of the left subtree and height of the right subtree right so if for every node we have to calculate the balancing factor and that dancing factor should be either 0 or 1 or a minus 1 so which violates this property that is that is called as imbalance in binary search tree it's not an avian tree right so if you are inserting any node into the AVL tree or if you are trying to delete a node from the behavioral tree then there is a chance of violating this rule that means if you insert an element into the AVL tree then the balancing factor may change for that particular node right so that means the tree may be imbalance in tree so we have to convert that imbalance in tree to balancing tree so for this conversion we we're supposed to use the burn among the four rotations which we have seen in the previous sessions so I will give you the link in the description section just follow that before watching this session right so there are four rotations there is a ll rotation RR rotation yellow hour rotation RL footage right now let us see an example and let us construct an AVL tree for the given nodes right now let us see this example let us take these elements and now we have to we have to construct the aviary that means inserting one element after another and we have to take care or what happen remember that after inserting an element we have to check for the two properties one is the binary search tree that means all the left side nodes should be less than the room floor and all the right side moves should be greater than the boom there's the property we have to remember and then we have to remember the second property that is a AVL tree property that is if for every node the balancing factor that means a for every node the height of the left left subtree - height of the right subtree must be either 1 minus 1 or 0 so two properties you should be remembered there is a BST property second one is an AVL property right so after in first consider the punty so faster step so 20 is a root because empty so here abl tree is an empty so 20 is the root load now second step inside the 30 insert 30 so after inserting that - 30 so based upon the property of BST and ability so based upon the BST property 30 is greater than 40 so 30 should be inserted on the right hand side of 20 right so this is the first first one second one immediately I mean AVL property AVL property means B this balancing factor should be either 1 0 or minus 1 right so basic vector so balancing factor means height of left subtree - height of right subtree so here the height of left subtree so there are no roads so zero the height of left subtree is zero height of right something for this 20 right for this 20 there is only one though so 0 minus 1 is 1 the bananas in factories - 1 420 430 it is a leaf road so you see it is a leaf node there will be no right children and left children so there's only the balancing proper the velocity factor will be 0 so minus 1 and 0 so both are within the range so this is also correct same balance it's a balancing third step we have to insert the third rivet ad so 80 is it greater than 20 so it should be inserted on left I made right-hand side so in the right hands in again there is a 30 so in the 30 also it is greater than 30 so it should be inserted towards right most of this 30 so after insulting this one the tree will be 30 ad right so coming to the third one so this is about the BST this is a binary search tree now we have to go with the AVL property a whale property means we have to find out the bouncy vector so from top always calculate the balancing factor factor from bottom to top so what are the top this is a Leafs room so the balancing factor will be zero so this is a road with only one element that is also rightmost in so these are left hand side there are going bits right so if F is equal to 0 minus 1 this is minus 1 and again here also there are lower left-hand side elements only the right hand side elements what's the height of this node right subtree height of right subtrees - right so height means the longest path from don't pro - I mean that goal to live board so to hear the balancing factor is to left side balance effect I mean you have to side a height is 0 so 0 minus 2 it is minus 2 so which violates Jagr property because all from every node the balancing factor should be either minus one zero one here we got the two the balancing bypass two right so here this is an imbalance it clean so this is an imbalance it ring so what we have to do in order to get this imbalance to balance we have to use one among the four rotations what are the four relations what is la are our yell are are all these other rotations so based upon the situation we have to apply this one so this is the right skewed right skewed so when we got these imbalances wherever we are inserting an element to the right sub-tree towards the rightmost element so that means this is called our rotation so we have to apply the our our rotation so after applying the our rotation means we have to rotate this towards the left side our winds towards left so we have to rotate in this direction we have to rotate in this direction so after rotating this one we will get so that we will be moved here thirty will be moved towards the left 480 will be moved towards all right so after rotating after applying the other rotation will help the result as this one so here now we have to calculate the balancing factor so these are the leaf nodes the vanishing factor will be zero and this is the node for this dancing filtration left side height - right side left side head is one right side height is 1 so 1 minus 1 it is again 0 so it is the property of aviary right now fourth one fourth element so we have to incent the 40 April for me so now the three is like this 30 towards the left there is a 20 towards the right there is an ad now we have to insert the element 40 so again that should know better be hasty property so 40 is greater than 30 so it should be inserted on a right circuit and again 80 is a route here so 40 is less than in D so here we have to insert the 40 has a left sub-tree for node 80 now so this this satisfies the BST because all the elements of right subtree are less rather than mu all the events of left subtree are less than root this this property isn't now coming to the AVL property so the primary behavioral property we have to find out the balancing factor so pump balancing factor for the leaf nodes is zero and for this road one minus zero so right subtree zero so one minus zero one and for this one one minus two because the right subtree for this 30 is to the height of right subtrees to the height of left subtree is 1 so 1 minus 2 it is minus 1 so all the balancing factors are within the range minus 1 0 and 1 so it is a balance now coming to the v 2 v 1 so we have to insert the element 10 so same property we have to use so 30 2018 so two words I left there is a 40 - 40 now we have to insert the tenon so n is less than 30 so 10 should be inserted towards the left hand side left subtree either of certainly there is a 1 hood 20 so 10 is less than 40 10 is less than 40 so 10 should be placed towards the left hand side 10 should be placed towards the left hand side right so who you know may still be SG because all the elements of left subtree are less than and all the elements of right sub-tree or greater than root Damon right so now we will go with the AVL by calculating the Bands effectors so biasing factors of this one is zero and this element is 1 - 0 1 1 - 0 it is 1 this 1 2 - 2 0 right so again this is a balancing tree now 6 that means we have to insert the element 60 so 30 2080 10 40 now we have to insert an element 60 so 60 is greater than 36 G is greater than room so we have to insert the 16 towards the like sick somewhere it says the boot is 80 so 60 is again less than 80 so 60 should be towards the left hand side of left subtree of 80 again have to simply we are having 40 so 60 is greater than 40 so 60 is greater than 40 means we have to insert this steel here itself towards its right side towards it right right so here we are inside so you think the DST property is satisfied because all the elements of right subtree are greater than whom all the elements of you have subtree are less them who this satisfies now calculate an AVL tree now calculate the property of via greenery so the leaf nodes it will be 0 and for this one 0 minus 1 X minus 1 for this one 2 minus 0 is it - so just stop it so we need not go with the remaining rooms so here it Wireless the egg indeed it violates the Eric right so here we have to stop so if you are observing this one when we got this imbalance so this is in balance this is the imbalance right so in order to change these imbalances to balance what we have to do to have to apply one among these four rotations so here when we have getting this violation wherever we have insulting an element towards the right side right side okay and see so here we have got the violation 480 right so left side right side okay left and right so you can observe this one so this we got then coalition so this is the left node right moon left node right node so that means yellow rotation you have to apply the yell our rotation so this is a two-step process so this is the two-step process so for the first step we have to apply them step 1 we have to rotate left side so we have to rotate left side left side means C this way so after applying this one so let us erase this one after applying this one we get so 30 20 and 80 now after rotation 60 will become here 16 forty right so this is the first system so after second step so what we have to do second step rotate right rotate right so in this way we have to be in this way we have to prove it right so then it will becomes so 30 20 10 60 40 80 so this becomes this one right now so now we have to calculate the balancing factor so here we should not calculate the balance event because this is a hello rotation Allah notation means two-step process so on after completion of two steps something we have to calculate the balancing factor so these are the leaf nodes the balancing might turn to be 0 and for this lure the balancing factor will be 0 for this load the magazine factor will be 1 and for this note the balancing factor will be 0 because height of collapse of tricks to either by accepting is also to now having to the seventh one so we have to insert 50 for this one so 30 2010 1640 ad so now we have to insert the 15 but it should it doesn't violate study history so if you insert a 50 so 50 is greater than 30 so it should be on the left to the right sub-tree 50 is less than 60 it should be on the right subtree left something and 50 is greater than 40 it should be on for example now again calculate the balancing factor so further he floats it is a zero zero zero for this 1 0 minus 1 it's the minus 1 for this one 2 minus 1 1 for this one too - thing it's a minus 1 so it's satisfying so it's a balancing tree because for every node but this one so funky for this one it's a balanced agree because for every note the balancing factor is either 1 0 or minus 1 now insertion orphan so 8 we have will insert the 70 so 30 20 and 60 40 1850 right so this one now we have to insert the 70 that should not violate the BST so 7 is greater than 30 so it should be inserted towards the right subtree so in that way it's not 360 is there so 70s later than 60 again we have to go to the avoid subtree in the right subtree there is a 80 so 70 is less than 80 so 17 should be placed here yourself so that that means it should be placed towards the left hand side for party which is a 50 and for 80 it is 1/7 480 it is a 70 right so this is how we can we have to apply right so here you can see the balancing factor so far the difference the balancing factor is 0 and for this one it is 1 for this one minus one for this one one and for this one 2 minus 2 0 for this one too - thing minus 1 so here it opens the property of AVL tree so that is why it is it balanced so it opens the BST property and it also a pistol regulatory property right so hope you understood this example so don't get confused so just we have to we have to satisfy the BST property binary search tree property so based upon the binary search tree property we have to insert the node into the AVL tree that means the element should be compared with the rule and then we have to decide whether it should be inserted towards the left side or it should be exactly towards the right side that is a positive thing so after insertion second thing we have to check for the balancing factor so whether the tree is a balanced or not so that's the definition of a mayonnaise right self-balancing binary search tree so for the balancing factor we have to calculate the height of a left subtree - height of the right subtree so if the balancing factor is other than minus 1 or 0 or 1 that tree is a imbalance a tree so for changing the beam balance a tree to balance a tree we have to choose one among the four rotations so ll notation our rotation L our rotation RL rotation right so based upon that thing so here L our rotation and RL rotation are two-step process so in the lr rotation first we have to apply the left rotation and then we have to in the second step we have to apply them right odisha coming to the RL first we have to apply the right rotation in the second step we have to apply the left rotation right so this is how we have to insert an element into the AVL tree so this is simply we call it as a construction of an event so the same process we have to apply by deleting an element from the Aviator so after deleting the element again we have to check for the BST the same process we will follow which we have followed in the BST so deleting an element from the binary search tree the same process we will follow but here in addition to that we have to calculate the balancing factor and based upon the balancing factor we have to apply the rotations to make the balance to balance right so this is a simple example so hope you understood this one so here only two rotations are that one is the this along right so if you take a one more example then okay you may get a vegetable number of rotations right so just to keep on practicing this one and if you are having any doubts regarding the process of this AVL tree construction so feel free to post your doubts in the comment section so that definitely they will try to clarify all your doubts 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 keep following thank you

Channel: Sundeep Saradhi Kanthety

Views: 23,623

Keywords: sundeep, saradhi, kanthety, data structures, lists, trees, linear, non linear, linked lists, ds fundamentals, ds basics, parent, child, leaf node, sub tree, root node, tree terminology, TREES IN DATA STRUCTURES, binary trees, binary search trees, binary search, 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, INSERTION, CONSTRUCTION

Id: 1vdBtBVnP9c

Length: 22min 14sec (1334 seconds)

Published: Thu Aug 08 2019