RedBlackTree II Chinese version address

## Basic operation of red black trees

### Insert

Insert a node into the red-black tree, which steps need to be performed?

- think of the red-black tree as a binary search tree and insert the node.
- Set this node to red.
- Modify the tree by rotating and recoloring it to make it a red-black tree again.

#### Step Description

##### Step 1

The red-black tree is a binary search tree, which is still a binary search tree after the node is inserted. This means that the key of the tree is still ordered. In addition, whether it is left-rotation or right-rotation, the tree is a binary search tree before rotation, and after rotation it must be a binary search tree.

##### Step 2

Why should set the node’s color to red?

Because it is not violate 5 features. violate more less feature mean less things we need to deal with.

##### Step 3

So how many features it violate?

- As for feature 1, obviously not violate.
- As for feature 2, insert operation does not change the root node, so the color of root node is still black.
- As for feature 3, leaf node is null node, inserting non-null node does not affect feature.
- As for feature 4, Is possible to violate.

#### Case Description

##### Case 1

###### Description

The current node’s parent node is red, and the current node’s grandparent node’s other child node (uncle node) is also red

1 | while color[p[z]] = RED |

Grandfather node must exist at this time, otherwise it is not black red tree before inserting. At this point is divided into the parent node is the grandfather’s left child or right child, according to symmetry, we just untie a direction on it. Here only consider the parent node left grandfather’s situation, as shown below.

###### Method

Strategy is as follows:

- Sets the parent node to black.
- Sets the node of the uncle to black.
- set grandfather node to red.
- The grandfather node is set as the current node (red node).

As shown in the following pseudo code:

1 | then color[p[z]] ← BLACK ▹ Case 1 |

Then, insert repair case 1 translates into insert repair case 2.

##### Case 2

###### Description

The current node’s parent node is red, the uncle node is black, and the current node is the right child of its parent node

###### Method

Strategy is as follows:

- Set the parent as the new current node.
- Do left rotation on current node.

As shown in the following pseudo code:

1 | else if z = right[p[z]] |

Insertion Repair Case 2 translates into insert repair case 3.

##### Case 3

###### Description

The current node’s parent node is red, the uncle node is black, and the current node is the left child of its parent node

###### Method

Strategy is as follows:

- Sets the parent node to black.
- set grandfather node to red.
- Do right rotation on grandfather node.

As shown in the following pseudo code:

1 | color[p[z]] ← BLACK ▹ Case 3 |

### Code Reference

#### Pseudo code:

##### Insert Pseudo Code

1 | RB-INSERT(T, z) |

##### Insert-Fixed Pseudo Code

1 | RB-INSERT-FIXUP(T, z) |

#### C++ Implementation

##### Insert C++ Code

1 | template <class T> |

##### Insert-Fixed C++ Code

1 | template <class T> |