Deletion in a RBT uses two main processes, namely,
Procedure 1: This is utilized to delete an element in a given Red-Black Tree. It involves the method of deletion utilized in binary search tree.
Procedure 2: when the node is removed from a tree, and after deletion, there might be chances of losing Red-Black Properties in a tree and so, some of the cases are to be considered to retain those properties.
This process is called only while the successor of the node to be deleted is Black, however if y is red, the red- black properties yet hold and for the following reasons:
- No red nodes have been made adjacent
- No black heights in the tree have altered
- y could not have been the root
Now, the node (say x) that takes the position of the deleted node (say z) will be called in process 2. Now, this process starts with a loop to make the extra black up to the tree until
o X points to a black node
o Rotations to be performed and recoloring to be done
o X is a pointer to the root wherein the extra black can be easily removed
This while loop will be executed till x becomes root and its color is red. Here, a new node (say w) is taken which is the sibling of x.
There are four cases that we will be letting separately as follows:
Case 1: If color of w's sibling of x is red
Since W must have black children, we can change the colors of w & p (x) and then left rotate p (x) and the new value of w to be the right node of parent of x. Now, the conditions are satisfied and we switch over to case 2, 3 and 4.
Case 2: If color of w is black & both of its children are also black.
As w is black, we make w to be red leaving x with only one black and assign parent (x) to be the new value of x. Now, the condition will be again verified, i.e. x = left (p(x)).
Case 3: If the color of w is black, however its left child is red and w's right child is black. After entering case-3, we change the color of left child of w to black and w to be red and then carry out right rotation on w without violating any of the black properties. Now the new sibling w of x is black node with a red right child and therefore case 4 is obtained.
Case 4: While w is black and w's right child is red.
It can be done by making some color changes and performing a left rotation on p(x). We can delete the extra black on x, making it single black. Setting x as the root causes the while loop to terminate.