RedBlackTree I Chinese version address

## Binary Tree Review

There are several features of binary tree:

- if the left subtree of any nodes is not null, the value of all nodes on the left subtree is less than the value of its root node.
- if the right subtree of any nodes is not null, the value of all nodes on the right subtree is greater than the value of its root node.
- the left and right subtrees of any node are also binary tree.
- No nodes with equal values

## Red Black Tree Overview

Red Black Tree is a special binary tree. each node of a red black tree has a bit to represenet the color, which can be red or black.

### Red Black Tree Features

- the color of each node is red or black.
- the color of root node is black.
- the color of each leaf node is black.
- if a node is red, the subnode of it must be black.
- The same number of black nodes is included on all paths from a node to the node’s descendant node.

#### Notes:

- leaf node is means which node is null.
- Feature 5 to ensure that no path is twice as long as the other path. Thus, the red black tree is a relatively balanced binary tree.

## Application of red black trees

The application of the red-black tree is particularly extensive, mainly because it uses it to store ordered data. Its time complexity is O (lgn), which is very efficient.

But its implementation is complicated, and insert, delete operation will pay more cost.

- Set and Map in STL
- TreeSet and TreeMap in Java
- Virtual memory management in Linux

## Basic operation of red black trees

### Left Rotation

1 | z |

Make left rotation on x node, and it will be a left node.

#### Pseudo code

1 | LEFT-ROTATE(T, x) |

#### C++ Code

1 | template <class T> |

### Right Rotation

1 | y |

Make right rotation on x node, and it will be a right node.

#### Pseudo code

1 | RIGHT-ROTATE(T, y) |

#### C++ Code

1 | template <class T> |