借着stl的由头，讲讲红黑树（一）

红黑树看着有点费劲，分两次写，这次先写旋转和插入，下一篇写删除~~~
其实最早的时候，之所以买侯捷的这本《stl源码剖析》主要是因为想搞懂这篇文章的主题——rb-tree，因为当时自己作死，买的《算法导论》，但是这一章翻来覆去的，看不明白，哎，还是太菜鸡了，然后就一直拖到现在，最近也是一直在看这一块，总算水磨工夫起了点作用（也可以说是他山之石，可以攻玉哈~），两本书联合着看，外加一点网络资料，看懂了一丢丢，在这里跟大家分享一下喽~

首先rb-tree严格意义上讲并不是一颗非常严格的“平衡”二叉查找树，没有avl-tree严格，但是在其限制条件下，其关于集合的操作，最坏的时间复杂度为O(lgN)，所以rb-tree是好多stl的关联式容器均选择。

先来说一下rb-tree的相关性质：

1. 每一个节点多出一个关于颜色的性质：非黑即红

2. 根节点是黑色的

3. 每一个叶子节点（NULL）视为黑色

4. 如果一个节点为红色，那么它的两个孩子的颜色必须都为黑色

5. 对于任意节点来说，从其开始，至其任意子孙当中的叶子结点的每一条路径当中，所包含的黑色节点数目相同。

然后还要先来示例说明一下对应的rb-tree节点的代码，注意哈，这里是有父节点指针的~

struct RB_tree_node{
    int val;
    bool color;// false: red; true: black
    struct RB_tree_node *parent;
    struct RB_tree_node *lchild;
    struct RB_tree_node *rchild;
    RB_tree_node(int value):val(value), color(false), parent(NULL), lchild(NULL), rchild(NULL){}
};

然后说一下左旋转和右旋转，跟之前那一篇avl的差不多，就是多了父指针，

情形如下图：

代码如下：

struct RB_tree_node *Left_Rotate(struct RB_tree_node *x){
    struct RB_tree_node *y = x->rchild;
    bool flag = false;
    if( root == x) flag = true;
    x->rchild = y->lchild;
    if( y->lchild != NULL) y->lchild->parent = x;
    y->parent = x->parent;
    if( !flag ){
        if( x == x->parent->lchild)x->parent->lchild = y;
        else x->parent->rchild= y;
    }
    y->lchild = x;
    x->parent = y;
    if(flag) root = y;
    return y;
}
struct RB_tree_node *Right_Rotate(struct RB_tree_node *y){
    struct RB_tree_node *x = y->lchild;
    bool flag =false;
    if( y == root) flag = true;
    y->lchild = x->rchild;
    if(x->rchild != NULL) x->rchild->parent = y;
    x->parent = y->parent;
    if(!flag){
        if( y==y->parent->lchild) y->parent->lchild = x;
        else y->parent->rchild = x;
    }
    x->rchild = y;
    y->parent = x;
    if(flag) root = x;
    return x;
}

接下来，说一下红黑树的插入，第一点要说明的是，插入节点的颜色默认都是红色的；这样以来呢，它就不会影响到性质3,5，如果是根节点，直接变黑就行了；但是，如果影响了性质4，就需要用到之前的旋转以及颜色调换了~

违背性质4的插入的话，用《stl源码剖析》的话说，只有两种情况：内插和外插，如下图所示，其中插入的节点可以自带子树，也可以是新插入节点，但是都保证知味饭性质4，这样做是为了将来在递归回溯时方便理解：

（为了方便，这里没有画出其他子树，并假设在插入之前该树满足红黑树性质）

我们通过观察可以发现，内插的话，通过一次之前的左旋或者右旋操作，会变成了外插，这样的话，以后的文章就可以归结为外插入一种情况了。

现在来分析一下，外插入红色节点的父节点为红色的情况，这种情况就要看其叔父节点的颜色了，因为两个红色节点肯定不能相邻，肯定会进行改变颜色或者进行旋转，影响的只有其祖父节点下的性质4和5，这样的话，看叔父节点就好了：

1） 叔父节点为黑，进行如下变换：

简单解释一下，首先，调整后的树满足性质4；之后查看性质5，原来对于G，a,b,c,d,四颗子树的黑高是相同的，调整完之后，依旧是相同的，跟p的兄弟节点的黑高只差p这一个黑色节点~嗯，很满足条件5了，其他的条件就更加满足了。

1） 叔父节点为红，进行如下变换：

这样变换的话，节点G（包含）的性质5得以保存，但是，其变为红色，若其父节点为红色，可能违反性质4，这时，我们就要把当前节设置为祖父节点，进行新一轮的迭代。最终，不要忘了设置根节点的颜色为黑色哦，因为如果一直回溯的话，是有可能将根节点回溯为红色，而违反性质2的哈~

代码如下：

struct RB_tree_node *Get_Sibling(struct RB_tree_node *cur){
    if( cur->parent == NULL) return NULL;
    if( cur == cur->parent->lchild) return cur->parent->rchild;
    else return cur->parent->lchild;
}
struct RB_tree_node *Get_Uncle(struct RB_tree_node *cur){
    if(cur->parent == NULL) return NULL;
    else return(Get_Sibling(cur->parent));
}
void insert_fix( struct RB_tree_node *cur){
    while(cur->parent != NULL && cur->parent->color == false){
        if(cur->parent == cur->parent->parent->lchild){
            struct RB_tree_node *uncle = Get_Uncle(cur);
            if(uncle != NULL && uncle->color == false){
                cur->parent->color = true;
                uncle->color = true;
                cur->parent->parent->color = false;
                cur = cur->parent->parent;
            }
            else{
                if(cur == cur->parent->rchild){//内插，需要多一步旋转
                    Left_Rotate(cur->parent);
                    cur=cur->lchild;
                }
                //外插情况
                cur->parent->color = true;
                cur->parent->parent->color = false;
                Right_Rotate(cur->parent->parent);
            }
        }else{//父节点是祖节点的右孩子
            struct RB_tree_node *uncle = Get_Uncle(cur);
            if(uncle != NULL && uncle->color == false){
                cur->parent->color = true;
                uncle->color = true;
                cur->parent->parent->color = false;
                cur = cur->parent->parent;
            }
            else{
                if(cur == cur->parent->lchild){//内插，需要多一步旋转
                    Right_Rotate(cur->parent);
                    cur=cur->rchild;
                }
                //外插情况
                cur->parent->color = true;
                cur->parent->parent->color = false;
                Left_Rotate(cur->parent->parent);
            }
        }
    }
    root->color = true;
}
void insert(int val){
    struct RB_tree_node *cur = new RB_tree_node(val);
    if( root == NULL){
        cur->color = true; root = cur; return;
    }
    struct RB_tree_node *x = root, *y;
    while(x != NULL){
        y=x;
        if (val < x->val) x = x->lchild;
        else x = x->rchild;
    }
    if( val < y->val) y->lchild = cur;
    else y->rchild = cur;
    cur->parent = y;
    if( y->color == false)insert_fix(cur);
}

之后就可以写个数组，插入进去试一试了哈~
不足之处，还望大家不吝赐教~~~