Red Black tree deletion involves following cases: If node to delete is a RED leaf node then just delete it. If node to delete is a BLACK node and has one red child then, just replace it with child and retain color of node to be deleted. If node is having more than two children then just replace the node with in-order predecessor and call the delete routine at in-order predecessor recursively. But the problem arises when node to delete is a BLACK node and it has only one BLACK child or node to be deleted is a BLACK leaf node. Then DOUBLE BLACK problem arises. Note: Points form 1 to 3 are easy to implement and can be understood using the code given below. To resolve DOUBLE BLACK problem we have following four cases: Why double black problem: Suppose we have deleted a BLACK node and the number of nodes in the path going through it is reduced by 1. So the BLACK replacement will carry one extra BLACK color to retain property 5 of RB Tree that in any path from root to leaf...
Programming Bits by: Amit