Red black tree is a data structure for searching data and can self-balance after modification. I will try to implement it and log in this article. You can find the source code in here.

## Node

Evey Node have five member properties. `color_`

represent the color of node, red or black.

1 | `enum RbTreeColor { rb_red = false, rb_black = true };` |

## Iterator

function `increment()`

find the last node that is larger than current node, corresponding `operator++`

. function `decrement()`

find the last node that is smaller than current node, corresponding `operator--`

.

1 | `template <typename T, typename Ref, typename Ptr>` |

## Tree Property

### header

- parent: link to root if exist
- left: also call leftmost, link to the most left node of tree
- right: also call leftmost, link to the most right node of tree
- color: default is red

### root

- parent: link to header
- left: link to nullptr if no node
- right: link to nullptr if no node
- color: always is black

### Multi Node

See a tree with multi nodes. The children of leaf are nullptr.

## Rotation

### Left Rotation

When the right sub-tree is taller, we need to rotate left to shorten it.

1 | `/*` |

### Right Rotation

When the left sub-tree is taller, we need to rotate right to shorten it.

1 | `/*` |

## Rule and Balance

- The color of node is eithor red or black.
- The root node always is black.
- If a node is red, its children must be black.
- Every path of every sub-tree have the same number of black nodes.

As the rule 4, we can ensure the different of the height of the tallest sub-tree and that of the shortest sub-tree cannot over 2 times. The color is the measure of the balance for red black tree, as the height difference for the AVL tree.

## Insertion

We insert a not-allow-replaced key with three considerations:

- insert to the left of leftmost
- insert to the right of y if just bigger than y
- insert to the left of y if just bigger than decrement(y)

1 | `pair<iterator, bool> insertUnique(const Val &v) {` |

### Inside and Outside

For convenient, we define the inside and outside as shown blow. If the cur node direction is not equal to the parent direction, we call it inside, or else we call it outside.

1 | `/*` |

### ReBalance

Initially, x is new inserted node. x is red default. When its parent is red, which break the rule 3. If its parent is black, it do not breaks any rules, which does not need to rebalance.

You need to consider four situations: - First, we need to think about the parent of x is either a left or a right, which determines the rotation direction. - And then, consider the uncle of x is either red or black, which determines how to change the color.

In the process of percolation and rebalance, the parent of x initially is red, when percolate up, we change its color. How to change is determines to its sibling (uncle of x), which we need to make the color as same as its sibling.

- If uncle is red, the grandparent must be black, all of you need to do is to change the color of parent and uncle to black, and grandparent's color to red, for following the rule 3. But these probably break the rules in higher position, so we need to percolate up to the grandparent.
- After percolate up, if you find the parent is black, you can stop the rebalance, because the number of black have not changed and followed the rule 3 as above step. But if the parent is red, two continuous red node break the rule 3 again. And its uncle must be black or null. Looking at the following steps.
- If uncle is black or null,
- If cur node is in outside, change parent's color to black and grandpa's color to red. These will make the number of black nodes in its parent sub-tree increase 1 and greater than that of the uncle sub-tree, so we do a rotation to make the parent move to the grandpa position to make anthor direction sub-tree have the same number of black nodes. The rotation direction is opposite to its direction to its parent.
- If cur node is in inside, we need to do a rotate firstly (the rotation direction is same to its direction to its parent) to make the cur node becomes the parent node, and the original parent node becomes the cur node in the outside, as same as the situation above, so do the same thing as above. (total two rotations)

- Finally, making the root's color to black, these action do not break any rule.

1 | `inline void _rebalance(NodePtr x, NodePtr& root) {` |

## Comments