红黑树（Red Black Tree）是一种自平衡的二叉搜索树，与 A V L AVL AVL树类似，在其上进行的插入、删除、查找操作的平均时间复杂度均为 O ( l o g n ) O(logn) O(logn)。
但与 A V L AVL AVL树不同的是，红黑树的平衡不是非常严格的平衡（即左右子树高度差不超过1），它牺牲了部分平衡性来换取了插入、删除时的少量旋转操作。
红黑树特别区分了中间结点与叶子结点。在二叉搜索树中，叶子结点与中间结点一般不做区分，两者的区别仅在于有没有子结点（叶结点的子结点为 N U L L NULL NULL，视为没有子结点）。虽然在红黑树中也可以这样，但是为了方便解释与实现，一般对叶子结点进行了区分：叶子结点不存储数据，只是充当树在此结束的标志。
Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init_NIL() {
NIL->color = 1;
NIL->key = 0;
NIL->lchild = NIL->rchild = NIL;
return ;
}
__attribute__介绍
__attribute__可以设置函数属性(Function Attribute)、变量属性(Variable Attribute)和类型属性(Type Attribute)。__attribute__前后都有两个下划线，并且后面会紧跟一对原括弧，括弧里面是相应的__attribute__参数
__attribute__语法格式为：__attribute__ ( ( attribute-list ) )
若函数被设定为constructor属性，则该函数会在main（）函数执行之前被自动的执行。
类似的，若函数被设定为destructor属性，则该函数会在main（）函数执行之后或者exit（）被调用后被自动的执行。
基于这5个性质，红黑树能够保证从根结点到叶子结点最长深度不会超过最短深度的2倍，从而保证了红黑树的平衡性。
因为最长路径即为红黑交替出现，而最短路径即为全部为黑结点。又由于性质5，所以这两条路径上的黑色结点数目一定相同，根结点与叶结点均为黑色，最长路径上多出的红色结点数目一定不会多于黑色结点的数目。
也正因为红黑树平衡性是通过黑高来进行维护的，所以在其结点上不用存储树的高度（本质上红黑树也是通过树高(黑高)维护平衡的）。
红色上浮：可能会导致与父结点冲突
红色下沉：可能会导致与新插入的子结点冲突
分析下图：
1、双红结点下还有其它结点说明此图发生在插入之后的回溯阶段（要想象成一个大红黑树的其中一小部分）
2、 L L LL LL失衡情况下结点的确定性：
20 20 20结点（祖父）确定为黑色
注意：两大类情况，包含 8 8 8 种小情况
删除度为 1 1 1的黑色结点，可以把其孤儿子树挂到父结点上，并把孤儿子树根结点染黑（度为 1 1 1的黑色节点，唯一子孩子，一定是红色）
当删除度为 0 0 0的黑色结点时会产生双重黑结点（删除调整主要是为了干掉双重黑）
情况一：双重黑结点的兄弟结点是黑色，兄弟结点下面的两个子结点也是黑色
调整策略：父结点增加一重黑色，双重黑与兄弟结点分别减少一重黑色，从而使双重黑结点向上传递
如果 43 43 43号结点为红色，那么向上传递后 43 43 43号变为普通黑(即干掉了双重黑)
如果 43 43 43号结点为黑色并且又是整颗红黑树的根结点，那么将其染发成普通黑结点(即干掉了双重黑)
如果 43 43 43号结点为黑色，又不是根结点，那么继续向上传递，有可能过程中通过其它情况干掉双重黑。
情况二：双重黑结点的兄弟结点是黑色，兄弟结点下面存在红色子结点
（一） R R RR RR失衡
R R R（兄弟） R R R（右子结点）为红色
调整策略：左旋（旋转后直接干掉双重黑），新根改成原根的颜色，将新根的两个子结点，改成黑色
策略分析：
旋转前分析 R R RR RR失衡下结点的确定性：因为 R R RR RR失衡，所以 28 ， 51 ， 72 28，51，72 28，51，72号结点的颜色确定。又因为 72 72 72号结点确定为红色，所以它的两个子孩子 64 ， 85 64，85 64，85都必为黑色。 48 48 48号的颜色不确定，当前 48 48 48为黑色，假设 48 48 48号结点为红色， 42 42 42号结点为黑色，再给 48 48 48加个黑色右孩子结点， R B RB RB树依然平衡。 38 38 38号结点的颜色也不确定，当前 38 38 38号结点为红色，假设为黑色，只需要在 89 89 89号结点的左子树中加一层黑色结点， R B RB RB树依然平衡。最后 29 ， 42 ， 73 29，42，73 29，42，73号结点可有可无，即使存在颜色也不确定，可以是一个庞大的子树根。
旋转后如何调整颜色并保证不失衡：首先看 48 48 48号结点旋转后接到 38 38 38号结点下边，又因为 48 48 48号结点的颜色不确定，也就是说 48 48 48号结点有可能是红色，为了不发生冲突，只能将38号结点改成黑色。又因为旋转前从原根结点（ 38 38 38号）到每个 N I L NIL NIL结点路径上的黑色结点数都为 2 2 2，为维护黑高性质，旋转后每条路径上黑色结点数量也应为 2 2 2。但是如果将 38 38 38号结点改为黑色，那么左侧路径上黑色结点数量变为 3 3 3，所以要把51号结点变为红色来保证左侧路径中黑色结点数量依旧为 2 2 2。 51 51 51变红后，右侧路径上黑色结点数量变为 1 1 1，为保证右侧路径黑色结点数量依旧为 2 2 2，还要将72号结点变为黑色。此时在 38 38 38号结点为红色时，无论 48 48 48号结点颜色为何，该调整策略都不会产生冲突( 51 51 51变红， 38 ， 72 38，72 38，72变黑)。但是 38 38 38号结点的颜色不确定也有可能为黑色，所以最终的完美调整策略是左旋，新根改成原根的颜色，将新根的两个子结点，改成黑色（51号变为38的颜色， 38 ， 72 38，72 38，72号变黑）
（二） R L RL RL失衡
R R R（兄弟） L L L（左子结点）为红色，右子结点不为红色
调整策略：通过小右旋（对调新根与原根颜色）转换成 R R RR RR失衡
策略分析：
旋转前分析 R R RR RR失衡下结点的确定性：因为 R L RL RL失衡，所以72，51，85号结点的颜色确定。因为51号结点确定为红色，那么48，64号结点确定为黑色。42，87号结点不确定存在，即使存在颜色也不确定，有可能是一个庞大子树的根。
旋转后如何调整颜色并保证不失衡：旋转前每个路径上两个黑色结点，旋转后左侧路径上一个黑色结点，所以要把51号结点染成黑色，来保证左侧路径。这时右侧路径变成了三个黑色结点，此时要把85号结点染成红色，来保证右侧路径。所以最终策略是，原根和新根对调颜色。
（三） L L LL LL失衡
同理 R R RR RR失衡
（四） L R LR LR失衡
同理 R L RL RL失衡
情况三：双重黑结点的兄弟结点是红色
兄弟结点红色，通过旋转，转变成兄弟结点是黑色的情况
插入调整，发正在递归的回溯阶段
插入调整代码中，使用 g o t o goto goto 语句， 8 8 8行代码，变成了 4 4 4行
处理根结点一定是黑色，通过代码封装， i n s e r t − > _ _ i n s e r t insert->\_\_insert insert−>__insert（染发）
进行 L R / R L LR/RL LR/RL 类型判断的时候，不能判断 L L / R R LL / RR LL/RR子树是否为黑色， L L / R R LL/RR LL/RR子树有可能是 N I L NIL NIL 节点，在某些特殊情况下(删除调整回溯阶段)，读到的颜色可能是双重黑(程序中 N I L NIL NIL结点通用)，取而代之的判断方法就是【 L L LL LL 子树不是红色】。
/*************************************************************************
> File Name: RB_tree.c
> Author: Luzelin
************************************************************************/
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int color, key;
struct Node *lchild, *rchild;
} Node;
Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init_NIL() {
NIL->color = 1;
NIL->key = 0;
NIL->lchild = NIL->rchild = NIL;
return ;
}
Node* GetNewNode(int val) {
Node *s = (Node *)malloc(sizeof(Node));
s->color = 0;
s->key = val;
s->lchild = s->rchild = NIL;
return s;
}
#define LC lchild->color
#define RC rchild->color
int has_red_child(Node *root) {
return (root->LC == 0 || root->RC == 0 ? 1 : 0);
}
Node* L_rotate(Node *root) {
Node *p = root->rchild;
root->rchild = p->lchild;
p->lchild = root;
return p;
}
Node* R_rotate(Node *root) {
Node *p = root->lchild;
root->lchild = p->rchild;
p->rchild = root;
return p;
}
//站在祖父节点 调整插入失衡(处理双红情况)
Node* Balance_Insert(Node *root) {
/***子结点都为黑色***/
//如果当前节点的两个子结点没有红色，那么就不可能发生儿孙冲突
if (!has_red_child(root)) return root;
//flag 0 平衡 1 左子树失衡 2 右子树失衡
int flag = 0;
//if (root->LC == 0 && root->RC == 0) goto end;
/***子结点都为红色***/
//如果当前节点的两个子结点都为红色，并且还存在红色孙子节点(失衡态)，此时红色上浮。
//分析，此时当前节点必为黑色，并且最多只有一个孙子节点可能是红色
if (root->LC == 0 && root->RC == 0) {
if (has_red_child(root->lchild) || has_red_child(root->rchild)) goto end;
}
/***子结点一黑一红***/
//如果失衡找到失衡侧
if (root->LC == 0 && has_red_child(root->lchild)) flag = 1;
if (root->RC == 0 && has_red_child(root->rchild)) flag = 2;
if (flag == 0) return root; //平衡
//分情况处理失衡态
if (flag == 1) {
if (root->lchild->RC == 0) root->lchild = L_rotate(root->lchild);
root = R_rotate(root);
} else {
if (root->rchild->LC == 0) root->rchild = R_rotate(root->rchild);
root = L_rotate(root);
}
//红色上浮
end:
root->color = 0;
root->LC = root->RC = 1;
return root;
}
Node* __Insert(Node *root, int val) {
if (root == NIL) return GetNewNode(val);
if (val < root->key) root->lchild = __Insert(root->lchild, val);
else if (val > root->key) root->rchild = __Insert(root->rchild, val);
return Balance_Insert(root);
}
Node* Insert(Node *root, int val) {
root = __Insert(root, val);
//封装染发
root->color = 1;
return root;
}
int precursor(Node *root) {
root = root->lchild;
while (root->rchild != NIL) root = root->rchild;
return root->key;
}
//站在父结点 调整删除失衡(处理双重黑)
Node* Balance_Erase(Node *root) {
//如果当前节点的子结点没有双重黑则平衡
/***子结点没有双重黑***/
if (root->LC != 2 && root->RC != 2) return root;
//存在双重黑节点，并且其兄弟节点为红色
/***子结点中存在双重黑，并且兄弟节点为红色***/
if (has_red_child(root)) {
root->color = 0; //原根红
int flag = 0;
//红色兄弟在左侧，右旋(向双重黑方向)
if (root->LC == 0) {
root = R_rotate(root);
flag = 1;
} else {
//红色兄弟右侧，左旋(向双重黑方向)
root = L_rotate(root);
flag = 2;
}
root->color = 1; //新根黑
//因为旋转之后双重黑节点到了当前节点的孙子节点的位置，所以需要向下一步走(站在父结点处理删除失衡)
if (flag == 1) root->rchild = Balance_Erase(root->rchild);
if (flag == 2) root->lchild = Balance_Erase(root->lchild);
return root;
}
//存在双重黑节点，并且其兄弟节点为黑色，兄弟节点的两个子结点也都为黑色(父结点+1重黑，两个子结点-1重黑)
/***子结点中存在双重黑，兄弟是黑色，兄弟的孩子都是黑色***/
if ((root->LC == 1 && !has_red_child(root->lchild)) || (root->RC == 1 && !has_red_child(root->rchild))) {
root->color += 1;
root->LC -= 1;
root->RC -= 1;
return root;
}
//存在双重黑节点，并且其兄弟节点为黑色，兄弟节点的子结点中存在红色节点
/***子结点中存在双重黑，兄弟是黑色，兄弟有红色孩子***/
if (root->RC == 2) {
if (root->lchild->LC != 0) {
//LR失衡
root->LC = 0; //原红
root->lchild = L_rotate(root->lchild);
root->LC = 1; //新黑
}
root = R_rotate(root); //LL失衡
root->color = root->RC; //新根颜色等于原根颜色
root->rchild->RC = 1; //干掉双重黑
} else {
if (root->rchild->RC != 0) {
//RL失衡
root->RC = 0; //原红
root->rchild = R_rotate(root->rchild);
root->RC = 1; //新黑
}
root = L_rotate(root); //RR失衡
root->color = root->LC; //新根颜色等于原根颜色
root->lchild->LC = 1; //干掉双重黑
}
root->LC = root->RC = 1; //两个子结点变黑色
return root;
}
Node* __Erase(Node *root, int val) {
if (root == NIL) return root;
if (val < root->key) root->lchild = __Erase(root->lchild, val);
else if (val > root->key) root->rchild = __Erase(root->rchild, val);
else {
if (root->lchild == NIL || root->rchild == NIL) {
Node *p = (root->lchild != NIL ? root->lchild : root->rchild);
p->color += root->color;
free(root);
return p;
} else {
int k = precursor(root);
root->key = k;
root->lchild = __Erase(root->lchild, k);
}
}
return Balance_Erase(root);
}
Node* Erase(Node *root, int val) {
root = __Erase(root, val);
//封装染发
root->color = 1;
return root;
}
void output(Node *root) {
if (root == NIL) return ;
output(root->lchild);
printf("%d %d %d %d\n", root->key, root->color, root->lchild->key, root->rchild->key);
output(root->rchild);
return ;
}
int main() {
Node *root = NIL;
int x, y;
while (scanf("%d%d", &x, &y) != EOF) {
if (x == 1) root = Insert(root, y);
else if (x == 2) root = Erase(root, y);
else if (x == 3) output(root);
}
return 0;
}