C语言——红黑树

性质
红黑树的节点包括5个属性：color、key、left、right、parent。如果一个节点没有子节点或者父节点，则该节点响应的指针属性的值为nil，把这些nil视为指向二叉搜索树的叶节点的指针，而把待关键字的节点视为树的内部节点。

红黑树必须满足下列五个条件：

• 每个节点或是红色，或是黑色。
• 根节点是黑色的
• 每个叶节点是黑色的
• 如果一个节点是红色的，则它的两个子节点都是黑色的
• 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点（简称黑高）

为了便于处理红黑树的边界条件，可以使用一个哨兵来代表NIL，哨兵的结构与红黑树的节点结构相同，color为黑色，其他属性任意设置。

红黑树

红黑树是一种特殊的二叉搜索树，它的插入和删除更加复杂。因为红黑树必须满足上面的五个条件，插入与删除有可能会破坏上面的性质，所以在插入和删除之后需要调整红黑树，改变树中某些节点的颜色以及指针结构。

颜色容易改变，而指针结构不容易改变，这时我们使用旋转来调整指针结构。
旋转分为左旋和右旋，通常是以关键字小的节点为轴心，轴心到关键字大的节点的路径为轴旋转。（希腊字母表示的是任意子树）x,y不等于nil。

旋转

左旋代码：（右旋代码读者可以自己尝试写写）

左旋示例

void left_rotate(RB_Tree *T,TNode *x){
    TNode *y = x->right;
    x->right = y->left;
    if(y->left!=T->nil){
        y->left->parent = x;
    }

    y->parent = x->parent;
    if(x->parent == T->nil){
        T->root = y;
    }else if(x==x->parent->left){
        x->parent->left = y;
    }else{
        x->parent->right = y;
    }

    y->left = x;
    x->parent = y;
}

插入：
插入的节点的颜色为红色（因为如果插入的是黑色，那么会改变黑高，违背性质5）

• 首先，找出插入的位置，并插入。
• 然后调整红黑树。

调整：
如果插入的父节点是黑色，显然是不用调整，所以我们只需要考虑插入位置的父节点的颜色是红色的情况。
插入情况导致冲突情况有如下三种，如方框所示，z节点是插入位置（有人可能会问不是应该插在叶节点（nil）位置？这里主要是为了说明三种情况的转换，我们可以吧方框下面部分当成nil，这里只考虑添加在爷节点的左子树的情况，右子树的情况与左子树完成相反，但对称）

情况一：插入节点的父节点和叔节点均为红色。
调整：此时，我们只需把父节点和叔节点的颜色改为黑色，父节点的父节点（简称爷节点【捂脸】）的颜色改为红色（不改变性质5）。（显然的，如果爷节点的父节点为黑色，则调整完成）

情况一

情况二：插入节点的叔节点为黑色，且插入节点是父节点的右孩子节点。
调整：以插入点的父节点为轴心左旋（显然，调整未完成）

情况二

情况三：插入节点的叔节点为黑色，且插入节点是父节点的左孩子节点。
调整：以插入点的父节点为轴心，右旋（显然，必然完成）

情况三

对于这三种情况的转换。

• 情况一有可能转换为情况二，也有可能调整结束。
• 情况二转换为情况三
• 情况三调整后完车。
  如上面的三张图所展示的情况，调整完成情况如下：
  完成
  代码：

void rb_insert_fixup(RB_Tree *T,TNode *z){
    while(z->parent->color == RED){
         //插入位置在爷节点的左子树
        if(z->parent==z->parent->parent->left){
            TNode *y = z->parent->parent->right;
            if(y->color==RED){
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                y->color = BLACK;
                z=z->parent->parent;
            }else if(z == z->parent->right){
                z = z->parent;
                left_rotate(T,z);
            }else{
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                right_rotate(T,z->parent->parent);
            }   
        }else{
            TNode *y = z->parent->parent->left;
            if(y->color==RED){
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                y->color = BLACK;
                z=z->parent->parent;
            }else if(z == z->parent->left){
                z = z->parent;
                right_rotate(T,z);
            }else{
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                left_rotate(T,z->parent->parent);
            }   
        }
    }
    T->root->color = BLACK;
}

void rb_insert(RB_Tree *T,TNode *z){

    TNode *y = T->nil;
    TNode *x = T->root;
    //找插入位置
    while(x!=T->nil){
        y = x;
        if(z->key<y->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }

    z->parent = y;

    if(y==T->nil){
        T->root = z;
        T->root->parent = T->nil;
    }else if(z->key<y->key){
        y->left = z;
    }else{
        y->right = z;
    }

    z->left = T->nil;
    z->right = T->nil;
    z->color = RED;
    //调整
    rb_insert_fixup(T,z);
}

删除：
删除相对于插入来说更加复杂……

首先设计一个删除调用的子过程（用一棵树代替另一棵树的子树）(u是被替代的子树 )

void rb_translate(RB_Tree *T,TNode *u,TNode *v){
    if(u->parent==T->nil){
        T->root = v;
    }else if(u == u->parent->left){
        u->parent->left = v;
    }else{
        u->parent->right = v;
    }
    v->parent = u->parent;
}

删除节点的三种情况，前面的二叉搜索树已经提到过了，这里主要是讲删除后，红黑树的调整。

我们假设有一个节点y，但被删除的节点z的子节点少于2个时，让y成为z（所谓成为z，即是把z的颜色传递给y，并且保持二叉树性质不变，这一点很重要）。当大于2时，y应当是z的后继节点（即z的右节点或是右节点的最左子代）。y有可能导致红黑树性质的破坏，所以，应该需要记录原本y节点的颜色（y-original-color）。此外，还需要节点x来记录原本y的唯一子节点（x可能为nil）。

删除节点情况

如果原本y颜色是红色，显然是不会改变红黑树性质（y不是根节点）；反之，则会。
当y替代了z后，因为z被删除，y替代上去，如果原本y的颜色是红色，那么原本y所在的节点的子树上的黑高不变，而y替代z后，以z为根节点的子树黑高也不变，没有影响到红黑树的性质。所以这里只讨论原本y颜色是黑色情况。

在原本y颜色是黑色前提下：

• 如果z是根节点，并且z子节点少于2，那么删除z后，节点x所在位置是根节点，无论x的颜色是什么情况，只要将x颜色设为黑色即可调整完成。

• 当x所在位置不是根节点时，此时，以x的父节点为根的树，x所在的子树的黑高显然比树的另一颗子树小1。显然违背了性质5 。此时，如果x的颜色是红色，那么我们只要将x的颜色设为黑色，即可将黑高+1，并且不改变红黑树的其他性质，则调整完成。

而如果x的颜色为黑色，那么可能会出现下面的四种情形：（这里只讨论x所在子树为左子树的情况，右子树与左子树对称相反）
（黑高：从某个节点出发（不含该节点），到达一个叶节点的任意一条简单路径上的黑色节点（必须是内部节点）个数）

• 情况一：x的兄弟节点C为红色，那么x（B节点）的父节点A为黑色。（假设A到B所在子树的后代的黑高为n，那么A到另一颗子树后代的黑高为n+1，下面情况依旧是）
  解决：将C节点的颜色传递给A，C颜色设为黑，以A为轴心，AC为轴，左旋。
  此时，A到叶节点的黑高情况跟上述一样，仍需要调整。情况一转变为下面三种情形之一。

情况一 左旋后

x（B）的兄弟节点（C）为黑色，那么x父节点（A）可黑可红，可分三种情形。

• 情况二：C的孩子节点均为黑色。
  解决，将C设为红色。如果A的颜色为红色，将A的颜色改为黑色，若A为黑色，则不变。则调整完成（我们这里强调将A标志为x，是为了方便循环时结束循环）。
  其实到了这里我们不难发现，我们都是在平衡A的黑高。

  
  情况二和解决后图

• 情况三：C的右孩子节点为黑，左孩子节点为红。
  解决：将C的左孩子节点D与C的颜色互换，以D为轴心，DC为轴，右旋。右旋后，A的黑高不变，未调整完成，转移到情况四。

  
  情况三

• 情况四：C的右孩子为红，左孩子可红可黑。
  解决：将A和C颜色互换，C的右孩子E颜色设为黑，以A为轴心，AC为轴，左旋。我们可以看到，将A、C颜色互换并右旋后，以C为根的树到B所在子树后代叶节点的黑高+1，即为n+1，而C的到另一颗子树后代的叶节点的黑高（n+1）-1，即n；但由于E节点为红色，我们改变E颜色为黑时，不改变E到叶节点的黑高，而此时C到该子树后代子节点的黑高+1，即n+1.
  这里标志x=（母）树根，是为了方便退出循环所用。

  
  情况四

对于x是x父节点的右孩子的情况，是与x是x父节点的左孩子的情况一样，只不过把对应的左改成右，右变为左。
代码实现：

//找后继
TNode* tree_min(TNode* R,RB_Tree T){
    while(R->left!=T.nil){
        R = R->left;
    }
    return R;
}
//修复删除节点z后的红黑树性质
void rb_delete_fixup(RB_Tree *T,TNode *x){
    while(x!=T->root && x->color == BLACK){
        //x是父节点的左孩子
        if(x==x->parent->left){
            //w是x的兄弟节点
            TNode *w = x->parent->right;
            //情况一
            if(w->color == RED){
                w->color = BLACK;
                w->parent->color = RED;
                left_rotate(T,x->parent);
                w = x->parent->right;
            }
            //情况二
            if(w->left->color==BLACK && w->right->color == BLACK){
                w->color = BLACK;
                x = x->parent;
            }else if(w->right->color == BLACK){
             //情况三
                w->left->color = BLACK;
                w->color = RED;
                right_rotate(T,w);
                w = x->right;
            }else{
            //情况四
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                left_rotate(T,x->parent);
                x = T->root;
            }   
        }else{
    //x是父节点的右孩子
            TNode *w = x->parent->left;
            if(w->color == RED){
                w->color = BLACK;
                w->parent->color = RED;
                left_rotate(T,x->parent);
                w = x->parent->left;
            }

            if(w->right->color==BLACK && w->left->color == BLACK){
                w->color = BLACK;
                x = x->parent;
            }else if(w->left->color == BLACK){
                w->right->color = BLACK;
                w->color = RED;
                left_rotate(T,w);
                w = x->left;
            }else{
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                right_rotate(T,x->parent);
                x = T->root;
            }
        }
    }
    x->color = BLACK;
}
void rb_delete(RB_Tree *T,TNode* z){
    TNode* y = z;
    TNode* x = T->nil;
    //记录原本y的颜色
    Color y_original_color = y->color;

    if(z->left==T->nil){
        x = z->right;
        rb_translate(T,z,z->right);
    }else if(z->right==T->nil){
        x = z->left;
        rb_translate(T,z,z->left);
    }else{
        y = tree_min(z->right,*T);
        y_original_color = y->color;
        x = y->right;
        if(y->parent == z){
            x->parent = y;
        }else{
            rb_translate(T,y,y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        rb_translate(T,z,y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    if(y_original_color==BLACK){
        rb_delete_fixup(T,x);
    }
}

测试代码：

//中序遍历
void rb_in_order_traverse(RB_Tree T,TNode* R){
    if(R!=T.nil){
        rb_in_order_traverse(T,R->left);
        printf("%d is red:%d \n",R->key ,R->color);
        rb_in_order_traverse(T,R->right);
    }
}
//由于这里使用的是深度优先遍历，很难体现出树的形状，建议读者用广度优先遍历（可利用队列或者栈实现）
int main(int argc, char const *argv[])
{
    RB_Tree T;
    init_rb_tree(&T);
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i){
        TNode *z = (TNode*)malloc(sizeof(TNode));
        KeyType key = rand()%100;
        printf("key==%d\n",key );
        z->key = key;
        rb_insert(&T,z);
    }
    rb_in_order_traverse(T,T.root);
    printf("\n");

    rb_delete(&T,tree_min(T.root,T));
    rb_in_order_traverse(T,T.root);
    return 0;
}