算法学习之数据结构之红黑树（1）

　　红黑树的性质。红黑树是一种二叉查找树，，每一个节点增加一个存储位表示节点的颜色，为红色或者黑色。红黑树确保没有一条路径会比其他路径长出两倍。因而是接*衡的。

　　树的每个节点包含五个域：color, parent, key, left, right。一个二查找树如果满足如下红黑性质，则为一个红黑树。

　　1)每个节点或是红的，或是黑的。  

　　2)根节点是黑。

　　3)每个叶节点（NIL）是黑的。

　　4)如果一个节点是红的， 则它的两个孩子都是黑的。

　　5)对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。

　　从某个节点x出发到达一个叶节点的任意一条路径上，黑色节点的个数成为该节点x的黑高度。

　　一个有n个内节点的红黑树的高度至多为2lg(n+1)

　　

　　当对红黑树上进行insert和delete时，对树进行了修改，结果可能会违反红黑树的性质，所以需要改变树中的节点的颜色和指针结构，即需要进行旋转。

　　左旋，假设它的右孩子节点y不是nil[T]；x可以为树内任意右孩子不是nil[T]的节点，左旋以x和y之间的链为轴进行，它使y成为该子树新的根，x成为y的左孩子节点，而y的左孩子节点为x的右孩子。

　　伪代码如下：

left-rotate(T, x)
y = right[x]
right[x] = left[y] // y的左子树变为x的右子树
parent[left[y]] = x
parent[y] = parent[x] // x的父亲节点是y的父亲节点
if parent[y] == null
    then root[T] = y // x的根节点是根节点则置为y
    else if x == left[parent[x]] // 如果x是其父节点的左孩子节点，则将y置为x父节点的左孩子节点否则置为其父节点的右孩子节点
             then left[parent[x]] = y
             else right[parent[x]] = y
left[y] = x // y的左孩子结点是x
parent[x] = y // x的父亲节点是y

rb-insert(T, z)
y = null
x = root[T]
while x != null
    do y = x
        if(key[x] < key[z])
            then x = right[x]
            else x = left[x]
parent[z] = y
if(y == null) //树是空的
    then root[T] = z
    else if key[z] < key[y]
        then left[y] = z
        else right[y] = z
left[z] = nil[T]
right[z] = nil[T]
color[z] = RED // 着色为红色
rb-insert-fixup(T, z)

rb-insert-fixup(T, z)
while color[p[z]] = RED
    do if parent[z] == left[parent[parent[z]]] // z节点的父亲节点是其祖父节点的左孩子节点
             then y = right[parent[parent[z]]] // y为z节点的祖父节点的右孩子节点，即叔叔节点
                    if color[y] == RED // 叔叔节点为红色 CASE1
                        then color[parent[z]] = black // 父亲节点黑色
                               color [y] = black // 叔叔节点黑色
                               color[parent[parent[z]] = red // 祖父节点红色
                               z = parent[parent[z]]
                        esle if z == right[parent[z]] // 叔叔节点是黑的，且z为父节点的右孩子节点 CASE2
                                 then z = parent[z]
                                        left-rotate(T, z)  // 左旋转
                         // CASE3
                        color[parent[z]] = black //把父节点着黑色
                        color[parent[parent[z]]] = red //原来的祖节点着红色
                        right-rotate(T, z)
         else // z节点的父亲节点是其祖父节点的右孩子节点
                操作和左孩子节点一样
color[root[T]] = black // 最后把根节点置为黑色