5.14 AVL tree Insertion | with solved example | Data structures

hi guys welcome back in this video I'm going to discuss with you how to insert data in AVL tree or you can say how to construct our AVL tree so the question is you're supposed to construct AVL tree by inserting the following data I mean these numbers from left to right fine okay now first of all what is their first number is 14 so first insert 14 because the static maybe have empathy trees or just create a node and insert this 1414 we have inserted fine now find out the balance factor of 14 is 0 this is balanced this is the balanced tree fine next is 17 the waves 17 should be inserted see AVL tree is first of all it is BST and second is height of left subtree - ID of light right subtree would be either minus 1 0 or 1 the where 17 would be inserted 17 check karo 17 is greater than 14 to 17 would be inserted here only fine now check out the balance factor balance factor of the 17 is left - right height 0 height of left is 0 and height of 4 writers 0 - 1 that is minus 1 so no need to balance it out it is already balanced now insert this 11 fine now where this 11 would be inserted 11 is less than 14 the 11 would be inserted to the left of 14 still this tree is balanced because balance factor of 11 is zero balance factor of 17 is also zero balance factor of 40 knees height of left subtree - IRA Freid subtree that is 1 - 1 0 fine see after inserting each and every node we are supposed to check the balance factor for each node hi next is 7 now where 7 would be inserted 7 check less than 14 less than 11 those 7 would be inserted here only now find out a balance factor balance factor of 7 is zero balance factor of this 11 is 1 - 0 1 that is also fine this balance factor of 17 is 0 14 is highteeeee kic open e 1 n 2 fine 2 - 1 1 so that is also fine in order to balance it out next answered 53 53 is greater than 1453 greater than the 17 the 53 would be inserted here only fine now also this is balanced zero balance vector zero balance vector balance factory zero minus 1 that is minus 1 well inspector of this 1 is 1 minus 0 that is 1 and balance factor of 14 is 1/2 height of left is my two height of right is 2 that is 0 right 0 1 and minus 1 okay now insert the next element next is 4 now where this 4 would be inserted four is less than 14 4 is less than 11 4 is less than 7 though it would be inserted also to the left of 7 left side fine left off 7 this 4 would be inserted now check out the balance factor balance factor of this 4s 0 fine balance factor of 7 is 1 right sub-tree key height is 0 1 minus 0 that is one balance factor of 11 is what height of left subtree height of left subtree is 1 n 2 2 minus 0 that is 2 fine and this is not either minus 1 0 or 1 so this node is a you can say critical node because of this node this trees and but unbalanced so before inserting next numbers in this tree you have to balance it out first of all I know okay now how to balance out this tree see find out why this tree is unbalanced this tree is unbalanced because because of this left insertion and again left insertion fine left and again left so you can say either you can say this is left left rotation ll rotation fine and how to solve this left left rotation making out there only one right route datian right Muslim like this right rotation fine and how that right rotation would be there this 11 would be pulled down and 707 would go up or simple the shortcut is see these are we are working in on these three elements 11 7 and for the median out of these element the median element would always be the root and the remaining element would be children of that element out of 4 7 and 11 but what is the median element that is 7 only 7 would be the root ARA PA rule according a are accepted in the left left rotation though half al or L so in that case one right rotation would be there fine the tree would be 14 would be as a tease 17 would be as a tease 53 would be as a tease now what is this right rotation pull out this or you can say pull down this 11 to the right side right rotation or median of this one is 7 so 7 would be 7 would go up that would become the root find 11 and 4 that would be the children of this 7 4 would be to the left of 7 and 11 would be to the right of 7 because it is BST to greater element would be the tri in the right side and less element would be the left side fine now check out the balance vector 0 0 1 minus 1 0 0 minus 1 1 2 1 2 2 minus 2 0 this is balanced 3 now next element to be inserted is this 13 where 13 needs to be inserted 13 is less than 14 13 is greater than 7 third go to the right part in 13 a is greater than eleventh we would go again to the right part that is here threating would be inserted now find out the balance factor of each and every node balance factor of 13 is zero balance factor of 11 is 0-1 that is -1 balance factor of 4 is zero balance factor of 7 is height of left subtree is 1 - site of right subtrees 1 2 that is minus 1 0 here we have minus 1 C 14 left of a sorry height of left subtree is how much one say you can't say 1 & 2 that is the height because you are supposed to go to the leaf node Kooskia height thickening up so you have say like a 1 yeah how's he like a heart to and from the snow to the leaf node 3 1 2 & 3 3 minus 1 to 1 so obviously this tree is balanced okay now next s you have to insert this to L now where this 12 would be inserted this 2l is obviously this less than 14 and greater than 7 and greater than 11 but less than this so here the 12 will be inserted now find out the wine inspector balance factor of the balance factor of this 12 is 0 this 1 is 1 minus 0 that is 1 this one is height of left subtree is there any element to the left of 11 no so 0 minus height of right subtrees 1 & 2 that is minus 2 fine and that is not possible in AVL tree fine so we will work on this part this is our critical node or you can see the unbalanced node and with this node as unbalanced because of first of all this right insertion and then left insertion so here it is right left rotation and how to solve this right left rotation first right rotation - rotation would be there first right rotation and then left rotation okay see first right rotation how the tree would be constructed 14 here we have seven here we have 17 here we have 53 here we have four now first of all right rotation take a right rotation is Takeshi of the right rotation would be on this part because we will make it right a right rotation okay so this 13 would be pulley down and 12 will go up seven here we have 11 now here this 12 will go up and 13 would go and there only fine so now this becomes right and right are our rotation still this is unbalanced because the balance factor of 11 is minus 2 still it is unbalanced and it is having minus 1 it is having 0 now next part is first is right rotation next is left rotation to have near R&R the one left rotation would be there and the tree would be 14 17:53 here we have 7 here we have force and do this left rotation left rotation means pull down this 11 the side left side then 12 would go up 12 this side left side of 12 is 11 and right side is 13 fine so this is a balanced string or simple trick is see this is right or left rotation always you have to take care the median element of these three would be the root and remaining two elements would be the children see you can check out out of eleven twelve and thirteen which one is the middle element or the median element out of eleven twelve and thirteen or baselet well now see after two rotation right and left we got what to L is the root and eleven and thirteen would be the children so it is BST so you can easily do this here to the left of 1211 would be there and to the right of 2013 would be there yes this is the simple trick find out the median element and that would be the root okay now this is balanced tree you can check out by finding the balance factor of each and every node fine now next next you how to insert is this 8 okay now where this 8 would be inserted left over 14 it is greater than 7 go to the right part it is less than 12 or to the left part it is less than this 11 go to the left part this is 8 pi now see find out the balance vector after every insertion you're supposed to find out the balance vector balance factor of this 8 is zero balance spectro this one is 1-0 that is 1/12 Kelley a 1/2 2 minus 1 that is 1 here we have zero and here we have 1 minus 1 2 & 3 see balance factor of 7 is height of left subtree is 1 minus height of right subtree of the 7 is 1 2 & 3 right 1 minus 3 that is minus 2 so you can take a 1 and 2 you can write height 1 minus 2 you are supposed to check the longest height go to the leaf the 1 2 & 3 that is minus 2 all right so this 7 is now a critical node okay now why this minus 2 y the 7 is unbalanced find out the reason because because of this first of all this right insertion and then this left insertion because of this right and left the left this node is unbalanced so you will work on this part seven - Ln 11 fine say right and left right and left - rotation would be their first right rotation then left rotation okay we have discussed in detail with the help of this case now second the shortcut is what just find out the median element out of seven twelve and eleven what is the median element seven eleven or twelve c7 K by the eleven I can then to Eliza became BST in sorted order then what is the median element amid an element is eleven okay so eleven would be the root and seven and 12 would be children of this eleven okay now the three would be something like this see after this the tree would be 40 1753 see that part is unaffected part fine now out of this 11 is median so 11 would be to the go to the root here 11 would be there fine and 7 and to a large children of this 11th oh seven eight children off 11th and seven obviously would go to the left part because seven is less than 11 and 12 would go to the right part with us 2 L is greater than 11 now where this four would go for will go to the left part of 7c left part of 7 schedule right for now where this 13 would go 13 is to the right of 2 L say check out industry because we are creating this from this only we're balancing out the string so 13 is to the right of 2 n fine and where this 8 would go now check out 8 is to the left of 11 in this tree so basically in this tree the 8 would be to the left of 11 right now go to the 11 node having key 11 now we're to the left of 11 but you can't insert 8 at this place because here is 7 only so it would go to the right of 7 why so because 8 is greater than 7 and this is BST so you know the rule very well because the element greater than that node will go to the right of that mode fine so this is a BST now and this is balanced you can check out this by checking out the balance factor of each and every node fine ok now next inserted element is what 60 where the 60 would be inserted 60 always check out from the root greater than 14 and greater than 17 greater than 50 53 the 60 would be inserted here only fine now find out the balance vector balance factor of 60 is zero balance factor of 53 zero minus 1 that is minus 117 is zero minus 2 that is minus 2 here we have some problem because it is not minus 1 or 0 not 1 okay now and balance factor of each and every is 0 0 0 here we have 0 minus 1 minus 1 here we have 1 minus 1 0 here we have 2 minus 2 0 I know you do not find out the benefit of this one because we have this node unbalanced so you're supposed to balance it out first of all so you will work on this part and the 17 is unbalanced because first of all this right insertion again right insertion that is our our rotation a rotation make out there 1 left rotation would be there fine like this 17 would be pulled down 53 would go or you can say the median element find out the median element out of these three elements out of 1753 and 60 what is the median element or middle element 53 53 would be the root and 17 and 60 would be children of this 50 53 now then over the tree would be C will draw this tree here really fine this 14 the left subtree would be unaffected 11 7 here we have 4 here we have 8 here we have 12 here you have 13 now the middle element is 53 53 would go up that is 53 becomes the root 17 and 60 would be the children 17 is less than 53 so it would go to the left part 60s would go to the right part okay now the you can check out the balance web profusion of your node industries balanced now insert 19 where 19 would be inserted greater than 14 less than 53 greater than 17 letters here 19 would be inserted fine you can find out the balance factor of each and every node and still this tree is balanced fine okay now 16 would be inserted where 16 would be inserted 16 would be inserted to the left of 17 here 16 would be inserted still this trace is balanced you can find out the balance vector 0 0 1 minus 1 0 1 2 2 minus 1 1 balanced 0 0 0 0 2 minus 2 0 here we have 0 here we have 0 minus 1 1 here we have 1 2 3 3 minus 1 2 3 3 minus 3 is 0 ok now insert this 20/20 would be inserted here only to the right of 19 now check out the balanced vector the balanced factor of 20 is 0 balanced factor of 19 is 0 minus 1 that is minus 1 16 is 0 17 1 minus 2 that is minus sorry 1 minus 2 that is minus 1 ok and balanced factor of 53 is what balanced factor of 53 is height of left subtree C 1 2 but 3 also go to the last level after 16 C 16 is you can see it this place only 16 so height of left subtree is 1 2 and this 3 the longest hide the longest distance from that node to de you know that leaf node you are supposed to go 3 minus 1 that is minus 2 so this 53 is our critical node or you can say the unbalanced node why this tree is unbanned why this sorry node is unbalanced because of left insertion and then right insertion okay you're supposed to find out the reason though here with rotation would be there left and then right so you would work on this part only on these three in 150 37919 okay now in left/right rotation how to solve this out we are supposed to do two rotation first is left then right okay left rotation on these two elements take a left rotation means 17 would go below and 19 would go up 19 a happy I got 17 I got then it would become left and left I'll draw see 14 left part is as it is okay 7 8 12 and 13 first see we have left right then first rotation would be left rotation left rotation because you're supposed to make it these type of you know that shape to the either ll rotation or RR rotation so here we can make it ll rotation because barely have any path starting here L this coal left banana clearly we will pull this this 17 below or 19 would go up then 53:19 would go up 17 would go below 17 k left make it happen a pass 16 right Oh 53 we have 60 and to the right of this 20s to the right of 19 here we have 20 it is unbalanced still see this is having 53 is having the balance factor is - sorry 1 2 3 3 minus 1 that is 2 here we have sorry - okay now 17 this would have 0 this would have 1 this would have 1 - 2 - 1 1 now it becomes L L rotation left left ll rotation see Ln fine ll rotation gases all what the a you will do one right rotation right rotation upkeep in Tonopah Casio V you will pull up pull this 53 down and 19 would go then the tree would be 14 11 7 4 8 here we have 2 else here we have 13 now do the right rotation 53 would go down in 19min go up so 19 would become the root to the right of 19 we will have 53 and 60 would be to the right of 53 fine and 19k left make a hog aapke 17 17 key left maybe have 16 where this 20 would go check out 20 is to the right of 19 now check out right of 19 you can't answer 20 here so 20 would be inserted to the left of 53 because 20 is less than 53 ok now this would be our tree or fine simply you can use the shortcut left and right rotation you are supposed to balance out this part find out the median element of these three elements - 17 1953 a median element would be C don't check out you pirelli 53 here then 17 then 19 the median median element would be 17 oh it is BS Tina so try to write down that data in sorted order first 17 then 19 then 53 now find out the median element median element is 19 19 would become the root okay 17 and 53 would become the children of that mode how many a same thing we have done 19 is the root fine sorry 19 is the root and 70 and 53 are the children of this 90 fine here see if you don't go this long processor with this left/right means to rotation first left rotation then right rotation then simply find out the median element then median element would become the root and remaining two elements would become the the left hand right child of that note fine that is the shortcut here nineteen is median element seventeen and fifty-three are child of children of this nineteen and then find out the proper place for though for this remaining element sixteen and twenty see somewhere you're supposed to you know can you have to keep in mind that this should be a BST so like that they see twenty if you want to insert 20 then 20 is to the right of this nineteen but in the right of this 1953 is there so it's not like you can insert twenty here or maybe twenty to the right of this nineteen find out the proper place for nine didn't go to the right of nineteen and then find out the proper place is to integrate proper places to the left of fifty-three because this is less than fifty three okay so this is how the data is to be inserted in AVL tree in the next video I'll discuss with you how to delete data from a via three till then bye-bye take it

Channel: Jenny's lectures CS/IT NET&JRF

Views: 330,950

Rating: 4.9074106 out of 5

Keywords: avl tree, avl tree rotation, avl tree examples, avl tree in data structure, what is avl tree, binary tree example, avl tree deletion example, avl tree properties, balanced binary tree, avl tree construction, avl tree definition, avl tree geeksforgeeks, construct binary tree, application of avl tree, full form of avl tree, advantages of avl tree, avl, balance bst, dsa, ugc net, gate, jenny's lectures, jayanti khatri, balancing factor in avl tree, syllabus, youtube channels

Id: _8qqlVH5NC0

Length: 26min 25sec (1585 seconds)

Published: Sat Feb 02 2019