# Red-Black Tree Deletion

This lesson will cover the deletion function in Red-Black trees and will discuss all four deletion cases.

## Deletion in Red-Black Tree #

Before we start discussing how deletion works in a Red-Black tree, let’s discuss the main difference between the Insertion and Deletion operations in Red-Black trees.

In insertion, we may violate the alternating parent-child colors property, i.e., a red parent may have a red child. But, in the deletion function, we may end up deleting a black node that could violate the property that “the same number of black nodes must exist from the root to the None node for every path.”

In insertion, we check the color of the *sibling of the parent* of the *currentNode*, and based on the color; we perform appropriate operations to balance the tree. But now, in the deletion operation, we will check the color of the *sibling* node of the *currentNode*, and based on its color, we will perform some actions to balance the tree again.

## Algorithm for Deletion #

Here is a high-level description of the algorithm to remove the value in a Red-Black Tree:

- Search for a node with the given value to remove. We will call it
*currentNode*. - Remove the
*currentNode*using the standard BST deletion operation that we studied earlier.

When deleting in a BST, we always end up deleting either a leaf node or a node with only one child because, if we want to delete an internal node, we always swap it with a leaf node or a node with at most one child.

- In case of the leaf node deletion, delete the node and make the child of the parent of the node to be deleted
`None`

. - In the case of a node with one child only, link the parent of the node to be deleted with that one child.

Let’s name some nodes relative to Node C, which is the node that we want to delete:

- Node C – The node to be deleted (let’s call it
*currentNode*) - Node P – The parent node of the
*currentNode* - Node S – The sibling node (once we rotate the tree, Node R will have a sibling node which we name Node S)
- Node SC – child node of Node S
- Node R – node to be Replaced with the
*currentNode*and linked with Node P (Node R is the single child of Node C)

## Deletion Cases #

Let’s study the deletion cases and the steps performed in each of these cases to make the tree balanced again. Given below is the first case in which Node C or Node R is red. In this type of scenario, we make Node R black and link it to Node P.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.