Red Black Tree algorithm: delete

Today's topic is the Red Black Tree algorithm's deletion procedure.

This is, shown as

RB-DELETE(T, z)

of which T stands for the tree and the z for the node to delete.

First, we set the pointer to z, as y:

y = z

then to later fix the broken red black texture patterns, save the y's original color as clone of the y's color property.

In the next, if the deletion target node z has only one child, then we apply RB-TRANSPLANT(T, z, z.right(or left)) to usurp the node z and instead place the node A.

On the other hand, if the node z has both the right and left child, there should be the extra steps:

1. suppose the right child (henceforth the bigger node) of z as z.right, then 

y = TREE-MINIMUM(z.right)

means that to set the minimum (smallest) node below the area z.right as y. (y as pointer)

then, there should be two patterns conceivable:

Since, these tree is in nature, as similar to the double linked list it's relational, 

when z is parents of the node B, then

 z should think that "oh, my bigger kid is B."

 B should think that "oh, my mom is z."

each time you need to make topological change in the R-B tree, you should update both dictations.

detect the minimum of the area under z.right = B with min(B)

1. one is the case B does not have any child node smaller (UPPER), or

2. the other is some node other than B is the smallest node under B (LOWER).

Then, as picture shows, in case (1.) since B is the minimum in the area below z, such that y should point at the node B.

y = B

Else, in case (2.) since the C is the minimum in the area below z, such that y should point at the node C.

Then we substitute this B with y for convenience:

then, for the right node of this y (in previous diagrams it is hidden), if we name it as node x, then

1. y should think that "oh, my bigger kid is x". (above pic)

then for the upper case (if y's parent is z), then 

2.  y should think that "oh, my mom is z"

3.  x should think that "oh,  my mom is y" as well.

These are just relation relation thing. Each character(=node) should clearly know that who their neighbors are and who they are to him/her.

On the other hand, for the lower case (if y's parent is not z) then

y should be replaced by its bigger child x, and y is miserably lonely so far. (sob)

This is done by the RB-TRANSPLANT(T, y, y.r)

2'. Then, y should think that "oh, my bigger child should be z's bigger child now, which is B!!!"

(oh... child abduction...)

no. no. no. It's not child abduction. They should love each other.

3'. B should think that "oh, now my mom should be y!!!!"

So you know, here is the mutual agreement!!!!!

Then now, okay we live in the cruel world, the node z, now is really useless piece of shit, needs to be purged from the earth and y should replace with it. 😢

Okay. relation, relation, relation.

4. y also need to clarify that "oh, my smaller kid should be former z's smaller kid, which is A!!!"

5. Then, you already guess, A should now forget the former mom z, who is purged from the whole galaxy and now think that "oh! my mom is now y! mommy mommy." (A.p = y)

Then the R-B tree's deletion algorithm ends.

After this logic, we need to fix the corrupted rule of black-red pattern rule, so with additional function it should be fixed.

Thanks for the reading.