5.18 Red Black Tree deletion | Data structure

so the topic is deletion in red-black trees see we have already discussed introduction to red-black tree as well as insertion in red-black trees so first of all go through that video that what is red-black tree if you know what is red-black trees then it would be easy for you to get this topic that is how to perform deletion in red-black tree as well as how to perform insertion right what is red-black tree it is a binary search tree or you can say it is a self-balancing binary search tree with some extra properties what are those properties root would be black second property was one there should not be any two adjacent red nodes means if parent is red then its children should be black third property was what that in each path from any node to its descendant nil node there should be same number of black nodes these three are important properties of red black tree right now how to perform deletion in red black tree see in case of insertion what we have done we simply follow the rules of binary search tree insertion right and if tree is empty then we create a black node and we will simply insert that node in the tree if tree is not empty then what you will do we always create a node in red color and we will insert as a leaf node then in that case which property is going to be violated that red red conflict property but if because if parent is red and always we will insert a node in red color then parent and child would be red but this should not be a case in that black tree right so for solving for resolving that conflict we need to do some rotations or 3-coloring fine now here in relation out of these three important properties of red black tree which property is going to be violated right see if you are going to delete a red node then there would not be any problem just to delete that node and exit right but if you delete a black node in that case which property is going to be violated that the number of black node in each path from any node to its descendant nil node would be same should be seen that property would be violated if you delete a black node because if you delete a black node then in that path the number of black node would be less than the other paths then you need to take care of that property so first resolving that issue you need to do some rotations maybe some recoloring as well many cases are there we will see all the cases simplest cases what if you want to delete the red node simply delete it no need to do anything but if you want to delete a node and that node is black node in that case you need to do something now in deletion the very first step is what you have to perform just standard a binary search tree deletion right now how to delete see I have already discussed insertion and deletion in binary search tree you can check out that video in the cybertor right suppose I am taking this is a binary search tree and here you want to delete this to L first of all we need to search 12 where is 2 L industry we have the address of the root node we are going to start from here 2 L is greater than 10 so we know that 2 L would be here in the right subtree of this and no need to check the left subtree right now again 15 mins 2 L is less than 15 so just go left so here you find to it right now if the node you want to delete is having no children I am just considering I'm just taking okay so binary search tree I'm not taking red black tree here all right so simply delete it no need to do anything right now second case was if the node you want to believe is having only one child suppose I want to delete this 7 first of all search this 7 right compare with this 10 less than 10 so we are going to to the left of the strength now here you got 7 of 7 is having only one child no problem what you will do see now see seven is what an internal node so one thing you need to take care when you are going to perform deletion in binary search tree all in red black tree we do not delete internal nodes right we always delete leaf nodes now seven is what internal nodes so you are not going to delete this node you are going to replace it now you are going to replace it with its child because it is having only one child so here you put nine now here we have nine and nine two lines are there now recursively you are going to call the delete function on this child and now we are going to delete this child all right so after deletion this is the binary search tree internal nodes we are not going to delete only we will delete the leaf nodes internal nodes is going to be replaced with its children right with which shall Charlie you need to take care of that thing now third case was if suppose I want to delete suppose this ten now n is having two children now we are we will replace this ten with which children with nine or fifteen or with what this thing you need to take care now here two cases are there either you can replace it with its inorder predecessor or inorder successor two cases are there so these two approaches are there suppose I'm replacing the stand with its inorder predecessor predecessor means in order predecessor means the largest element from the left subtree of that node because i am i want to replace this 10 so find out the left subtree of this 10 and from that left subtree the largest element would be the inorder predecessor means here we have only one element that is nine so you can replace this with nine or if you follow this approach if you will follow this approach then you are going to replace this 10 with its inorder successor now how to find inorder successor the smallest element from the right subtree of that node right I want to replace this 10 or you can say I want to delete this so the right sub-tree of this 10 is this one now the smallest element from the right subtrees 2n so we are going to replace this 10 with this 12 see how to find this in order predecessor successor and how to replace that node this thing we have already discussed in detail when we were discussing the BST insertion and deletion so you can check out that video in the description box as well right now first step is in this in this deletion in red black trees would simply perform standard BST deletion right the same rules here we have discussed these rules would be followed after that you need to take care of that property that is that red black property of the string so now we will see all the cases one by one with the help of example and at last you will also discuss that we will take example of one red black tree and we will apply the deletion operation and we will discuss all the cases in one example right now first step is simply perform BST deletion so you should know how to perform BST deletion right suppose I am taking this as a red black tree now you can see this is a red black tree because this is a binary search tree first of all root is black know red red conflict is there and height you can say that from any node the path every path from the node to its descendent nil is having same number of black nodes right now here the case one is what if the node you want to believe is a red in that case just delete it this is the simplest case and deletion right so suppose here I want to delete 30 now first step is you need to search where is 30 means binary search you need to apply here compared with this root because I am having the address of the root node only right 30 is greater than 10 go to the right side that is greater than 20 go to the right side here we got 30 right and this node is ha this is what leaf node or here somewhere it is also written that because obviously we are we are having here null null here also null null and null or you can say nil and all the nil nodes are having color black right now if you want to delete this 30 and it is humming only nil children know not knowledge children is there so now and the red is the color is red so simply delete it right and if you delete it so here somewhere it is also written that when you delete it then simply replace it with this either of its nil children so here you can write nil and this is also in black in color so you can see it is still a red black tree right root is black in every path see here you can say here we have one in two black node 1 in 2 here also 1 & 2 & 1 & 2 somewhere they count that one two and three this nil also has a black node but here I'm not counting this thing or some somewhere it is counted that they don't count this root in the path because this is always black so they count this 1 1 & 2 1 & 2 1 & 2 & 1 & 2 it's up to you have you you are going to count but the logic would be correct right so now the node was red we simply deleted it no need to do anything now here I am writing simply like this I'm not writing the null nodes because these are null node so no need to write down those notes right now second case is now suppose here I want to delete 20 now search where is 20 greater than 10 so here I got 20 but 20 is what is having one child so it is internal node so you cannot delete this 20 internal we cannot delete internal nodes we can replace those nodes so now with which node you are going to replace this 20 because it is having only one child so just follow the rules of BST deletion we are going to replace this 20 where this 30 now Here I am writing 30 now 30 is read but here I am not recoloring it this is still black why so because here we are not going to believe this node and if you will not delete this node then this node still having its color black we are just replacing the value now rather than 20 here we have replaced to this 30 we are not deleting this node so that is why internal node will always preserve its color its retain its color if it is black it would be black if it is red internal node is red it would be red because the common sense is what if you don't delete any node then obviously the color of that node would be same now right so we are just replacing this we are putting this 30 here now we have 230 here now apply that delete function on its inorder successor or you can see on the children all right so now delete this one this is red so if the node to be deleted is red this is leaf node now so we can simply delete it right we can delete leaf node we cannot delete internal nodes so simply delete it I am NOT replacing this with rights nil children or you can do it something like this here nil nil nil and name so here what you can write if the node to be deleted it is rather than just deleted and if the node you want to believe is black with one child in color red then simply replace that node with its child right and delete that child because child is red so simply you can delete that and that node would be having its own color because we are not going to change this its color right now let us take few more example of this case so here in this example I want to delete suppose 30 now search where is 30 start from the root 30 is greater than 10 so to the right of this root now here I go to 30 but this is what internal node here you can see this is having left and right both the child so the case is what either you can select in order predecessor to replace this or inorder successor here i am following the approach where i am going to select inorder successor right now see this 30 is internal node so we cannot delete you can only replace it we will delete the DF node this point is very important you need to take care of this point so now that inorder successor would be what the smallest element from the right subtree of that node because I want to delete this 30 so the right subtree of this node is this one smallest element is 38 so we will replace this way this 38 means rather than 30 here you will write 38 but the color would be same see it is internal node you are not going to delete the node that is why the color would be as a tease if 30 it's not like that if 38 is black or it's red then you are going to take the color of 38 only know the internal node will having its own color so we are not going to change its color that would be red only now that on that inorder successor now you are going to call recursively that delete function here now can you delete this 38 yes obviously it is the leaf node and it is red so simply delete it you not no need to do anything so you can simply delete it right or you can say here we will replace the 30th with it's nil children so nearly black each node is humming male children right as you can see this is still a red black tree no red it conflicted is there in each path we are having same number of black nodes and do this black right let us take another example now let us take this example here also see this is a red black tree you can check out all the properties now here also I want to believe this 30 first of all search where is 30 it is greater than 10 so here I got 30 now it is having two children now I will replace it with its inorder successor you know the successor is what from the right subtree of this 30 find out the smallest element smallest element from this is what 35 right so now here you will write 35 35 right and it will it is black so it is going to contain its own color right because it is internal node we will not delete internal own now the problem is we have 235 now on that inorder successor called the delete function recursively not now you want to believe this one right but this is still having one child so we will not believe this we will replace this so here we will write 38 and it will contain its own color right it's not like that 38 is red so we are going to make it red no it is internal node will not delete this so it is having its own color now 38 38 now again recursively call or delete function on this 38 now it is red so simply deleted right so as you can see this is still a red black tree right so not the problem comes when you will delete a black node and that black node is having black children right so there for double black situation will arise and the main task here is what you need to convert that double black into single black and for that you need to have some cases so we'll discuss all the cases with the help of example now now suppose here I want to delete this 20 right first of all search where is 20 to the right of this 10 it is having two children so which with which children you are going to replace it with inorder successor from the right subtree find out the minimum element in the right subtree we have only 30 so we are going to replace it with 30 right and we are not deleting this one so we are just replacing it so it will contain its own color right we're not going to affect this color now again called lead function on its inorder successor now if you delete this 30 obviously this leaf node so you can delete it but here the situation is what it is black it is not red so it's not like that you simply delete it no why so they can see this is having nil nil all are having it's nil children and these nil are black so by default if this is red what we have done we simply replace it with its nail children but here this is black you want to delete this node this is black and you will replace it with it's nil children and the nil children is also black so now this is situation of double black so if you delete and you will replace it with its nil so it's own color was black and the children color is also black so it is now double black this is the case now what you can say it is now DB double black note you need to take care of this node now this is the main problem in deletion in red block right now you need to convert it into single block Y so see now check out in each path here we have two black node here also we have two black nodes but here we have only one black node because we obviously we are not going to count this nil node so you will not count this nel node so in this path from here to this nil node we have only one black node so the main property which is violated here is what because of the listeners of black node in this path we have one less black node so it has it has affected the black height no you need to take care of this thing now so here we have multiple cases right now see first case is simple if the root is double black so simply remove double black right suppose because of some situations you got double black at the root right this is root this is double black and here we have left subtree and here we are right subtree right no need to do anything simply remove this double black and make it single duck right this situation will discuss with the help of example this is the simplest case in this scenario right next situation is what now if the node is double black right so to resolve this conflict we will always check its sibling right see in case of insertion we have checked the uncle of that node right I guess you remember or you can say that parents sibling according to that we decided which rotation or which case we need to follow but here when we will check the sibling of that double black note and according to that we will decide which case you are going to apply right now first case in this key in this is what if the double black nodes sibling is black and both its children are also black so let us take that example so now let us take this example here in this example this is a red black tree and here I want to believe this from here I want to delete 15 right so search where is 15 to the right of the stain to the left of this 20 here we were 15 now see we cannot simply delete this 15 it is a leaf node and you cannot delete it like this because it is having color black if it is red then you can delete it it is having two nil children which are also black this is also having nil nil in the land name now if you will delete this one then you will replace this with its children one of its children that is nil and this is black and the children color is also black so this is now you can say double black DB right I'm not showing these Nell children so now in this path from here to here because obviously we are not going to count the snell while we are counting the black node in the path so it is having only one black node here we have one into here we have one and two so now we need to solve this problem now to solve this problem this double black node will always check its sibling sibling is 30 check the color of sibling it is black right and sibling children are two nil and nil and color of nil children is also black as we know right so now BB's sibling is black and both its children are black so this is the situation now now what does DB will do see here you can relate it with this example that red means if someone is angry then his face becomes you know red so 20 is angry if someone is cool then he is black right now this is double black means this is also a problem you cannot be so much cool or come sometimes you need to be angry sometimes you need to show your anger right so this is a problem double black says question is also not good so now it will see he will see its sibling it is black cool he is cool so this the sibling doesn't need any black color now because it is already in black its children is also black so now all the three are black so he cannot give its extra black to either of these three nodes neither to its sibling no to its children now what he will do he will ask to its parent right and obviously he will give its extra black or you can say that its problem to its parent right so now here first of all remove this BB so it is simply single black now and add black woods parent so now parent is red so parent becomes black right now what you will do when it's sibling come to know that he has given his problem to parent then what the sibling becomes angry right that why you are giving you why you are troubling our parent fine so now it will become red now the steps are what if this is a situation then what we have done simply remove this BB first of all and what we have done done add black to its parent and black boots this was double black node to its parent right now here also pool situations can be there if the parent is already black then it will become double black and if the parent is red then it will become single black here the parent was red so here also two situations are there if the other than parent I'm writing P P is red now next thing what we have done the sibling becomes now red so now next step is what make sibling red sibling means sibling of double black node because double black node is having problem number are discussing the cases on this double black so sibling means double black sibling becomes now red right now if still the problem of double black exists then we will apply some other cases right so now and what are these other cases that thing also we will discuss one by one right now here see there is no double black problem exist now right so now it is done so we can remove the snow this is also nil so you can remove it so now as you can see this is a red black tree rudest root is black in this path one and two blacks one in two blacks one in two here also one and two and one and two right now if the parent was red sorry the parent is black so it would become double black and here still the double double black situation is there so we will apply some other cases right that him also will discuss I hope you go to these points so now here let us discuss this case that parent is already black so it will become divided black see let us take this case this is a red black tree perfect by new trees there and all the nodes are black so this is a red black tree now delete here 15 see 15 is black so you cannot simply delete it because it is having two nil children those are black so we will replace this 15 with it's nil children so Nell is also black and this is already black so it will become double black so now here this is Nell and it will become now you can say double black so here the situation is there the problem is there because see in this path we have only one end to black notes and all the other parts are having three black notes right because this is nil we are not going to count it so now we need to take care of this thing so now apply the cases check out the double black sibling sibling is black the two children of sibling is also black so this is the case right now here what you will do simple first step is remove dB remove double black so it is now single black right and it is now give its black extra black to its parent right same you can discuss that see this is what black means cool red means angry so now this is what a double cool so that is also a problem he'll ask to its sibling but sibling is cool he doesn't know need any black node or you can say no more coolness he needs children is also black so they don't need any extra black so what it will do it will ask to it's obviously parent right because if children is in problem so he'll go to it he'll go to his parent right so now he'll go to his parent and give its extra black or give its problem to its parent so now parent becomes double black why so because parent is already black so it means it becomes double black and it becomes now single black now sibling becomes red sibling becomes angry why so because he'll say why you are giving your own problem to our parent why you are troubling your parent so now it becomes red sibling becomes angry makes sibling red now here still DB exists in this case right so you need to follow some other case now which case you need to apply here see this is the node which is having problem so he'll check its sibling sibling is black children both children are black so he they they don't need any extra black because they are already cool so now what he'll ask to its parents means he will give its problem to parent right so parent is already black so now you can say first of all remove this DB it has become now single black and parent becomes now double black because parent is already black now after doing this now sibling becomes angry why so because he'll say why you are giving your own problem to our parent right so now it will become red from black to red now the situation see now here still inner problem we have double black situation now which case is there identify the cases now see double black is what root root is double black this is root so simply remove double black no need to do anything so simply remove it and it will become single black right and that's it so you can see this is water red black tree you can count the black nodes 1 & 2 1 & 2 here also 1 & 2 and here also 1 & 2 because this is nil so we will simply delete it so here also 1 & 2 right now check out the next case so now let us take this case and here this is a red black tree and from here I want to believe this 15 right now such where is 15 here you got 15 but you cannot simply delete it because this is black so now after deleting this 15 it will become because obviously it is having Nell children we will replace this with this nil and it will become now double black because it is already black and its children is also black with which you are going to replace it so it will double black now now find out which case you need to apply to find out the cases simply check the sibling of double black right check the sibling of double black after that after that you will check the this children of the sibling right the children which is away from double black and after that you will check this children these cases also we will discuss now we have already discussed this case when sibling and its children were black now second case is now here the sibling of double black is ready so this case is their right here we have discussed two sub cases right now this is red now what you will do see it means the sibling of double black is angry so now he wants his sibling to come down right now he cannot directly go to his sibling mean generally suppose two brothers are there so if one is angry so second brother will go to his parent and ask his parent to for his brother come down right now he lasts to its parent and he will send his parent to his brother to come down his brother right or you can say is sibling now when the parent will go and tell him to come down then it will become black right but in that process the parent will become angry so parent will become red because generally it happens when you are angry and your parent comes to calm you down to pull you down then they will become angry and then after that you will be like silent so now we are going to swap the colors now the the sibling becomes red to black but parents become from black to red first step is this one right but still the problems is their BB problem is their double black problem is there now second step is what the parent will rotate in the double black node direction right second step is this one so now after rotation the parent will rotate towards this direction because this children of parent is having problem this child is having problem so parent will go will always rotate towards the the child who is having problem right so now this rotation you can say the left rotation or you can say in the direction of BB the parent will rotate now after rotation the tree would become after rotation 20 would be down third we'll go up 30 is black 30 is having right child does 40 and now 30 is up 20 is down so 20 is to the left of this one and here we have to the left of 20 we have null that is double black 20 is what red now where 25 will go 25 is to the left of 30 and to the right of 20 right this is black this is black and this is black and this would be same this side would be same right now still after rotation still we have double black problem so now you need to again check which case you need to apply right so now this case in this case steps would be what first of all what we have done we have swapped color of its sibling and parent right so now here you can write swap colors of parent or you can say double black parent of double black right and it's sibling properly you can write this thing so parent and it's sibling right after swapping the colors we have done rotations rotations in this direction in DB direction right see this case is having its mirror image if bb's in this direction in that case this will rotate in this direction that thing also we will discuss right that is why I am saying that rotate the parent towards bv direction see here parent parent off you can write down properly parent of double black node in double black node direction right I am writing it in short cut and again reapply cases right now this is the scenario here which case you need to apply check out still we have double black situation now check out the to find out which case we need to apply check out the sibling of double black sibling is black now check out the children children is also nil and male that is black and black so this case you need to apply now write what is this case simply remove DB here we have means one black oniy right and add black to its parent so he'll give its problem to its parent the parent is red so it becomes black right this is the case parent is red it becomes black and after that sibling makes sibling red so now sibling becomes angry that why you are giving your problem to our parent so sibling becomes angry now now if still DB exists but in this case there is no DB problem exists now this is the final tree after deleting this 15 and as you can say this is now a red black tree from here this is null so you can delete it now what can be the next case so now we'll discuss the case 5 let us take this example right this is a red black tree and from here I want to delete this one in one example I'm I want to discuss more than this one case two or three cases I'll discuss now see if you delete this one right first of all search where is one this is black so we will replace it with its null null node and it will become double black now right so here we have the problem now find out which case you need to apply to find out this thing just check the sibling of double black sibling is what black now children of the sibling say this is also black this is also black because these are new so now this case you will apply first of all right so now he'll give its problem to its parent so now remove this double black this would become single black now null and a parent is black already black so it would become now double black right now still problem of double black exists now reapply cases now find out which case you need to apply now this is the node which is having problem now check out the sibling of this node that is 30 which is black right now check out this node sorry this children of sibling see it is having two children which children is near to this double black node this one and which is are from this this one so first you will check sibling this is black now the child who is far from double black this situation siblings child who is far from double black this child is far from double black this is near so this is black right and the child which is near to double black is red and there but the near child of double black is red now this is the case now here what you need to do see here I'm not writing left child or right cell because all the case in this case or all the cases are having its mirror image right so if you write down the left and right child then that would create a problem in mirror image so that thing also I will discuss the mirror image of this thing fine now see the siblings child is red means he's angry right now this double black node will ask to its sibling to go to his child and cool him down right so now the parent will go to its children and cool him down but in this process the parent would become angry so you can say we will swap the color of sibling and its child so now this becomes black means cool down and this would become angry right this is the first step now rotation in this case also rotation would be required so now 30 becomes red right or you can say that he becomes angry and why he becomes angry because of because his sibling 30 sibling is 5 because his sibling ask him to go to his hot chill to his child and cool him down that is why he becomes angry so you can say he becomes angry with its sibling that is why 30 would rotate in opposite direction to its sibling right not in this direction opposite direction to its sibling now the tree would be something like this so now when you will rotate this 30 in this right direction and 30 would be downward and 25 would go up so 25 has here now having color black 30 is to the right of 25 if not as 30 is having color red here we have 40 and through the left of 25 we have 20 with color black and to the right of 25 they are 28 to the right of 25 and to that now to the left of 30 that is here we are 20 and that is an black color now still we have problem of double deluxe situation now again you need to find out which case you need to apply right and after case 5 definitely you need to apply case 6 that is for sure right here we have applied case 5 first of all we applied case 3 then we apply case 5 and now you need to apply case 6 now what is case 6 see first of all write down the steps of this case I'm writing the steps here because see this step is very simple and this is very simple because if node is deleted you want to read it as read simply delete it so I'm writing the steps of this case here first of all what we have done we simply swap color off see this one and this one right means color of DB's sibling when it's child who is near to dB now after swapping the colors what we have done we have rotate the sibling of this BB in opposite direction to D be not in the direction of DB so now and now still the double black problem exists and definitely you need to apply case 6 so here you can write down apply case 6 right now what is is 6 C so now I will discuss case 6 after applying case 5 this should become this thing I guess this would be red right because when you will this double black this node will give its extra black book parent then the sibling becomes angry or you can say it becomes red now this is nel so you can delete it so now this is the tree now here what is case six now we'll discuss see this is not having double black situation now check out the sibling of double black this is black now this is having two children so first of all you will check the child who is far from double black say this is far from double black this is near to double so now this far child is red now now Moe need to check this child right if you find this is red now you have to do something now you can say this siblings the for child or you can say this child is angry so now he'll not directly go to his sibling and ask to cool his children down if the this this was this case this was the case if this chil the near the near children was red then he will ask to its sibling to go to his child and cool him down right now this is the far child so he'll ask to its parent to go and calm down his children right now if the parent will go in that case we will swap the parent and siblings colors here both are having black and black so swapping does not affect anything now if situation is something like this if this is red and this is obviously black in that case this will become black this would become red but here this is not the case both are black so no swapping would be there right now again next step is what now he'll rotate towards DB direction because in this case 10 then is the one who went to cool him down right so this would rotate in this case 30 rotated why so because 30 went to cool his children down that is why he will rotate and he was sibling of double black that is why rotate in opposite direction right and it is parent of double black so parent always rotate towards the child which is having problem right so now this is having problem so he will rotate towards this direction right now after rotation the tree would become ten would rotate it towards this direction 25 would go upward 25 is black now here we have 30 40 28 20 is to the left of 25 but to the left of 25 when you will rotate this tree so now here we have 10 so now 20 would be to the right of 10 and 5 is still having the problem of double black and here we have 7 that is red and this is black this is black black 30 is red sorry this was black and this is black now next step is what this remove this double black why so because see this double black node can push his double black problem upwards not downwards now the problem was the fire child was red so he will give its extra black to 30 so the 30 would become now black and this would become single black and that's it now you can see this is a red black tree right after applying a 6 so now these are all the cases and these cases are having its mirror image also like this here the DB is in this direction but suppose DB is in this direction and this direction and we have sibling of this DB right so now the far child of DB would be this one and the near child will be this one right so you need to take care of this thing also but apply the same rules in mirror image also right so now we will take one example and we will discuss the deletion process in red black tree now let us take this example one by when we are going to delete these numbers so this is a red black tree as you can see now first of all delete 55 search where is 55 from the root 55 is greater than this one less than this one so here we go to 55 right you cannot directly delete it because this is black node right and children obviously nil and nil those are also black so if you will delete this thing so we will replace this with nail and black so that is why it will become double black because this was already black now the problem is there now you have to convert it into single black now apply find out which case you need to apply to find out this thing simply you need to do you need to check out the sibling of double black sibling is red it means this case for you need to apply it means sibling is angry right so now he can see he can give its extra black to its sibling but right now cannot give because these are at same level and it can push its problem to upwards only right not downwards and not at the same level right so now he'll ask to its parent to go and cool his brother or it's his sibling down right so now parent will go so that is why the parent now become red and now it becomes black because during this process parent become angry and that child who was angry becomes cool down now now parent is angry so now parent will rotate in which direction parent will always rotate in the direction the child in the direction of the child who is having problem and now this child is having problem right so parent will rotate in this direction so 65 would go downward 70 would go upward right so now that tree would be something like this so now this is the tree after applying case for still we have DB problem see we have done swapping of parent color of the parent and its sibling rotate parent in baby's direction now you have to reapply cases now again check which case you can apply so now in this case now DB is this one this node is having DB problem so first of all check the sibling sibling is black now check the the child who is far from this TV that is nil that is black and this is also nil that is black so now you will apply case 3 this is black this is black this is black right so now he cannot give its extra black to any of these so now what he'll push his problem upwards he'll push the extra black boots parent of this week right so now the parent is red see 65 is red so now this parent becomes black and this would become single black and this is null that is why you can delete it means we will not write this thing right we have solved the problem now one more step one more step is what now this children has given its problem to parent now after looking this one the sibling becomes angry he will say why you are giving your problem to our parent right so now this was black so it would become now red right so now this is the tree because here now we don't have any double black problem so after deleting this 55 this as the final red loctite so now next you delete 30 so suppose this is no 20 this is 30 so now we need to delete this one first of all find out where is 30 less than 50 so here we got 30 now 30 is having two children so we will replace it with inorder successor you know the successor is 35 because in the right subtree only one node is there that is 35 so we will replace this 30 with this 35 right and if you are going to replace it we are not going to believe the internal node that is why it will having its own color that is black only now 35 35 to 35 are there so now we recursively hold delete on this inorder successor right so we can not directly delete it because it is already black so now we will replace it with nil and it would become now double black right now the problem occurs now which case you need to apply see now check the siblings of double block now sibling of double black is this one so this is black it's first of all check the fire child this would be nil that is black near child this is also black now again you will apply here this one case 3 now in case 3 what does the situation see now this double black will push it's problem upward you can say to its parent because these are all black no red is there right sibling and it's children so now he'll give extra black to its parents so now it 35 could become double black right some I'm I'm updating here only now this is 35 so this would become double black because this was already black and one extra black he has given to its parent so it would become double black now it would become single black that as null so if it is null so you can no need to write down the nun now after seeing this the sibling of double black would become angry that why you are giving your problem to our parent so that is why it will become red right now still the problem occurs now double black problem is here now again check out which case we need to apply now check out the sibling of this one sibling is black right now check out the far child from this double black this is also black now check out the near child this is also black now again you will apply this case only right now it will give its extra black to its parent right now the parent would become double black now 50 would become double black and it will become single block that is 35 only after seeing this the sibling of double black was this one this would become angry so it would become black to red now the double black situation still exists but here the double black is the root is double black so in that case you will do what simply remove the padlock right so simply remove it double black and 50 is become single black now so now this is the tree after deleting 30 so this as you can see it's a red black tree now from here delete 90 where is 90 here we have 90 see now the node of you want to delete is a red so you can simply delete it no need to do anything right because this is red and if you will replace it with nil then that would be a single black only no double black situation is there no need to write down so you can directly delete this 90 right now next we want to delete 80 from here now you will see the mirror image of the case we have discussed earlier see if you want to believe but this is already black node so you cannot simply delete it right we will replace it with its nil and it would become now double black now here the problem exists now you need to convert it into single black right now check out the sibling of double black that is 65 is the sibling sibling is black in color right after that check out the child of the sibling which is far from double black so this child is far from double black and this is nil and this is black only nil is always black right now check out the child which is near to the double black this is red now now which case you need to apply see this one now these are the steps now what you will do see now he will ask to its sibling that go to your child and cool him down because he is angry right so now he'll go to a chilled to a child and cool him down that is why it become now black but now he become red right now he was the one who went to cooled his children to cool his child down that is why he will rotate now so now he will rotate because he was the one who went to cool him to cool his child down so that is why he will rotate now he will rotate in opposite direction to DB why so because he asked to go him to a child and pull him down that is why he becomes angry now he is angry with his sibling also so now he will rotate in opposite direction to this DB so now the child so now the tree would become now it will rotate in opposite direction who 68 would go upward and 65-foot go downward now 65 is red and 68 is black and this is still a double black problem right and say these red now see applied k-6 because once you apply case five definitely you will reach to a situation where you need to apply case six now k-6 is what this is the problem node having problem DB problem so check out the sibling that is black now check out the child which is far from DB which is red for our child is red so that is why we breach to case six ultimately now applies case six now what you will do now see he lost to parent his parent to go and come his child down right now he will not directly ask to sibling to go to its children he lost to paint because this child is far from DB right now parent will go right so that is why we are going to swap the color of parent and its sibling so now see parent is red so it will become black and it is black so it will become red right after swapping colour of parent and sibling rotate now he was the one who went to calm his children down right so now that is why he will rotate now so now his parent of double black and parent will always rotate in the direction of DB right because this child is having problem so parent will need to rotate in the direction of the children which is having problem right so now after rotation three would be something like this 70 would go downward 68 would go upwards 68 is now red now after rotation remove DB so DB is this one so remove this thing this would become only null that is one black and change the color of red child see the red child was this one because because of the sixty five was red right so sixty five the fire child was red so it would become now black so 65 now becomes black see now it will push its problem upward right so 65 is one level up up from this so he can give one extra black to 65 now right so now only null so you can remove it no need to write it down so now this is the tree as you can see this is now a red black tree after deleting what 80 now we will delete 50 50 is having to child so we will replace it with its inorder successor you know the successor is what from the right subtree find out the smallest smallest is 65 so here you will write 65 you are not deleting this we are replacing the value only so it would become it would remain it would you know retain its color right that is black now 265 are there so we will call recursively the delete function on this inorder successor so we will delete this one but this is black so you cannot directly delete it so it would become now double black right so now which case you need to apply sibling check out the sibling which is black check out the fart child of sibling that is nel that is black left child that does Anil that is also black now which case you need to apply case 3 in this case he will push its problem or you can say it's extra black boots parent right now parent is red so it would become now black right and it would become single black now after seeing this one the sibling becomes angry or you can say becomes red that why you are giving your problem to a parent right so now this is null or single black so you can delete it no need to write down the null so now this is that we after deleting 50 now next I want to delete 35 see where is 35 less than 65 here we have 35 right 35 is having one child that is red child so simply first of all we will replace this 35 whether it's child that is 15 but the color would be saying that is black because we are not going to believe the node we are just replacing the value right now we need to delete this 15 right so now 15 is red so you can simply delete it no need to do anything so this is now a red black tree right now next digit 15 here we have 15 15 is black and it is having two nil child the are also black so you cannot directly delete it right so we will replace it with null and it would become not double black now check which case when you to apply double black sibling is black check out the fart child for child of double black is red now the situation is this one sorry situation is this one case six directly you need to apply case six now right now what you need to do so now he'll ask to its parent to go and ask you can say his sibling to pull his child down he will not directly ask to its sibling in this case if the cases for child is red if near child is red then he will directly ask to sibling to go and pull his child down right now if parent will go then parent and we will swap the color of parent and this sibling but both are black so no need to do any swapping right now after this after swapping this parent will rotate in which direction towards DB direction so now the situation would be sixty five would be rotated towards this 68 would go upward sixty it is black here we have 70 which is red 65 is black and here we have now double black right now now see this this child was red he was angry right the far child 70 so now the 70 is one level upwards to double black so now if he can give its extra black to this 70 spoon of 70 becomes black and it would become single black so you can remove it no need to write down this thing so this is the tree after deleting 15 so this is now you can see a red black tree so now suppose if you delete 65 I want to believe 65 see where is 65 here we have but this is black you cannot directly delete it right so after deleting this this would become would be replaced by a null so it would become now double bla now check out which case you need to apply check out the sibling which is black the first child is also black the near child is also black because both are not so which case we need to apply this thing now he will push its problem to its parent that is the extra black he will give to its parent now parent is already black so it would become double black right and now it would become single black right so that's this is null so no need to write down this thing now after seeing this situation that the sibling becomes red sibling becomes angry now still double black problem exists in our tree so now double black root is now double black so simply remove it no need to do anything simply remove double black now suppose if you delete 68 in that case what you will do 68 is having only one child so first of all you will replace this with its child that is 70 and we will simply replace it the change the color would be same internal node will be retain its own color right now we delete this one so this is red so you can simply delete it right so this is how we are going to perform delete operation in red black tree I hope I have discussed all the cases with the help of an example if you have any problem then you can write me down in the coming box right so now I will see in the next video till then bye bye take

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

Views: 148,231

Rating: 4.8860946 out of 5

Keywords: data structure tutorials, operating system, data structure and algorithms, what is red black tree in data structure, red black tree insertion and deletion, red black tree in data structure, tree in data structure, ugc net computer science coaching, gate cs lectures, gate computer science lectures, jenny data structures, jennys lecture, jennys' lecture cs/it NET&JRF, cs it youtube channels, data structure notes, what is binary serach tree, bst insertion and deletion

Id: w5cvkTXY0vQ

Length: 63min 5sec (3785 seconds)

Published: Sat Nov 09 2019