{"id":378,"date":"2018-07-19T06:41:01","date_gmt":"2018-07-19T06:41:01","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=378"},"modified":"2018-12-12T10:42:18","modified_gmt":"2018-12-12T10:42:18","slug":"red-black-trees-ii","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/red-black-trees-ii\/","title":{"rendered":"Red Black Trees -II"},"content":{"raw":"
\r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of Red Black tree and insertion into them. In this module we will discuss deletion from Red-Black Trees.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022 To understand the concept of deletion from Red Black Trees\r\n\r\n\u2022 To discuss the properties of Red Black Trees that are affected by Deletion\r\n\r\n\u2022 To explain the deletion from Red Black Trees\r\n\r\n \r\n\r\n26.1 Deletion from Red-black Trees<\/strong>\r\n\r\n \r\n

There are basically two approaches to deletion from Red-black trees. The bottom-up approach is recursive where the BST deletion is carried out going down the tree (winding up the recursion) and the RB(Red-black) properties violated as a result of the deletion is fixed while coming back up the tree (unwinding the recursion). The other approach is the iterative top down approach where the tree is restructured on the way down itself and hence we do not need to go up the tree for fixing the violated RB properties. In this module we will be discussing the bottom-up approach in detail.<\/p>\r\n \r\n\r\n26.2 Deletion from Binary Search Trees<\/strong>\r\n\r\n \r\n

Before we discuss deletion from Red-black, let us recall the deletion of a node from a binary search tree, since Red-black trees are a type of balanced binary search trees. In the case of deletion from binary search trees, there are basically three cases. If the node to be deleted is a leaf, we can just delete it. If the node to be deleted has just one child, we replace it with that child by making the parent of the node to be deleted to point to the one child that exists. If the node to be deleted has two children, we replace the node by its in-order predecessor\/successor and then then delete the in-order predecessor\/ successor (a recursive step). We note that the deletion of the in-order predecessor\/ successor will have either no child or only one child. In other words eventually a BST deletion will be done with the node being a leaf or having just one child.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n26.3\u00a0 Bottom-up Deletion<\/strong>\r\n\r\n \r\n

As we have already discussed we will be discussing bottom \u2013 approach to Red-black tree deletion. Now let us introduce some variables, in order to later explain the deletion from Red-black Tree.<\/p>\r\n \r\n\r\n1. If deleted node U, is a leaf, think of deletion as replacing U with the NULL pointer, V.\r\n\r\n2. If U had one child, V, think of deletion as replacing U with V.\r\n\r\n \r\n\r\nWhat can go wrong?? -Which RB Property may be violated after deletion?\r\n

    \r\n \t
  • If U is Red<\/strong>? - Not a problem \u2013 no RB properties are violated<\/li>\r\n \t
  • If U is Black<\/strong>? if U is not the root, deleting it will change the black-height<\/strong> along some path<\/strong><\/li>\r\n<\/ul>\r\n \r\n\r\n26.2.1 Concept of Red-black Deletion<\/strong>\r\n\r\n \r\n

    Now let us discuss deletion from Red-black trees. In insert operation of Red-black trees, we check color of uncle to decide the appropriate case. In delete operation of Red-black trees, we will need to check the color of sibling<\/em> to decide the appropriate case. In the case of deletion, the main violated property is, change of black height in sub-trees as deletion of a black node may cause reduced black height in one root to leaf path that is RB property 5 may be violated.<\/p>\r\n \r\n

    In order to understand deletion, we need to understand the notion of double black. When a black node is deleted and replaced by a black child, the child is marked as double black<\/em>. The main task now becomes the conversion of this node marked as double black to single black.<\/p>\r\n \r\n\r\n26.2.2 Understanding Deletion with an Example<\/strong>\r\n\r\n \r\n

    Let us assume that the node that is deleted is U. Now let us see what will be the consequence if the node U that was removed is Black.<\/strong> In other words let us see which of the 5 RB properties will be affected by this deletion.<\/p>\r\n \r\n\r\nProperty 1-Every node is either red<\/strong> or black<\/strong> \u2013<\/strong> this property is not affected by the deletion of a black node.\r\n\r\n \r\n

    Property 2 - The root is black<\/strong> \u2013 this property will be violated if the node that is deleted is the root and the child that replaces it is red. The property that every leaf (NULL) node is black<\/strong> is not affected by the deletion of a black node.<\/p>\r\n \r\n

    Property 3 &4 - If a node is red, then both its children are black \u2013 this property will be violated as the deletion of the black node could sometimes create two red nodes in a row<\/p>\r\n \r\n

    Property 5 - For each node, all paths from the node to descendant leaves contain the same number of black nodes \u2013this property may be violated as the deletion of the black node could change the black heights of some nodes.<\/p>\r\n \r\n

    26.2.3 Deletion \u2013 Case 1 and Case 2<\/strong><\/p>\r\n \r\n

    Let U be the node to be deleted and V be the child that replaces U. V is NULL when U is a leaf and color of NULL is considered as Black.<\/span><\/p>\r\n \r\n

    Case 1 : If either U or V is red that is U is black and V is red or U is red and V is black<\/strong><\/p>\r\n

    Case 2 : If Both U and V are Black<\/strong>.<\/span><\/p>\r\n \r\n

    26.2.3.1 Case 1: If either U or V is red<\/strong><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n

    Figure 26.1 shows the case where U the node to be deleted is black and V is red. 30 the parent of U is black. In this case U, the black node to be deleted is 20 and V, the red node that replaces it is 10. We mark the replaced child 10 as black. There will be no change in black height. U and V cannot be red as U is parent of V and two consecutive reds are not allowed in the original red-black tree.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n26.2.3.2 Case 2: If both U and V are Black<\/strong>.\r\n\r\n \r\n

    In this case we color V as double black. Now our task reduces to converting this double black to single black. If U is leaf, then V is NULL and color of NULL is considered as black. So the deletion of a black leaf also causes a double black. This case is shown in Figure 26.2 where U, 10 is the black node to be deleted and the V node that replaces it is NULL. Now this NULL node V becomes a Double black Node.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\n \r\n\r\n26.3 Steps of the Deletion Procedure<\/strong>\r\n\r\n \r\n

    For deletion we first carry out regular BST deletion. Let U be the node to be removed. The removed node can have at most one child. If deleted node, U is a leaf, deletion is the replacement of U with the NULL pointer, V. If U had one child, V, deletion is the replacement U with V. If the removed node U was red, no property could get violated, so we just remove it. Otherwise that is U is black remove it and call the tree-fix algorithm on U\u2019s child V (the node which replaced the position of U). If U is not the root, deleting it will change the black-height along some path.<\/p>\r\n \r\n\r\n26.4 Fixing the problem<\/strong>\r\n\r\n \r\n

    Let us assume that V is the node that has the \u201cextra\u201d unit of blackness, due to the deletion of a node U. This extra blackness must be absorbed into the tree (by a red node), or propagated up to the root and out of the tree.<\/p>\r\n \r\n\r\nLet us assume that the node that we just deleted was U. Let the node that replaces it be V and is the node with an extra unit of blackness or the double black node. Let the parent of V be P and it\u2019s sibling be S. In the explanation we give we use the notation given in Figure 26.3.\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n26.4.1 Deletion and Violation of Red-Black Properties<\/strong>\r\n\r\n \r\n

    The extra black unit is pushed up the tree until a red node is reached, when it is made black or the root node is reached or it can be removed by rotating and recoloring. If the deleted node U is red, no property is violated. If U is a leaf, no property is violated. Otherwise U is black and has a child V, and property 2, 3, and 4 (refer to properties of Red-black trees) are violated. For fixing property 2, set the color of root to black after deletion. To fix property 3 and 4, if U\u2019s Child V (the replacing node) is red, set it to black and we are finished. If V is black, fixing property 3 and 4 requires the adding of an extra unit of black to V, making it a double black node. However now property 1 is violated.<\/p>\r\n \r\n

    In order to fix property 1, we will consider if V (the doubly black node) is a left child or right child, of its parent, the color of V's sibling S is red or black and the colors of S's children. We consider x is a left child first, where we have four cases. The other four cases when V is a right child of its parent are symmetric.<\/p>\r\n \r\n

    26.4.2 Cases 1-4<\/strong><\/p>\r\n \r\n

    Remember V is the node that has is of concern here and is the node that replaces the node U that was deleted. Considering the double black node V as left child of its parent we have 4 cases as discussed below:<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n
      \r\n \t
    • Case 1 - Sibling S of V is Red<\/li>\r\n \t
    • Case 2-4 -Sibling S of V is Black<\/li>\r\n \t
    • Case 2 \u2013 S is Black & S has two Black Children<\/li>\r\n \t
    • Case 3 \u2013 S is Black & Right Child of S is Red & Left Child is either<\/li>\r\n \t
    • Case 4 \u2013 S is Black & Right Child of S is Black & Left Child is Red<\/li>\r\n<\/ul>\r\n \r\n

      Now we will see how we handle each of the cases when we use the bottom-up approach. In delete operation of Red-black trees, checking the color of sibling<\/em> is the operation which helps to decide the appropriate case.<\/p>\r\n \r\n\r\n26.4.2.1 Bottom-Up Deletion -Case 1<\/strong>\r\n\r\n \r\n\r\nThis is the case when Sibling S of V is Red<\/strong> (as shown in Figure 26.4).\r\n\r\n \r\n\r\n\u2022\u00a0 Rotate S around P (parent of V )\r\n\r\n\u2022\u00a0 Recolor S & P\r\n\r\n \r\n

      This case is not a terminal case, as after this case, one of the other cases will apply. Three cases (2-4) apply when the sibling S is black<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n\"\"\r\n

      \r\n\r\n \r\n

      The operations for case 1 when V\u2019s sibling S is Red is shown in Figure 26.5. Here we first perform a left rotate of S with P as pivot. Now S becomes the parent of P and P becomes Left Child of S. Now we recolor where S is colored black and P red.<\/p>\r\n \r\n\r\n26.4.2.2 Bottom-Up Deletion -Case 2-4<\/strong>\r\n\r\n \r\n

      This concerns three cases as discussed in section 26.4.2 \u2013 Cases 2-4 where V has<\/strong> two Black Children \u2013 Sibling S of V is Black <\/strong>(as shown in Figure 26.6). The three cases are as follows:<\/p>\r\n \r\n\r\nCase 2. S has 2 Black Children\r\n\r\nCase 3. S\u2019s Right child is Red (Left child can be either color)\r\n\r\nCase 4. S\u2019s Right child is Black and S\u2019s Left child is Red\r\n\r\n \r\n\r\n\"\"\r\n\r\nNow we will consider each of the three cases 2-4, one by one.\r\n\r\n \r\n\r\n26.4.2.2.1 Bottom-Up Deletion -Case 2<\/strong>\r\n\r\n \r\n\r\nThis is the case where V\u2019s sibling, S, is Black and<\/strong> it has<\/strong> two Black children<\/strong>\r\n\r\n \r\n\r\n(Figure26.7). The steps for fixing are as follows:\r\n\r\n \r\n\r\n\u2013\u00a0 Recolor S to be Red\r\n\r\n\u2013\u00a0 P absorbs V\u2019s extra blackness\r\n\r\n\u2022 If P is Red, we\u2019re done (it absorbed the blackness)\r\n\r\n\u2022 If P is Black, it now has extra blackness and problem has been propagated up the tree<\/span>\r\n\r\n<\/div>\r\n

      \r\n\r\n\"\"\r\n\r\n \r\n

      The operations for case 2 when V\u2019s sibling S is black and has two black children is shown in Figure 26.8. Here we first recolor S as red and make P absorb the blackness. If P was red, then the operation is complete. However if P is black, we propagate black up the tree.<\/p>\r\n \r\n\r\n \r\n\r\n\"\"\r\n

      Figure 26.9 shows an example of the above case. Here parent p (rooted at 20) is a sub-tree, u (10) is the node to be deleted and v the node that replaces u is a black NULL node. As you can see s (30), the sibling of the NULL node is black and has two black NULL children. Now node v (NULL) becomes a double black node. Now we first recolor s to be red. p (20) will absorb the blackness. Since p is already a black node, we need to propagate the blackness up the tree.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

      \r\n\r\n \r\n

      This is the case where V\u2019s sibling, S<\/strong> (Right Child of Parent P of V) is Black and<\/strong> S\u2019s Right child is RED (Left child can be either color) <\/strong>(Figure 26.10). The steps for fixing are as follows:<\/p>\r\n \r\n\r\n\u2013\u00a0 Rotate S around P\r\n\r\n\u2013\u00a0 Swap colors of S and P, and color S\u2019s right child Black\r\n\r\n\u2013\u00a0 This is the terminal case \u2013 we\u2019re done\r\n\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

      This fixing is explained in Figure 26.11. We Left Rotate S (sibling of V that replaces the deleted node U), around P (parent of V). Then we swap the colors of S and P where P (red becomes black), S (black becomes red) and the red right child of S becomes black. We then continue down the tree.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

      \r\n\r\n \r\n

      Figure 26.12 shows an example of the above case. Here parent p (rooted at 30) is a sub-tree, u (20) is the node that is deleted and v the node that replaces u which was originally a black NULL node and now becomes a double black node. As you can see s (40), the sibling of the v node is black and has a red right child r (50). Remember that the left child of s can be either red (in this example 35 is red) or black. We first carry out a Left Rotate of s about p. and swap the colors of s and p. Since both are black in our example there in no effect. The original red right child of s (r-50) is now recolored black.<\/p>\r\n \r\n\r\n26.4.2.2.3 Bottom-Up Deletion - Case 4<\/strong>\r\n\r\n \r\n\r\nThis is the case where S the<\/strong> Right Sibling of V is Black, S\u2019s Right child is Black<\/strong> and S\u2019s Left child is Red <\/strong>(Figure 26.13). The steps for fixing are as follows:\r\n

        \r\n \t
      • Rotate S\u2019s left child around S<\/li>\r\n \t
      • Swap color of S and S\u2019s left child<\/li>\r\n \t
      • Now we are left with the conditions of case 3<\/li>\r\n<\/ul>\r\n<\/div>\r\n
        \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

        This fixing is explained in Figure 26.14. We Right Rotate, the red left child LC of S with S as the pivot. Then we again Left rotate LC around P (the orginal parent of S). Then we swap the colors of S and LC the original left child of S. If the new V is Red, continue down again. However if the new V is Black (S is Red, P is Black), we Rotate S around P and recolor P and S. Now go back to the main case, that is we go to step 2, where again the cases 1-5 are checked.<\/p>\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\nFigure 26.15 shows an example of the above case. Here parent p (rooted at 30, u\r\n\r\n \r\n\r\n(20)\u00a0 is the node that is deleted and v the node that replaces u which was originally a black NULL node and now becomes a double black node. As you can see s (40), the sibling of the v node is black and has a red left child r (35). We first carry out a Left Rotate of lc (left child LC of s) about s. Then we again Right Rotate lc about p (the original parent of s). Then we swap the color of s and s\u2019s original left child lc.\r\n\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n\u00a0<\/strong>\r\n\r\n26.4.3 Algorithm for Fixing after Deletion<\/strong>\r\n\r\n \r\n

        The algorithm for the fixing of the red-black after the deletion of a node is given in Figure 26.16. Here we assume that the deletion of a node has already been carried out and the replacement of the deleted node by another node sometimes results in violation of the red-black properties which needs to be fixed.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\nSummary<\/strong>\r\n

          \r\n \t
        • Explained the concept of deletion from Red Black Trees<\/li>\r\n \t
        • Discussed the properties of Red Black Trees that are affected by Deletion<\/li>\r\n \t
        • Explained the deletion operation of Red Black Trees<\/li>\r\n<\/ul>\r\n\"\"","rendered":"
          \n

           <\/p>\n

          Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of Red Black tree and insertion into them. In this module we will discuss deletion from Red-Black Trees.<\/p>\n

           <\/p>\n

          Learning Objectives<\/strong><\/p>\n

           <\/p>\n

          The learning objectives of the module are as follows:<\/p>\n

           <\/p>\n

          \u2022 To understand the concept of deletion from Red Black Trees<\/p>\n

          \u2022 To discuss the properties of Red Black Trees that are affected by Deletion<\/p>\n

          \u2022 To explain the deletion from Red Black Trees<\/p>\n

           <\/p>\n

          26.1 Deletion from Red-black Trees<\/strong><\/p>\n

           <\/p>\n

          There are basically two approaches to deletion from Red-black trees. The bottom-up approach is recursive where the BST deletion is carried out going down the tree (winding up the recursion) and the RB(Red-black) properties violated as a result of the deletion is fixed while coming back up the tree (unwinding the recursion). The other approach is the iterative top down approach where the tree is restructured on the way down itself and hence we do not need to go up the tree for fixing the violated RB properties. In this module we will be discussing the bottom-up approach in detail.<\/p>\n

           <\/p>\n

          26.2 Deletion from Binary Search Trees<\/strong><\/p>\n

           <\/p>\n

          Before we discuss deletion from Red-black, let us recall the deletion of a node from a binary search tree, since Red-black trees are a type of balanced binary search trees. In the case of deletion from binary search trees, there are basically three cases. If the node to be deleted is a leaf, we can just delete it. If the node to be deleted has just one child, we replace it with that child by making the parent of the node to be deleted to point to the one child that exists. If the node to be deleted has two children, we replace the node by its in-order predecessor\/successor and then then delete the in-order predecessor\/ successor (a recursive step). We note that the deletion of the in-order predecessor\/ successor will have either no child or only one child. In other words eventually a BST deletion will be done with the node being a leaf or having just one child.<\/p>\n<\/div>\n

          \n

           <\/p>\n

          26.3\u00a0 Bottom-up Deletion<\/strong><\/p>\n

           <\/p>\n

          As we have already discussed we will be discussing bottom \u2013 approach to Red-black tree deletion. Now let us introduce some variables, in order to later explain the deletion from Red-black Tree.<\/p>\n

           <\/p>\n

          1. If deleted node U, is a leaf, think of deletion as replacing U with the NULL pointer, V.<\/p>\n

          2. If U had one child, V, think of deletion as replacing U with V.<\/p>\n

           <\/p>\n

          What can go wrong?? -Which RB Property may be violated after deletion?<\/p>\n

            \n
          • If U is Red<\/strong>? – Not a problem \u2013 no RB properties are violated<\/li>\n
          • If U is Black<\/strong>? if U is not the root, deleting it will change the black-height<\/strong> along some path<\/strong><\/li>\n<\/ul>\n

             <\/p>\n

            26.2.1 Concept of Red-black Deletion<\/strong><\/p>\n

             <\/p>\n

            Now let us discuss deletion from Red-black trees. In insert operation of Red-black trees, we check color of uncle to decide the appropriate case. In delete operation of Red-black trees, we will need to check the color of sibling<\/em> to decide the appropriate case. In the case of deletion, the main violated property is, change of black height in sub-trees as deletion of a black node may cause reduced black height in one root to leaf path that is RB property 5 may be violated.<\/p>\n

             <\/p>\n

            In order to understand deletion, we need to understand the notion of double black. When a black node is deleted and replaced by a black child, the child is marked as double black<\/em>. The main task now becomes the conversion of this node marked as double black to single black.<\/p>\n

             <\/p>\n

            26.2.2 Understanding Deletion with an Example<\/strong><\/p>\n

             <\/p>\n

            Let us assume that the node that is deleted is U. Now let us see what will be the consequence if the node U that was removed is Black.<\/strong> In other words let us see which of the 5 RB properties will be affected by this deletion.<\/p>\n

             <\/p>\n

            Property 1-Every node is either red<\/strong> or black<\/strong> \u2013<\/strong> this property is not affected by the deletion of a black node.<\/p>\n

             <\/p>\n

            Property 2 – The root is black<\/strong> \u2013 this property will be violated if the node that is deleted is the root and the child that replaces it is red. The property that every leaf (NULL) node is black<\/strong> is not affected by the deletion of a black node.<\/p>\n

             <\/p>\n

            Property 3 &4 – If a node is red, then both its children are black \u2013 this property will be violated as the deletion of the black node could sometimes create two red nodes in a row<\/p>\n

             <\/p>\n

            Property 5 – For each node, all paths from the node to descendant leaves contain the same number of black nodes \u2013this property may be violated as the deletion of the black node could change the black heights of some nodes.<\/p>\n

             <\/p>\n

            26.2.3 Deletion \u2013 Case 1 and Case 2<\/strong><\/p>\n

             <\/p>\n

            Let U be the node to be deleted and V be the child that replaces U. V is NULL when U is a leaf and color of NULL is considered as Black.<\/span><\/p>\n

             <\/p>\n

            Case 1 : If either U or V is red that is U is black and V is red or U is red and V is black<\/strong><\/p>\n

            Case 2 : If Both U and V are Black<\/strong>.<\/span><\/p>\n

             <\/p>\n

            26.2.3.1 Case 1: If either U or V is red<\/strong><\/p>\n<\/div>\n

            \n

             <\/p>\n

            Figure 26.1 shows the case where U the node to be deleted is black and V is red. 30 the parent of U is black. In this case U, the black node to be deleted is 20 and V, the red node that replaces it is 10. We mark the replaced child 10 as black. There will be no change in black height. U and V cannot be red as U is parent of V and two consecutive reds are not allowed in the original red-black tree.<\/p>\n

             <\/p>\n

            \"\"<\/p>\n

             <\/p>\n

            26.2.3.2 Case 2: If both U and V are Black<\/strong>.<\/p>\n

             <\/p>\n

            In this case we color V as double black. Now our task reduces to converting this double black to single black. If U is leaf, then V is NULL and color of NULL is considered as black. So the deletion of a black leaf also causes a double black. This case is shown in Figure 26.2 where U, 10 is the black node to be deleted and the V node that replaces it is NULL. Now this NULL node V becomes a Double black Node.<\/p>\n

             <\/p>\n

            \"\"<\/p>\n<\/div>\n

            \n

             <\/p>\n

             <\/p>\n

            26.3 Steps of the Deletion Procedure<\/strong><\/p>\n

             <\/p>\n

            For deletion we first carry out regular BST deletion. Let U be the node to be removed. The removed node can have at most one child. If deleted node, U is a leaf, deletion is the replacement of U with the NULL pointer, V. If U had one child, V, deletion is the replacement U with V. If the removed node U was red, no property could get violated, so we just remove it. Otherwise that is U is black remove it and call the tree-fix algorithm on U\u2019s child V (the node which replaced the position of U). If U is not the root, deleting it will change the black-height along some path.<\/p>\n

             <\/p>\n

            26.4 Fixing the problem<\/strong><\/p>\n

             <\/p>\n

            Let us assume that V is the node that has the \u201cextra\u201d unit of blackness, due to the deletion of a node U. This extra blackness must be absorbed into the tree (by a red node), or propagated up to the root and out of the tree.<\/p>\n

             <\/p>\n

            Let us assume that the node that we just deleted was U. Let the node that replaces it be V and is the node with an extra unit of blackness or the double black node. Let the parent of V be P and it\u2019s sibling be S. In the explanation we give we use the notation given in Figure 26.3.<\/p>\n

             <\/p>\n

            \"\"<\/p>\n

             <\/p>\n

             <\/p>\n

             <\/p>\n

            26.4.1 Deletion and Violation of Red-Black Properties<\/strong><\/p>\n

             <\/p>\n

            The extra black unit is pushed up the tree until a red node is reached, when it is made black or the root node is reached or it can be removed by rotating and recoloring. If the deleted node U is red, no property is violated. If U is a leaf, no property is violated. Otherwise U is black and has a child V, and property 2, 3, and 4 (refer to properties of Red-black trees) are violated. For fixing property 2, set the color of root to black after deletion. To fix property 3 and 4, if U\u2019s Child V (the replacing node) is red, set it to black and we are finished. If V is black, fixing property 3 and 4 requires the adding of an extra unit of black to V, making it a double black node. However now property 1 is violated.<\/p>\n

             <\/p>\n

            In order to fix property 1, we will consider if V (the doubly black node) is a left child or right child, of its parent, the color of V’s sibling S is red or black and the colors of S’s children. We consider x is a left child first, where we have four cases. The other four cases when V is a right child of its parent are symmetric.<\/p>\n

             <\/p>\n

            26.4.2 Cases 1-4<\/strong><\/p>\n

             <\/p>\n

            Remember V is the node that has is of concern here and is the node that replaces the node U that was deleted. Considering the double black node V as left child of its parent we have 4 cases as discussed below:<\/span><\/p>\n<\/div>\n

            \n
              \n
            • Case 1 – Sibling S of V is Red<\/li>\n
            • Case 2-4 -Sibling S of V is Black<\/li>\n
            • Case 2 \u2013 S is Black & S has two Black Children<\/li>\n
            • Case 3 \u2013 S is Black & Right Child of S is Red & Left Child is either<\/li>\n
            • Case 4 \u2013 S is Black & Right Child of S is Black & Left Child is Red<\/li>\n<\/ul>\n

               <\/p>\n

              Now we will see how we handle each of the cases when we use the bottom-up approach. In delete operation of Red-black trees, checking the color of sibling<\/em> is the operation which helps to decide the appropriate case.<\/p>\n

               <\/p>\n

              26.4.2.1 Bottom-Up Deletion -Case 1<\/strong><\/p>\n

               <\/p>\n

              This is the case when Sibling S of V is Red<\/strong> (as shown in Figure 26.4).<\/p>\n

               <\/p>\n

              \u2022\u00a0 Rotate S around P (parent of V )<\/p>\n

              \u2022\u00a0 Recolor S & P<\/p>\n

               <\/p>\n

              This case is not a terminal case, as after this case, one of the other cases will apply. Three cases (2-4) apply when the sibling S is black<\/p>\n

               <\/p>\n

              \"\"<\/p>\n<\/div>\n

              \"\"<\/p>\n

              \n

               <\/p>\n

              The operations for case 1 when V\u2019s sibling S is Red is shown in Figure 26.5. Here we first perform a left rotate of S with P as pivot. Now S becomes the parent of P and P becomes Left Child of S. Now we recolor where S is colored black and P red.<\/p>\n

               <\/p>\n

              26.4.2.2 Bottom-Up Deletion -Case 2-4<\/strong><\/p>\n

               <\/p>\n

              This concerns three cases as discussed in section 26.4.2 \u2013 Cases 2-4 where V has<\/strong> two Black Children \u2013 Sibling S of V is Black <\/strong>(as shown in Figure 26.6). The three cases are as follows:<\/p>\n

               <\/p>\n

              Case 2. S has 2 Black Children<\/p>\n

              Case 3. S\u2019s Right child is Red (Left child can be either color)<\/p>\n

              Case 4. S\u2019s Right child is Black and S\u2019s Left child is Red<\/p>\n

               <\/p>\n

              \"\"<\/p>\n

              Now we will consider each of the three cases 2-4, one by one.<\/p>\n

               <\/p>\n

              26.4.2.2.1 Bottom-Up Deletion -Case 2<\/strong><\/p>\n

               <\/p>\n

              This is the case where V\u2019s sibling, S, is Black and<\/strong> it has<\/strong> two Black children<\/strong><\/p>\n

               <\/p>\n

              (Figure26.7). The steps for fixing are as follows:<\/p>\n

               <\/p>\n

              \u2013\u00a0 Recolor S to be Red<\/p>\n

              \u2013\u00a0 P absorbs V\u2019s extra blackness<\/p>\n

              \u2022 If P is Red, we\u2019re done (it absorbed the blackness)<\/p>\n

              \u2022 If P is Black, it now has extra blackness and problem has been propagated up the tree<\/span><\/p>\n<\/div>\n

              \n

              \"\"<\/p>\n

               <\/p>\n

              The operations for case 2 when V\u2019s sibling S is black and has two black children is shown in Figure 26.8. Here we first recolor S as red and make P absorb the blackness. If P was red, then the operation is complete. However if P is black, we propagate black up the tree.<\/p>\n

               <\/p>\n

               <\/p>\n

              \"\"<\/p>\n

              Figure 26.9 shows an example of the above case. Here parent p (rooted at 20) is a sub-tree, u (10) is the node to be deleted and v the node that replaces u is a black NULL node. As you can see s (30), the sibling of the NULL node is black and has two black NULL children. Now node v (NULL) becomes a double black node. Now we first recolor s to be red. p (20) will absorb the blackness. Since p is already a black node, we need to propagate the blackness up the tree.<\/p>\n<\/div>\n

              \"\"<\/p>\n

              \n

               <\/p>\n

              This is the case where V\u2019s sibling, S<\/strong> (Right Child of Parent P of V) is Black and<\/strong> S\u2019s Right child is RED (Left child can be either color) <\/strong>(Figure 26.10). The steps for fixing are as follows:<\/p>\n

               <\/p>\n

              \u2013\u00a0 Rotate S around P<\/p>\n

              \u2013\u00a0 Swap colors of S and P, and color S\u2019s right child Black<\/p>\n

              \u2013\u00a0 This is the terminal case \u2013 we\u2019re done<\/p>\n

               <\/p>\n

               <\/p>\n

              \"\"<\/p>\n

               <\/p>\n

               <\/p>\n

              This fixing is explained in Figure 26.11. We Left Rotate S (sibling of V that replaces the deleted node U), around P (parent of V). Then we swap the colors of S and P where P (red becomes black), S (black becomes red) and the red right child of S becomes black. We then continue down the tree.<\/p>\n<\/div>\n

              \"\"<\/p>\n

              \n

               <\/p>\n

              Figure 26.12 shows an example of the above case. Here parent p (rooted at 30) is a sub-tree, u (20) is the node that is deleted and v the node that replaces u which was originally a black NULL node and now becomes a double black node. As you can see s (40), the sibling of the v node is black and has a red right child r (50). Remember that the left child of s can be either red (in this example 35 is red) or black. We first carry out a Left Rotate of s about p. and swap the colors of s and p. Since both are black in our example there in no effect. The original red right child of s (r-50) is now recolored black.<\/p>\n

               <\/p>\n

              26.4.2.2.3 Bottom-Up Deletion – Case 4<\/strong><\/p>\n

               <\/p>\n

              This is the case where S the<\/strong> Right Sibling of V is Black, S\u2019s Right child is Black<\/strong> and S\u2019s Left child is Red <\/strong>(Figure 26.13). The steps for fixing are as follows:<\/p>\n

                \n
              • Rotate S\u2019s left child around S<\/li>\n
              • Swap color of S and S\u2019s left child<\/li>\n
              • Now we are left with the conditions of case 3<\/li>\n<\/ul>\n<\/div>\n
                \n

                \"\"<\/p>\n

                 <\/p>\n

                 <\/p>\n

                This fixing is explained in Figure 26.14. We Right Rotate, the red left child LC of S with S as the pivot. Then we again Left rotate LC around P (the orginal parent of S). Then we swap the colors of S and LC the original left child of S. If the new V is Red, continue down again. However if the new V is Black (S is Red, P is Black), we Rotate S around P and recolor P and S. Now go back to the main case, that is we go to step 2, where again the cases 1-5 are checked.<\/p>\n

                 <\/p>\n

                 <\/p>\n

                \"\"<\/p>\n

                 <\/p>\n

                Figure 26.15 shows an example of the above case. Here parent p (rooted at 30, u<\/p>\n

                 <\/p>\n

                (20)\u00a0 is the node that is deleted and v the node that replaces u which was originally a black NULL node and now becomes a double black node. As you can see s (40), the sibling of the v node is black and has a red left child r (35). We first carry out a Left Rotate of lc (left child LC of s) about s. Then we again Right Rotate lc about p (the original parent of s). Then we swap the color of s and s\u2019s original left child lc.<\/p>\n

                 <\/p>\n

                \"\"<\/p>\n<\/div>\n

                \u00a0<\/strong><\/p>\n

                26.4.3 Algorithm for Fixing after Deletion<\/strong><\/p>\n

                 <\/p>\n

                The algorithm for the fixing of the red-black after the deletion of a node is given in Figure 26.16. Here we assume that the deletion of a node has already been carried out and the replacement of the deleted node by another node sometimes results in violation of the red-black properties which needs to be fixed.<\/p>\n

                 <\/p>\n

                \"\"<\/p>\n

                 <\/p>\n

                Summary<\/strong><\/p>\n

                  \n
                • Explained the concept of deletion from Red Black Trees<\/li>\n
                • Discussed the properties of Red Black Trees that are affected by Deletion<\/li>\n
                • Explained the deletion operation of Red Black Trees<\/li>\n<\/ul>\n

                  \"\"<\/p>\n","protected":false},"author":3,"menu_order":26,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-v-geetha"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-378","chapter","type-chapter","status-publish","hentry","contributor-dr-t-v-geetha"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/378","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":4,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/378\/revisions"}],"predecessor-version":[{"id":853,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/378\/revisions\/853"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/378\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/media?parent=378"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapter-type?post=378"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/contributor?post=378"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/license?post=378"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}