Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C++

Red-Black Tree Deletion

Understand the deletion process in Red-Black Trees, including how to maintain their essential color and balance properties. Explore the different cases for deletion, learn how rotations restore balance, and grasp the algorithmic approach with relevant C++ context. This lesson prepares you to implement and troubleshoot Red-Black Tree deletions effectively.

We'll cover the following...

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:

  1. Search for a node with the given value to remove. We will call it currentNode.
  2. Remove the currentNode using the standard BST deletion
...