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

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.