5.15 AVL Tree Deletion in Data structures | with Example | DSA Tutorials

hi guys welcome back in this video I'm going to discuss with you how to delete data from AVL tree right in the previous video we have already discussed how to create AVL tree recorder you can see how to insert data in AVL tree and all about the events if you want put you out that video i'll give you the link it in the description box you can check it out fine so today we will discuss how to delete data from AVL tree see this is the ability we have created in the last video now suppose you want to delete data first in this series eight seven then eleven and fourteen then seventeen fine see AVL tree is what first of all it is a BST second is a second is the balance factor of each and every node should be either minus one zero one and balance factor is to be created how a height of left subtree - height of right subtree or maybe somewhere it is also written height of right subtree - hydro left subtree fine okay so when you delete the data from AVL tree you need to keep in mind two things first of all deletion would be same as in BST and we have already discussed how to delete data from BST the link of that video also I will give you in the description box fine the first point is delete data same as you delete data in BST fine second point is after deletion of data from this tree you need to check out the balance factor of each node again all right and the balance factor is minus 1 0 or 1 in that case tree is balanced no need to balance it out if the balance factor is out of this range minus 1 0 and 1 then you need to balance it out using that AVL rotations for types of rotation we have discussed left left right right left right and right left fine so let us discuss now suppose first of all you want to believe this it okay find out where is it whatever it is see this AVL trees first of all be a steena so how to find out it compare with this root 8 is less than 14 go to the left part it is less than 11 go to the left part here is 7 8 is greater than seven through here is eight yeah we have found her fear of finding from this hey now how to delete see deletion would be same as in BST right so this node is having no child it is leaf node so directly you can delete this node fine like this okay and after deletion of this 8 the tree would be something like this we have already we have billeted this it now it's not like that check out the next number and delete 7 second thing is you need to check out the balance factor of each node again fine now check out the balance factor after deletion balance effect of this one is zero this one is left minus right is one this one is zero this one is 0 minus 1 minus 1 this one is height of left subtree 1 too high to fry it is also 2 that is 0 this one balance factor is 0 this one is also a zero balance factor of this is also 0 0 1 minus 0 that is one balance factor of 19 is 1/2 hi Toph left subtree is too high to fry it is also 2 that is 2 minus 2 is 0 fine and height of left subtree of this 14 is 1 2 & 3 3 minus 1 2 3 0 so this tree is balanced no need to balance it out now check out the next number 2 middle next number is 7 find out where is 7 compare with 14 less than 14 go to left less than 11 go to left we found seven fine now we have to delete this number now check out is this number is having any children yes this is having one child that is left child for now how to delete the 7 you will replace this 7 with this with its child either its left or right child one child had in there there would be no problem I know which will child over left or right you would replace the deleted node from his child fine so when we will believe this 7 then the tree would be 14 see this right part would be as it is this would be unaffected part of this tree only the affected part is this the left subtree so 11 is add as it is when you delete this seven fine then directly in four will will be linked with this 11 or you can say the 7 would be replaced with this for now 11 here we have for right side of 11 is 2l and here we have 13 fine now next is see next is 11 but don't you cannot directly delete this 11 after deletion next task is what you have to check out the balance factor of each node fine now see balance factor of this 4 is 0 13 is 0 to L EA 0 minus 1 minus 1 for 11 it is 1 minus 2 that is minus 1 and it's this part was unaffected the balance factor would be same like 0 0 0 0 here is 1 here we have 0 in here we have see this would be affected sorry you know the height of left's appraised and now 1 & 2 it's not like 1 & 2 you are supposed to check the height 2 you are supposed to go to the leaf node and height up to leaf node is 1 2 & 3 fine 3 minus 1 2 3 that is 3 minus 3 0 still this tree is balanced okay no need to balance it out next to how to delete is 11 now find out where is 11 11 is this node this one you have to delete now now check it out this node deletion would be same as in BST this node is having two children one is left and one is right now the node this node being deleted will be replaced with which of its children left right you have to check it out and here we have two cases you can replace it with this node with its inorder predecessor or with its inorder successor in order predecessor case you find out cutting in order predecessor would be C predecessor means just parallel scheme by fine inorder predecessor would be the largest element from the left subtree of the node being deleted right and you know the successor would be the smallest element from the right subtree of this node fine so we will suppose replace the this node with its inorder predecessor we'll just take one case then after deletion of eleven the tree would be here we have 14 the right part would be unaffected and that is 53 here we have 60 here we have 20 here we have 17 and here we have 16 now you have to delete this 11 find out its in order predecessor you know order predecessor is go to its left subtree in left subtree we have only one element that is 4 so obviously there is a largest element from this left subtree would be 4 so we can replace this 11 with 4 fine in the left of 4 there is nothing in the right of 4 we will have this 2 n and this 13 because this 11 is replaced by this for now the right subtree will be same second case would be you can replace this 11 with its successor successor is the smallest element from this right subtree and out of this 2l and 13 what is the smallest element that is 2 L so you can replace this 11 with 12 then here you can write to L here you have 4 and here would how 13 that would be the second is okay now check out the balance factor of every node before deleting 14 here the same balance factor would be there because this node was this right subtree was unaffected now check out zero balance factor of 12 is 0 minus 1 that is minus 1 balance factor of this 4 is now height of left subtree 0 height of right subtree is one end to 0 minus 2 that is minus 2 right now see this minus 2 is not within this range minus 1 0 and 1 so this node is critical node now you have to balance it out fine this one now we are working with this part of me now we have already discussed the AVL rotations which case is this see this right hand right are our rotations fine and how this can be balanced are our rotations cooking our rotation make out there we just do one left rotation why by doing the one left rotation you can balance out this one and how this left rotation would be done this is left rotation see this trees and by this node is unbalanced now or you can say this node is critical now so you just pull down this for like this then twelve would go up and thirteen would be the right of twelve and four would be to the left of this twelve so you are supposed to do the left rotation fine it's couple left move corner then the four would be pulled down okay now the tree would be here am i I'm ending this tree 14 the right subtree would be same fine the left subtree would be four would go this displays here boom pow 12 he would have 13 and here we will have four by this left rotation will pull down this for twelve would go up this is now the left subtree and the right is same 19 would have here we got 50 360 2017 and 60 right now see before deleting this 14 check out the balance factor of each and every node is this now balanced tree because we have this are our rotation we have done this are our rotation so 0 0 here we have 0 and this tree was unaffected so this one is also 0 0 same as this one right 14 can be 1 2 2 minus 1 2 3 that is - 1 so this ray is now balanced now what you have to delete is you how to delete this 14 now huh 14 would be deleted see again 14 is having two children one is left and one is right then how this 14 this 14 would be replaced with which one either you can replace this 14 with inorder predecessor or inorder successor deletion would be same as in DST okay now you have to delete this 14 now find out this inorder predecessor okay in order we will disable replace this 14 with its inorder predecessor in order predecessor is C this is the left subtree of 14 the node being deleted the left subtree of the node being deleted is this one so inorder predecessor is what the largest element from this left subtree of that node largest element out of 4 12 and 13 is what 13 so you can replace this 14 with 13 or second cases inorder successor you know the successor is the smallest element from this right subtree so out of these elements smallest element is 16 so you will delete this 16 from here and you will replace this 14 with this here you can write 16 right so we'll discuss one case we will replace this 14 with it's in order predecessor so 13 would go up right part would be safe 53 here we have 60 here we have 20 here we have 17 and here we have 16 and the love left part would be 12 common a 1400 hinari play square there with this 13 to 13 years a couch I have not delete and here boot out well and for now before deleting the 17 second step Cayuga you need to check out the balance factor of each no balance factor of 4 is 12 14 is 1 - 0 this 1 is unaffected 0 0 0 0 1 - 0 that is 1 2 - 2 that is 0 1 2 2 - 1 2 3 that is minus 1 so the story is balanced now delete the 17 find out where is 17 17 is greater than 13 go to the next right part 17 is less than 19 go to the left part here we find 17 now 17 is having only one child so no problem is they're just simply delete this 17 and replace 17 with this 16 then the 3 would be 13 1953 60 20 and here is 16 happy him - well and here picky over for now check out the balance factor of each node balance factor is 0 1 0 0 0 1 minus 1 0 1 minus 2 that is minus 1 2 minus 3 that is minus 1 so this tray is balanced like this you can delete data from a value you just have to remember deletion would be same as in BST first step delete data as you have belittled in BST second step is after deletion check out the balance factor of each node if tree is balanced then you can proceed you can delete the next number if tree is unbalanced you output Jack out which rotation is there by which rotation you can balance it out if tree is unbalanced after deletion then balanced output that tree first then you can proceed with your deletion okay so I'll see in the next video till then bye bye take care