红黑树

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.

红黑树性质：
1. The root is black.
2. If a node is red, then both its children are black.
3. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得红黑树大致上是平衡的。

rotation操作

插入
1. 先将新节点像BST的插入那样插入，将新节点标记为红色。(如果新节点的父亲为黑色就不用调整了)
2. 然后从该节点开始，依次向上进行颜色调整，直到父亲节点为黑色(即达到满足红黑树性质的状态)。
向上颜色调整规则(z为新节点，y为z父亲节点的兄弟)

Case 1: z’s uncle y is red (whether z is left or right child)

Case 2: z’s uncle y is black and z is a right child
Case 3: z’s uncle y is black and z is a left child

插入已让我很晕，删除更为复杂，还是算了···

更多参看《算法导论》