Those data structures can not learn from the leetcode— Red-black tree(2)

LORY
5 min readNov 26, 2022

How the rebalancing happens during deletion in RB Tree

Continuing with advanced DSA topic: Skip list, B Tree Step by Step, Treap.

And in the last post, we know 8 cases to handle during insertion.

In this post, I will go over the deletion process of the Red-black tree step by step.

quick recap. what defines the Red-black tree.

Red-Black tree definition

  1. It is a self-balanced BST. (Binary Search Tree)
  2. Every node has a color (black or red)
  3. Root is black
  4. When Parent’s color is red then the child MUST be black
  5. From the current node to the leaf, the “black nodes on each path” is the same
  6. On every leaf, there are 2 “None” nodes, color is black

Deletion

Let’s start with the below Red-black tree.

Before we start Red-black tree deletion. let’s think about BST deletion. you can get the sample here.

Case 1: When deleting node is a leaf, delete it.

Case 2: When deleting a node that has only 1 child, replace it with the child.

Case 3: When deleting node has 2 children. find the successor (do BST, find left sub tree max or right sub tree min), swap, then delete it.

But that is BST. for Red-Black Tree, it is step 1. we need to consider the violation of rules. when a deleted black node, needs correction.

So Let’s imagine we have done BST delete. we need to discuss the cases, and we may or may not need to correct the black colors on the tree.

Let’s dive in.

Delete 10.

Since 10 is a red leaf. deletion does not cause any color issues. It is a very simple case.

Case #1 When deleting a red leaf, no need to do anything.

--

--

LORY

A channel which focusing on developer growth and self improvement