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
Red Black Tree is a binary search tree. With extra property with each node having color either RED or BLACK. It has following properties: Every node is either RED or BLACK Root element will have BLACK color. Every RED node has BLACK children. Every path from root to leaf will have same number of BLACK nodes. We have few theorems over RB tree: Note: Height of RB tree is θ(logn). Insertion: Insertion in RB tree is little tricky as compared to BST, we have following cases to insert a node in RB tree: When tree is null just insert the node and it will be root, color will be BLACK. To insert an element first find its position: if key <= node.key then move to left else move to right Once we find the correct place to insert, we insert the node with color RED. But if the parent of the node just inserted has color RED then it will violate 3 property. So we have to fix this issue. We call it double RED problem, we resolve it using following few cases. DOUBLE R