[数据结构与算法]红黑树（Red Black Tree）（C语言实现、200行精简版）

红黑树

红黑树（Red Black Tree）是一种自平衡的二叉搜索树，与$AVL$树类似，在其上进行的插入、删除、查找操作的平均时间复杂度均为$O(logn)$。

但与$AVL$树不同的是，红黑树的平衡不是非常严格的平衡（即左右子树高度差不超过1），它牺牲了部分平衡性来换取了插入、删除时的少量旋转操作。

一、关于红黑树的叶子结点：

? 红黑树特别区分了中间结点与叶子结点。在二叉搜索树中，叶子结点与中间结点一般不做区分，两者的区别仅在于有没有子结点（叶结点的子结点为$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条性质：

1. 结点非黑既红
2. 根结点是黑色
3. 叶子（NIL）结点是黑色
4. 红色结点下面接两个黑色结点（即有父子关系的两个结点不能均为红色）
5. 从任一结点出发，到其每个叶子结点的所有简单路径上的黑色结点的数量相同。（这个黑结点数量也被称为黑高）

基于这5个性质，红黑树能够保证从根结点到叶子结点最长深度不会超过最短深度的2倍，从而保证了红黑树的平衡性。

因为最长路径即为红黑交替出现，而最短路径即为全部为黑结点。又由于性质5，所以这两条路径上的黑色结点数目一定相同，根结点与叶结点均为黑色，最长路径上多出的红色结点数目一定不会多于黑色结点的数目。

也正因为红黑树平衡性是通过黑高来进行维护的，所以在其结点上不用存储树的高度（本质上红黑树也是通过树高(黑高)维护平衡的）。

三、学习诀窍

• 插入：

1. 理解红黑树的插入调整，要站在祖父结点向下进行调整
2. 插入调整，主要就是为了解决双红情况
3. 新插入的结点一定是红色。插入黑色结点一定会产生冲突，违反性质5，插入红色结点，不一定产生冲突

• 删除：

1. 理解红黑树的删除调整，要站在父结点向下进行调整
2. 删除红色结点不会对树的平衡产生影响
3. 删除度为1的黑色结点，可以把其孤儿子树挂到父结点上，并把孤儿子树根结点染黑（度为1的黑色节点，唯一子孩子，一定是红色）
4. 删除度为2的黑色结点，可以把其转换成删除度为1或度为0的情况
5. 删除度为0的结点会产生双重黑NIL结点。删除调整，主要就是为了干掉双重黑

• 整体动态感：

1. 把每一种情况，想象成一棵大的红黑树中的局部子树
2. 局部调整的时候，为了不影响全局，调整前后的路径上黑色结点数量相同

四、插入调整策略

• 情况一：叔叔结点为红色的时候，修改三元组小帽子，改成红黑黑。(回溯阶段解决冲突的祖父结点一定是黑色）

• 情况二：叔叔结点为黑色的时候，参考 $AVL$ 树的失衡情况，分成 $LL,LR,RL,RR$, 先参考 $AVL$ 树的旋转调整策略，然后再修改三元组的颜色，有两种调整策略：红色上浮，红色下沉。

红色上浮：可能会导致与父结点冲突

红色下沉：可能会导致与新插入的子结点冲突

分析下图：

1、双红结点下还有其它结点说明此图发生在插入之后的回溯阶段（要想象成一个大红黑树的其中一小部分）

2、$LL$失衡情况下结点的确定性：

1. $20$结点（祖父）确定为黑色

   2. $16、10$结点（$LL$失衡）确定为红色
   3. 因为是情况二，所以$25$（叔叔结点）为黑色，那么$8，12，18$都存在并且都为黑色(黑高)。如果叔叔结点为$NIL$结点，其它三个结点也都为$NIL$结点（也是黑色）
   4. 此图中只有$19$号结点为特例结点（此情况下不必然存在）

注意：两大类情况，包含 $8$ 种小情况

五、删除调整策略

• 删除度为$1$的黑色结点

删除度为$1$的黑色结点，可以把其孤儿子树挂到父结点上，并把孤儿子树根结点染黑（度为$1$的黑色节点，唯一子孩子，一定是红色）

• 删除度为$0$的黑色结点

当删除度为$0$的黑色结点时会产生双重黑结点（删除调整主要是为了干掉双重黑）

• 干掉双重黑的三种情况(策略)：

情况一：双重黑结点的兄弟结点是黑色，兄弟结点下面的两个子结点也是黑色

调整策略：父结点增加一重黑色，双重黑与兄弟结点分别减少一重黑色，从而使双重黑结点向上传递

如果$43$号结点为红色，那么向上传递后$43$号变为普通黑(即干掉了双重黑)

如果$43$号结点为黑色并且又是整颗红黑树的根结点，那么将其染发成普通黑结点(即干掉了双重黑)

如果$43$号结点为黑色，又不是根结点，那么继续向上传递，有可能过程中通过其它情况干掉双重黑。

情况二：双重黑结点的兄弟结点是黑色，兄弟结点下面存在红色子结点

（一）$RR$失衡

$R$（兄弟）$R$（右子结点）为红色

调整策略：左旋（旋转后直接干掉双重黑），新根改成原根的颜色，将新根的两个子结点，改成黑色

策略分析：

旋转前分析$RR$失衡下结点的确定性：因为$RR$失衡，所以$28，51，72$号结点的颜色确定。又因为$72$号结点确定为红色，所以它的两个子孩子$64，85$都必为黑色。$48$号的颜色不确定，当前$48$为黑色，假设$48$号结点为红色，$42$号结点为黑色，再给$48$加个黑色右孩子结点，$RB$树依然平衡。$38$号结点的颜色也不确定，当前$38$号结点为红色，假设为黑色，只需要在$89$号结点的左子树中加一层黑色结点，$RB$树依然平衡。最后$29，42，73$号结点可有可无，即使存在颜色也不确定，可以是一个庞大的子树根。

旋转后如何调整颜色并保证不失衡：首先看$48$号结点旋转后接到$38$号结点下边，又因为$48$号结点的颜色不确定，也就是说$48$号结点有可能是红色，为了不发生冲突，只能将38号结点改成黑色。又因为旋转前从原根结点（$38$号）到每个$NIL$结点路径上的黑色结点数都为$2$，为维护黑高性质，旋转后每条路径上黑色结点数量也应为$2$。但是如果将$38$号结点改为黑色，那么左侧路径上黑色结点数量变为$3$，所以要把51号结点变为红色来保证左侧路径中黑色结点数量依旧为$2$。$51$变红后，右侧路径上黑色结点数量变为$1$，为保证右侧路径黑色结点数量依旧为$2$，还要将72号结点变为黑色。此时在$38$号结点为红色时，无论$48$号结点颜色为何，该调整策略都不会产生冲突($51$变红，$38，72$变黑)。但是$38$号结点的颜色不确定也有可能为黑色，所以最终的完美调整策略是左旋，新根改成原根的颜色，将新根的两个子结点，改成黑色（51号变为38的颜色，$38，72$号变黑）

（二）$RL$失衡

$R$（兄弟）$L$（左子结点）为红色，右子结点不为红色

调整策略：通过小右旋（对调新根与原根颜色）转换成$RR$失衡

策略分析：

旋转前分析$RR$失衡下结点的确定性：因为$RL$失衡，所以72，51，85号结点的颜色确定。因为51号结点确定为红色，那么48，64号结点确定为黑色。42，87号结点不确定存在，即使存在颜色也不确定，有可能是一个庞大子树的根。

旋转后如何调整颜色并保证不失衡：旋转前每个路径上两个黑色结点，旋转后左侧路径上一个黑色结点，所以要把51号结点染成黑色，来保证左侧路径。这时右侧路径变成了三个黑色结点，此时要把85号结点染成红色，来保证右侧路径。所以最终策略是，原根和新根对调颜色。

（三）$LL$失衡

同理$RR$失衡

（四）$LR$失衡

同理$RL$失衡

情况三：双重黑结点的兄弟结点是红色

兄弟结点红色，通过旋转，转变成兄弟结点是黑色的情况

六、代码演示

1. 插入调整，发正在递归的回溯阶段

2. 插入调整代码中，使用 $goto$ 语句，$8$行代码，变成了$4$行

3. 处理根结点一定是黑色，通过代码封装，$insert?>\_\_insert$（染发）

4. 进行 $LR/RL$ 类型判断的时候，不能判断$LL/RR$子树是否为黑色，$LL/RR$子树有可能是 $NIL$ 节点，在某些特殊情况下(删除调整回溯阶段)，读到的颜色可能是双重黑(程序中$NIL$结点通用)，取而代之的判断方法就是【$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;
}