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;
}
