5.21 Splay Trees Deletion | Bottom-up Splaying | Data Structure & Algorithm

so in this video we will see how to perform deletion in splay trees in the previous video we have already discussed how to perform insertion in splay trees right so this is the tree I am taking this example and I am going to delete first of all 12th and 14th and 16th right now how to delete a data from splay trees as we know splay trees are what these are also a variant of binary search trees right so the deletion operation would be would be having same process as the as in the BST binary search tree right but only difference is what after deletion you are going to perform playing operation in splay tree right after insertion also we have performed this playing operation after search also you you are going to perform splay operation right now first of all you will delete the data we will perform the same step as we have discussed in BST after that we will do splaying of this tree now splaying on which element this thing you need to take care this is the important point to note here you are going to splay this tree for which element right now see I'll tell you first of all suppose I'm going to delete first of all to L so how to delete first step is what simple perform standard BST deletion right that is the first step now in BST deletion what we will do first of all you in search for this to end where is this - L in this frame right compare with this root we are going to start obviously from the root because we are having address of the root node only right now compared 12 is less than 14 so go to the left side 12 is less than 13 go to the left side well is greater than 7 go to the right side 12 is greater than 10 go to the right side and here we go 12 right now see what is the parent of this node you want to delete this is the parent right and this is the node suppose and you want to delete right now in based a deletion this is the leaf node so you can simply delete it no need to do anything right we will discuss all the cases the node you want to delete is having on you one child or if it is having two children right in this case this node is having a zero a child so now you can simply delete it now after deletion what you need to do now after deletion of this this is the tree now that is not yet done the deletion is not yet done in splay trees now we are going to splay this tree for this element for the parent of the node you want to delete you have deleted this 12 parent of this node is 10 so you will splay this 10 now right this is the important point to note here now see suppose I have deleted this 12 this this is having no children so you can simply delete it right now parent is this one so splay this tree for this on this element you can say splay this 10 over here you can write display at 10 now I have already discussed how to lose playing operation in splay trees find out the parent of this node now this is not the parent now we are going to splay this right so suppose this is X parent of this one is this one and grandparent is this one so this is having both parent and a grandparent so that case you need to follow in that case also we have 4 sub cases now see this is what right child of parent but this is what left child of its parent both are in opposite direction so this is what zig-zag situation so here you will do zigzag rotation right now in case of zigzag rotation first we are going to perform rotation on the parent then grandparent now you have to find out which rotation left or right you need to perform see this 10 is what the right child of this parent so we are going to perform left rotation on parent right and after that right rotation on grandparent so now after first rotation the tree is something like this rotate this to the left so 10 would go up 4 & 7 go downward now this is grandparent so now rotate it with right because now this is a left child of this one so now the tree would be but now this is not yet band because 10 is still not the root splaying means if you want lose play this 10 then it means we are going to make 10 as a root of the tree but 10 is not the root still so I have told you what is that splaying algorithm we are going to write this step of splaying in while loop right in the previous video we have already discussed you can check out that video in this I button now see now again which rotation you need to apply which case is there now this 10 is what left child of this parent and the parent of 10 is what root right so now 10 is not having any grandparent so now this is what only Zig situation now which rotation you need to apply left or right this you need to take care now this is left side of 14 so we need to apply a right rotation right rotation on this root or you can say parent of this 10 so after this right rotation the tree would be see here 13 is to the right of this 10 so it would go to the right of 10 but left of now 14 this also we have already discussed in the previous video that how to do left rotation and right rotation means how to write down the steps right now this is the tree right after deletion of twin right now I will delete 14 now find out where is 14 greater than 10 so here you go to this 14 now see the 14 is having both left and right child now this is internal node so you cannot simply delete it we cannot delete internal node in BST we can delete only leaf nodes right now we can replace this node now with which child you are going to replace it because it is having both left and right child so two approaches are there either you can select in order predecessor or inorder successor it's up to you now I am selecting suppose inorder successor now what inorder successor of 14 is what in the right subtree find out the smallest element right now in the right subtree of this 14 smallest element is what 15 right see I have already discussed BST insertion and deletion in detail so you can check out that video in the cyber 10 now we are going to replace this 14 with this 15 so suppose I am replacing here 15 right now here we go to 15 this and this so now we are going to delete this one we are going to call recursively the date function on this inorder successor right now this is what leaf node so you can simply delete it now this is not yet done now we are going to performs playing operation now splaying on which element on which node C before deletion here we had 14 parent of the node you want to delete this this one right so we will do is playing on the parent of the node you want to believe now parent is this one now see parent is already root node so now you no need to do any splain fine because in splaying we will we are going to make that node the root of the tree and this is already the root of the tree so you no need to do any splaying now this is done right now we will delete 16 now find out where is 16 greater than 10 greater than 50 now here we go to 16 we cannot delete it because it is internal node now it is having one child only so simply you can replace the 16 with 70 its children now you can delete this yes we can delete because this is the leaf node so we can delete it now on which node you are going to performs playing operation before deletion the node 16 was here parent of this is 15 so we will delete sorry we will perform splay operation on this 50 now we are going to make this 15 as the root of the tree now find out which rotation you require 15 the parent of 15 is root node so it is only Zig situation is there which rotation you need now 15 is right child of 10 so we will do left rotation left rotation right or you can say the zeg rotation so now after this left rotation the tree something like this now ten would go downward 15 would go upward right now see here to the left of this 15 we have 13 so to the left of 15 now the 13 would go left of 15 and right of this 10 here we got 13 now you can see 15 is now the root node now suppose you want to delete 20 now search where is 20 in this tree greater than 15 greater than 17 but we don't have any child of this 17 we have raised to none it means we don't have this 20 in the string right now you will do splain you will dos playing in this that is for sure but on which element you will lose playing operation now see this before reaching to the null node because here we have null 20 is greater than 17 but here we have null so the last exists note null node is 17 right so you need to display 117 now it's not like that the data is not present so simply you just leave it like this no after searching if the data is not present then splay on the node which is last not null node lastly access should not null node before reaching to the null node fine now you will lose playing 117 now 17 is what root of 17 is sorry the parent of 17 is root only so this is Zig situation now the 17 is to the right of 15 so we will do left rotation right so this is what is a rotation or here you can say this is zag rotation as well fine now the 17 would go upward so the tree would be something like this so now suppose you want to be it 17 now see where is 17 the root of the tree is 17 so now is there any parent of this root no parent of root is there so we cannot do any splaying or you can simply delete it means we are going to replace it it is hanging left child's for left child is 15 now 15 would become the new root and no need to do any spring because this root is the node you want to delete is not having any parent right so basically two steps in this deletion first is perform standard BST deletion second is you display the tree on the element which is parent of the node you you have deleted right so two steps are there now I have already deleted I have already discussed the algorithm force playing in the previous video right how to write down the algorithm now simply be a state volition algorithm is what that thing will I will discuss in the separate video algorithm for BST insertion as well as deletion right so now see this is what a bottom-up approach or you can say bottom-up splaying deletion in splay trees can be performed in two ways first s that is top-down playing you can say or next one is bottom-up right so maybe this is what a bottom-up splaying fine in the next video we will discuss how to do deletion in splay tree by following that top-down splaying approach right now you can in the question you you can be asked like this they'll give you a tree and they'll ask you to delete a key and they'll say you that the splay tree is what a bottom-up tree it is having bottom-up approach so you need to follow this approach if they ask you to follow the top-down approach means in that case you have to split the tree in two sub trees and after that after deleting the particular node you how you want to delete after that you can merge those trees right first of all then the key you want to delete you have to make that he has the root of the tree after that once you delete the root of that tree then the tree would be splitted into two trees one is left sub tree one is right sub tree that thing we'll discuss in the next video with the help of an example so this is all about deletion in splay please following this bottom-up splaying approach right and I'll see you now in the next video till then bye bye take care