红黑树（含图解和代码参考）_红黑树结构代码

1. 红黑树的结构定义
2. 红黑树的学习诀窍
3. 红黑树的学前思考
4. 红黑树的插入调整情况
5. 红黑树的删除调整情况
6. 红黑树的代码演示

1.红黑树——结构定义

五个条件：

（1）每个结点非黑即红

（2）根结点是黑色

（3）叶结点(NIL)是黑色

（4）如果一个结点是红色，则它的两个子结点都是黑色的（红色和红色不能挨着）

（5）从根结点出发到所有叶结点路径上，黑色结点数量相同

2.红黑树——学习诀窍

（1）插入调整站在==祖父结点==看

（2）删除调整站在==父结点==看

（3）插入（2）和删除（3）的情况处理一共总结为五种

（4）理解调整策略时，时刻记住黑色结点数量调整前后相同（对整体不影响）

3.红黑树——学前思考

qes1：红黑树中，最长路径和最短路径长度的关系？

qes2：新插入的结点是什么颜色的？红色，黑色？

ans2：红色。插入黑色一定失衡，插入红色不一定失衡。

---

4.插入调整情况

（1）情况一：叔叔是红色——最简单

（四种情况，x也可以在图示中的另外三个兄弟结点的位置）

（2）情况二：叔叔是黑色（LL、LR）

LL型为例：

①红黑黑：红色上浮

②黑红红：红色下沉

LR型：先进行小左旋，不需要进行颜色调整，再进行大右旋，最后才进行颜色调整（红色上浮、红色下沉）

5.删除调整

情况1：删除度为2的红色结点

情况2：删除度为2的黑色结点

（1）和（2）转换为删除度为1和度为0的情况，不另做讨论。

情况3：删除度为1的红色结点

不存在度为1的红色结点。因为从根结点出发到所有叶结点路径上，黑色结点数量相同。

情况4：删除度为1的黑色结点

度为1的黑色结点有且只有一个红色子结点。（只有倒数第二层会出现度为1的黑色结点）直接把红色子结点变为黑色结点即可。

情况5：删除度为0的红色结点

直接删除。

情况6：删除度为0的黑色结点

影响平衡。因为从根结点出发到所有叶结点路径上，黑色结点数量相同，删除一个黑叶子结点时，另一个黑色叶子结点就会无处安放。被删除的黑色结点连接的NIL结点就会被记为双重黑色。

删除调整，主要就是解决由双重黑造成的不平衡

（1）删除调整一

brother结点为黑色且无红色子结点

（2）删除调整二

兄弟结点为黑且其同一侧的子结点是红色结点，RR类型

（3）删除调整三

brother结点为黑色且红色子结点不在同一侧，则为RL类型

（4）删除调整四

兄弟结点为红色结点

6.代码演示

#include<stdio.h>
#include <stdlib.h>

typedef struct Node{
        int key, color; //color 0: red, 1: black, 2: double black
        struct Node *lchild, *rchild;

} Node;

Node __NIL;//NIL映射到一个真实结点的地址
#define NIL (&__NIL)

__attribute__((constructor))
void init_NIL(){
    NIL->key = 0;
    NIL->color = 1;//红黑树中NIL结点是黑色
    NIL->lchild = NIL->rchild = NIL;
    return ;
}

Node *getNewNode(int key){
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->lchild = p->rchild = NIL;
    p->color = 0; //新插入结点默认是红色（插入黑色必定不平衡）
    return p;
}

//返回当前结点下面是否有红色结点
int has_red_child(Node *root){
    return root->lchild->color == 0 || root->rchild->color == 0;
}

//左旋
Node *left_rotate(Node *root){
    printf("left rotate: %d\n", root->key);
    Node *new_root = root->rchild; //新根结点=原根结点的右子结点
    root->rchild = new_root->lchild; //原根结点的右子结点=新根结点的左子结点
    new_root->lchild = root; //新根结点的左子结点=原根结点
    return new_root;
}

//右旋
Node *right_rotate(Node *root){
    printf("right_rotate: %d\n", root->key);
    Node *new_root = root->lchild; //新根结点=原根结点的左子结点
    root->lchild = new_root->rchild; //原根结点的左子结点=新根结点的右子结点
    new_root->rchild = root; //新根结点的右子结点=原根结点
    return new_root;
}

const char *insert_maintain_type_str[] = {"insert type 1: change color", "insert type 2: LL", "insert type 2: LR", "insert type 2: RR", "insert type 2: RL"};

Node *insert_maintain(Node *root){
    if(!has_red_child(root)) return root; //如果当前结点的子结点没有红色的，就不会出现双红的情况
    //左（右）子树颜色是红色并且左（右）子树没有红色子孩子时没有冲突
    if(!(root->lchild->color == 0 && has_red_child(root->lchild)) &&
       !(root->rchild->color == 0 && has_red_child(root->rchild))) return root;

    //rotate
    int type = 0;
    if(root->rchild->color == 1){//右子树颜色是黑色，说明冲突发生在L（LL、LR）
        if(root->lchild->rchild->color == 0){ // LR类型
            root->lchild = left_rotate(root->lchild); //抓住左子树进行小左旋
            ++type;
        }
        ++type;
        root = right_rotate(root); //抓住根结点大右旋 LL
    } else if(root->lchild->color == 1){ //左子树的颜色是黑色，说明冲突发生在R（RR、RL）
        type = 2;
        if(root->rchild->lchild->color == 0){ //RL类型
            root->rchild = right_rotate(root->rchild); //抓住右子树进行小右旋
            ++type;
        }
        ++type;
        root = left_rotate(root); //抓住根结点大左旋 RR
    }

    printf("insert maintain type = %s\n", insert_maintain_type_str[type]);
    //上三角变成红黑黑
    root->color = 0;
    root->lchild->color = root->rchild->color = 1;
    return root;

}

Node *__insert(Node *root, int key){
    if(root == NIL) return getNewNode(key);
    if(root->key == key) return root;
    if(root->key > key) root->lchild = __insert(root->lchild, key);
    else root->rchild = __insert(root->rchild, key);
    return insert_maintain(root); //返回进行调整以后的根结点
}

Node *insert(Node *root, int key){
    root = __insert(root, key);
    root->color = 1; //保证根结点是黑色
    return root;
}

const char *erase_maintain_type_str[] = {
    "red 1(right) : change color",
    "red 2(left) : change color",
    "balck 1 : no red child", 
    "black 2 : LL",
    "black 2 : LR", 
    "black 2 : RR",
    "black 2 : RL"
};

//删除调整
Node *erase_maintain(Node *root){
    if(root->lchild->color != 2 && root->rchild->color != 2) return root; //左右子树都不是双重黑，直接return
    int type = 0;
    if(has_red_child(root)){ //如果当前结点下有红色子结点，就是双重黑结点的兄弟结点是红色
        root->color = 0; //原根结点改为红色
        if(root->lchild->color == 0){ //如果左侧的结点是红色
            root = right_rotate(root); //拉着当前根结点进行右旋，双黑结点就会在右子树上
        } else { //否则拉着根结点进行左旋，双黑结点就会在左子树上
            root = left_rotate(root);
            type  = 1;
        }
        root->color = 1; //旋转之后的新根结点改为黑色
        if(type) root->lchild = erase_maintain(root->lchild); //type是1，递归到左子树去进行删除调整
        else root->rchild = erase_maintain(root->rchild); //否则到右子树进行删除调整
        printf("brother is %s\n", erase_maintain_type_str[type]);
        return root;
    }

    //处理双黑结点的兄弟结点是黑色且无红色子结点（删除调整一）
    if((root->lchild->color == 1 && !has_red_child(root->lchild)) ||
       (root->rchild->color == 1 && !has_red_child(root->rchild))){
           type = 2;
           --root->lchild->color; //左子结点-1层黑色
           --root->rchild->color; //右子结点-1层黑色
           ++root->color; //根结点+1层黑色
           return root;
       }

    type = 2;
    //调整二、三
    if(root->rchild->color == 1){ //如果左子树的颜色是黑色 L
        if(root->lchild->lchild->color != 0){ // LR类型（要直接判断左子树的颜色，因为LL类型是优先的，右子 树不论是不是红色，只要左子树是红色就是LL类型）
            ++type;
            root->lchild = left_rotate(root->lchild); //抓住左子树进行小左旋
        }
        ++type;
        root->rchild->color = 1;
        root->lchild->color = root->color; //新根结点的颜色改为原根结点的原色。右旋的新根结点就是原来的左 子树
        root = right_rotate(root); //抓住当前根结点进行大右旋
    } else { //LL
        type = 3;
        if(root->rchild->rchild->color != 0){
            ++type;
            root->rchild = right_rotate(root->rchild);
        }
        ++type;
        root->rchild->color = root->color;
        root = left_rotate(root);
    }
    root->lchild->color = 1;
    root->lchild->color = root->rchild->color = 1; //根结点的左右子结点都改为黑色
    printf("brother is %s\n", erase_maintain_type_str[type]);
    return root;
}

Node *__erase(Node *root, int key){
    if(root == NIL) return root;
    if(root->key > key) root->lchild = __erase(root->lchild, key); //到左子树删除
    else if(root->key < key) root->rchild = __erase(root->rchild, key); //到右子树删除
    else { //要删除的是当前结点
        if(root->lchild == NIL || root->rchild == NIL){ //删除n = 0 || n = 1的，对应了情况3、4、5、6
            Node *temp = root->lchild == NIL ? root->rchild : root->lchild; //如果左子树为空就指向右子树，否则指向左子树。找到唯一子孩子或者让temp指向NIL
            //情况4：红色子结点变为黑色代替被删除的黑色结点。红色是0，黑色是1，把当前子结点的黑色加到子结 点上去
            //情况5直接删除，不用管颜色
            //情况6：temp结点指向的其实是NIL结点，把当前结点的黑色加到NIL上去变成双重黑
            temp->color += root->color; 
            free(root);
            return temp;
        } else { //n = 2
            Node *temp = root->lchild;
            while(temp->rchild != NIL) temp = temp->rchild; //找到当前结点的前驱（也可以是后继）
            root->key = temp->key; //前驱的值直接赋值给当前结点
            root->lchild = __erase(root->lchild, temp->key); //到左子树中删除前驱结点的值
        }
    }
    return erase_maintain(root); 
}

Node *erase(Node *root, int key){
    root = __erase(root, key);
    root->color = 1; //保证根结点是黑色
    return root;
}

void clear(Node *root){
    if(root == NIL) return ;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}

void printf_node(Node *root){
    printf("( %d(%d) | %d, %d )\n", root->key, root->color, root->lchild->key, root->rchild->key);
    return ;
}

void output(Node *root){
    if(root == NIL) return ;
    printf_node(root);
    output(root->lchild);
    output(root->rchild);
    return ;
}

int main(){
    Node *root = NIL;

    int key;
    while(~scanf("%d", &key)){
        if(key == -1) break;
        printf("\n===insert %d to rad black tree===\n", key);
        root = insert(root, key);
        output(root);
    }
    while(~scanf("%d", &key)){
        if(key == -1) break;
        printf("\n===erase %d to rad black tree===\n", key);
        root = erase(root, key);
        output(root);
    }

    clear(root);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237

要是对您有帮助，点个赞再走吧~ 欢迎评论区讨论~