wjin

红黑树

 7420  15 分钟

§定义

红黑树是一种自平衡的二叉搜索树，除满足二叉搜索树的要求外，还满足 1、节点是黑色或者红色的； 2、根节点是黑色的； 3、叶子节点是黑色的； 4、每个红色节点有两个黑色的孩子节点； 5、从任意一个节点出发，到达其叶子节点的路径上黑色节点个数相同。

这些约束保证了红黑树的关键特性：从根节点出发到叶子节点的最长可能路径不超过最短可能路径的两倍长，所以红黑树大致是平衡的。这是因为4保证相邻的两个节点一定不都是红色的，而5保证最短的可能路径上必定全是黑色节点，而最长可能路径上必是红黑相间，且两者黑色节点个数相等，所以最长可能路径的长度最多为最短可能路径长度的2倍。

下图所示是一棵典型的红黑树，此处叶子节点不保存数据，所以省略了所有叶子节点。在二叉树中，一个节点可能只有一个子节点，而叶子保存数据，这样也可以实现红黑树，但算法比较复杂。因此本文中所有叶子节点都不保存数据，省略不画，实现中不为它分配内存，即使用nullptr表示叶子节点，而不是使用左右孩子都为nullptr指针的节点表示叶子节点。这样，一个显而易见的结论是所有节点都有两个子节点，不过其中的一个或两个为空。为方便起见，本文称呼nullptr为空节点，及称呼左右孩子都为nullptr的节点为叶子节点。

example

红黑树的节点定义为

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

struct RBNode {
    enum Color {
        RED, BLACK
    };

    int value;
    Color color;
    RBNode *left;
    RBNode *right;
    RBNode *parent;

    explicit RBNode(int value = 0) : value(value), color(RED),
            left(nullptr), right(nullptr), parent(nullptr) {}
};

为方便后续代码的表达，此处再定义一组返回周围节点的操作：

 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

struct RBNode {
    enum Color {
        RED, BLACK
    };

    int value;
    Color color;
    RBNode *left;
    RBNode *right;
    RBNode *parent;

    explicit RBNode(int value = 0) : value(value), color(RED),
            left(nullptr), right(nullptr), parent(nullptr) {}

    // 返回父节点的父节点
    RBNode *grandparent() const {
        if (!parent)
            return nullptr;
        return parent->parent;
    }

    // 返回父节点的兄弟
    RBNode *uncle() const {
        if (!grandparent())
            return nullptr;
        if (parent == grandparent()->right)
            return grandparent()->left;
        else
            return grandparent()->right;
    }

    // 返回自己的兄弟
    RBNode *sibling() const {
        if (!parent)
            return nullptr;
        if (parent->left == this)
            return parent->right;
        else
            return parent->left;
    }
};

§插入节点

首先我们以二叉搜索树插入节点的方法(参考平衡二叉树的插入一节)来插入一个节点并标记它为红色。之所以标记为红色是因为如果标记为黑色，则此路径上多了一个黑色节点，这一点难以调整，而标记为红色只可能导致连续出现两个红色节点的冲突，可以通过旋转和染色来解决。

在下面的示意图中，将要调整的节点(初始为刚插入的节点，可能向上递归)标记为N，N的父节点为P，N的祖父节点标记为G，N的叔父节点标记为U。红黑树插入节点分为以下几种情况： 1、要调整的节点N为树的根节点，没有父节点。将它重绘为黑色即可。 2、要调整的节点的父节点P为黑色，此时未破坏红黑树的性质，什么也不用做； 3、要调整的节点的父节点P和叔父节点U都为红色，此时祖父节点G必为黑色。调整方法为将P和U重绘为黑色，G重绘为红色，这样通过G的任意一条路径的黑色节点个数和原来一样，但如果G是根节点则违反性质2，或者如果G的父节点是红色则违反性质4。因此需要再调整节点G。示意图如下(实际情况中，N可能为P的右孩子，P也可能为G的右孩子)：

insert3

4、要调整的节点的父节点P为红色而叔父节点U不存在或者为黑色，且N为P的左孩子，而P为G的左孩子，或者与此对称地，N为P的右孩子，而p为G的右孩子。此时祖父节点G必为黑色节点，将G重绘为红色节点，将P重绘为黑色节点，然后右旋节点G，或者与此对称地，左旋节点G。示意图如下：

insert4

如果N是新插入的节点，则P到nullptr的路径上只有一个黑色节点(nullptr本身)，所以P的右子树必为空，U必为nullptr。但如果是第3种情况向上递归时遇到的第5种情况则不一定了，此时N可能有子树，所以P也可能有右子树，而U不为空，即上图所画的情况。 5、要调整的节点的父节点P为红色而叔父节点U不存在或者为黑色，且N为P的右孩子，而P为G的左孩子，或者与此对称地，N为P的左孩子，而P为G的右孩子。前者左旋节点P，后者右旋节点P，然后按第4种情况调整节点P。示意图如下：

insert5

如果N是新插入的节点，则P到nullptr的路径上只有一个黑色节点(nullptr本身)，因此P的左子树必为空，U必为nullptr。但是如果是第3种情况向上递归时遇到的第5种情况则不一定了，此时N可能有子树，即上图所画的情况。

代码描述为：

 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

// 插入数据。如果data已存在，则什么也不做。
void RBTree::insert(int data) {
    // 空树插入为根节点，并绘制为黑色
    if (!rb_root) {
        rb_root = new RBNode(data);
        rb_root->color = RBNode::BLACK;
        return;
    }

    RBNode *p = rb_root;
    while (true) {
        if (data == p->value)  // 值已经存在什么也不做
            return;
        else if (data < p->value) {
            if (p->left) {
                p = p->left;
            } else {
                p->left = new RBNode(data);
                p->left->parent = p;
                return insertionAdjust(p->left);
            }
        } else {
            if (p->right) {
                p = p->right;
            } else {
                p->right = new RBNode(data);
                p->right->parent = p;
                return insertionAdjust(p->right);
            }
        }
    }
}

void RBTree::insertionAdjust(RBNode *p) {
    if (!p->parent) {  // 要调整的节点是根节点，重绘成黑色即可
        rb_root = p;
        rb_root->color = RBNode::BLACK;
        return;
    } else if (p->parent->color == RBNode::RED) {
        // 父节点为黑色时什么也不用做，只考虑父节点为红色的情况，此时父节点不可能
        // 是根节点，即祖父节点必然存在
        if (p->uncle() && p->uncle()->color == RBNode::RED) {
            // 叔父节点存在且为红色，将父节点和叔父节点重绘为黑色，祖父节点重绘为
            // 红色，然后递归处理祖父节点
            p->parent->color = RBNode::BLACK;
            p->uncle()->color = RBNode::BLACK;
            p->grandparent()->color = RBNode::RED;
            insertionAdjust(p->grandparent());
        } else { // 叔父节点不存在或者为黑色
            if (p == p->parent->left && p->parent == p->grandparent()->left) {
                p->parent->color = RBNode::BLACK;
                p->grandparent()->color = RBNode::RED;
                rightRotate(p->grandparent());
            } else if (p == p->parent->right && p->parent == p->grandparent()->right) {
                p->parent->color = RBNode::BLACK;
                p->grandparent()->color = RBNode::RED;
                leftRotate(p->grandparent());
            } else if (p == p->parent->right && p->parent == p->grandparent()->left) {
                leftRotate(p->parent);
                p->color = RBNode::BLACK;
                p->parent->color = RBNode::RED;
                rightRotate(p->parent);
            } else { // p == p->parent->left && p->parent == p->grandparent()->right
                rightRotate(p->parent);
                p->color = RBNode::BLACK;
                p->parent->color = RBNode::RED;
                leftRotate(p->parent);
            }
        }
    }
}

要注意insertionAdjust函数中，也不能少了判断p为根节点的情况，表面上这种情况在insert函数中已经单独处理了，但由第3种递归处理时也可能得到这种情况。

§删除节点

首先参考二叉搜索树删除节点的方法，如果待删除的节点有两个孩子，则从右子树中选择具有最小值的节点，即后继节点，交换它们的值，然后删除后继节点。由于后继节点必为叶子节点或者只有右孩子，所以删除节点的问题只需要考虑删除最多只有一个孩子的节点的问题，以下仅考虑这一种情况。

首先看三种基本情况：

1、如果待删除节点为红色，删除它后不会影响红黑树的性质，直接删除即可。

2、如果待删除节点为黑色，但它有一个红色的孩子节点，则以此节点代替它并重绘为黑色即可。

3、如果待删除节点为黑色，且孩子节点是黑色节点。由于它最多只有一个孩子节点，如果这个孩子节点存在且为黑色，则此路径比另一路径多一个黑色节点，所以待删除节点必定没有孩子节点。但这种情况只会出现在删除某个节点第一次调用调整函数时，由于调整函数有递归，递归时情况可能会变复杂，此时不去考虑被调整节点的孩子即可。

这三种基本情况中，第3种比较复杂，后面再讨论，先考虑第1、2两种情况，代码描述如下：

 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

// 删除节点
void RBTree::erase(RBNode *node) {
    if (!node)   // 空指针什么也不做
        return;

    // node既有左孩子又有右孩子，从右子树中选择最小的节点，交换它和node的值，
    // 然后删除它
    if (node->left && node->right) {
        RBNode *p = node->right;
        while (p->left)
            p = p->left;
        node->value = p->value;   // 如果不是内置类型考虑使用移动语义
        node = p;
    }

    // node至多只有一个孩子，根据周围的节点情况调整。几种使用孩子节点替换的情况不在
    // erasionAdjust中，必须单独考虑
    RBNode *parent = node->parent;
    if (RBNode::RED == node->color) {
        // 红色节点直接删除，其它什么也不做
    } else if (node->left && RBNode::RED == node->left->color) {
        // 待删除节点为黑色，左孩子存在且为红色。以左孩子替代它并重绘为黑色
        node->left->color = RBNode::BLACK;
    } else if (node->right && RBNode::RED == node->right->color) {
        // 待删除节点为黑色，右孩子存在且为红色。以右孩子替代它并重绘为黑色
        node->right->color = RBNode::BLACK;
    } else {
        erasionAdjust(node);   // 第3种基本情况
    }

    // 把node从红黑树中摘下来并删除
    if (!parent) {
        if (node->left)
            rb_root = node->left;
        else
            rb_root = node->right;
    } else {
        if (node == parent->left) {
            if (node->left)
                parent->left = node->left;
            else
                parent->left = node->right;
        } else {
            if (node->left)
                parent->right = node->left;
            else
                parent->right = node->right;
        }
    }
    node->left = nullptr;
    node->right = nullptr;
    delete node;
}

现在来考虑第3种基本情况，由于存在递归，递归过程中的待调整节点不是待删除节点，因此以待调整节点来称呼即将被删除的节点。记待调整节点为D，其父节点为P，兄弟节点为S，兄弟节点的两个子树为Sl和Sr。

根据待调整节点D周围的情况，可以分为以下6种情况：

1、待调整节点为根节点。如果随后要删除这个节点，则整棵树只有这一个节点，删除之后为空树；如果随后不删除这个节点，则必然是由情况6递归而来，此时这个节点已经是黑色，不用做任何调整。因此这种情况直接返回即可。

待调整节点不为根节点时，其父节点存在，由于待调整节点为黑色，因此其兄弟节点必定存在，否则待调整节点所在路径多一个黑色节点。

2、兄弟节点为红色，此时父节点必为黑色。交换P和S的颜色，然后对P做左旋，此时D的兄弟节点变成黑色，为3、4、5三种情况中的任意一种(Sl为子树，其根节点为黑色但可能还有红色子节点，因此不一定为情况5)，接着处理即可。示意图如下：

erase2.1

erase2.2

3、兄弟节点为黑色，远侄子节点存在且为红色，此时父节点可黑可红，而近侄子节点可空可红。交换P和S的颜色，然后对P左旋，把远侄子重绘为黑色，调整即完成，随后即可删除节点D。示意图如下：

erase3.1

erase3.2

4、兄弟节点为黑色，远侄子节点不存在或者为黑色，近侄子节点为红色。此时父节点可黑可红，如果D是待删除节点，将在调整完成后删除，则远侄子节点必定不存在，否则从P出发经过它的两个孩子的路径长度不一致。但如果是从情况6递归而来，则远侄子节点可能存在且为黑色，此时近侄子变有黑色孩子(图中未画出，旋转时某一个孩子由S收养)。调整方法为旋转节点S，并交换近侄子和S的颜色，然后按情况3调整近侄子节点。当D在左子树时，右旋S，当D在右子树时，左旋S。示意图如下：

erase4.1

erase4.2

5、兄弟节点为黑色，侄子节点都不存在或者为黑色，父节点为红色。如果D是待删除节点，将在调整完成后删除，则兄弟节点必为叶子节点，但如果是从情况6递归而来，则侄子节点可能存在并为黑色。调整方法为将P重绘为黑色，S重绘为红色，调整即完成，随后可删除节点D。示意图如下：

erase5.1

erase5.2

6、兄弟节点为黑色，侄子节点不存在或者为黑色，父节点为黑色。调整方法为将S重绘为红色，这样删除D后经过P的路径黑色节点个数减少1，因此必须继续调整节点P。在继续调整节点P时，由于之后不会删除P，因此以孩子节点顶替待调整节点的情况不能考虑在内，也就是递归调整只在基本情况3内递归，这是把基本情况的1和2单独列出来的原因。示意图如下：

erase6.1

erase6.2

综合以上6种情况，可得到基本情况3的处理方法，代码描述为：

 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

void RBTree::erasionAdjust(RBNode *node) {
    // 黑色节点可能为根节点
    if (node == rb_root)
        return;

    // 待删除节点不为根节点，则兄弟节点必然存在
    RBNode *parent = node->parent;
    RBNode *sibling = node->sibling();

    if (RBNode::RED == sibling->color) {
        // 兄弟节点为红色，此时父节点必为黑色。旋转父节点，交换父节点和兄弟节点
        // 的颜色，然后按其它情况处理。
        parent->color = RBNode::RED;
        sibling->color = RBNode::BLACK;

        if (node == parent->left)
            leftRotate(parent);
        else
            rightRotate(parent);

        // 旋转后兄弟节点变成了sibling的孩子，此节点和sibling的另一个孩子必存在
        // 且为黑色
        sibling = node->sibling();
    }

    // sibling->color == RBNode::BLACK必然成立，即兄弟节点必为黑色
    if (node == parent->left &&
        sibling->right && RBNode::RED == sibling->right->color) {
        // 待删除节点位于左子树，远侄子节点存在且为红色。此时父节点颜色不定，可黑可红。
        // 交换父节点和兄弟节点颜色，父节点左旋，远侄子重绘为黑色
        sibling->color = parent->color;
        parent->color = RBNode::BLACK;
        sibling->right->color = RBNode::BLACK;
        leftRotate(parent);
    } else if (node == parent->right &&
               sibling->left && RBNode::RED == sibling->left->color) {
        // 待删除节点位于右子树，远侄子节点存在且为红色。此时父节点颜色不定，可黑可红。
        // 交换父节点和兄弟节点的颜色，父节点右旋，远侄子重绘为黑色
        sibling->color = parent->color;
        parent->color = RBNode::BLACK;
        sibling->left->color = RBNode::BLACK;
        rightRotate(parent);
    } else if (node == parent->left &&
               sibling->left && RBNode::RED == sibling->left->color) {
        // 待删除节点位于左子树，远侄子节点不存在，近侄子节点存在且为红色。此时父节点
        // 颜色不定，可黑可红。交换兄弟和近侄子颜色，兄弟节点右旋，然后按远侄子为红色
        // 的情况处理
        sibling->left->color = parent->color;
        parent->color = RBNode::BLACK;
        rightRotate(sibling);
        leftRotate(parent);
    } else if (node == parent->right &&
               sibling->right && RBNode::RED == sibling->right->color) {
        // 待删除节点位于右子树，远侄子节点不存在，近侄子节点存在且为红色。此时父节点
        // 颜色不定，可黑可红。交换兄弟和近侄子颜色，兄弟节点左旋，然后按远侄子为红色
        // 的情况处理
        sibling->right->color = parent->color;
        parent->color = RBNode::BLACK;
        leftRotate(sibling);
        rightRotate(parent);
    } else if (RBNode::RED == parent->color) {
        // 侄子节点不存在或者全为黑色，父节点为红色。交换父节点和兄弟节点颜色
        parent->color = RBNode::BLACK;
        sibling->color = RBNode::RED;
    } else {
        // 侄子节点不存在或者全为黑色，父节点为黑色。兄弟节点重绘成红色，然后调整父节点
        sibling->color = RBNode::RED;
        erasionAdjust(parent);
    }
}

§完整的参考代码

  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
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361

struct RBNode {
    enum Color {
        RED, BLACK
    };

    int value;
    Color color;
    RBNode *left;
    RBNode *right;
    RBNode *parent;

    explicit RBNode(int data = 0) {
        value = data;
        color = RED;
        left = nullptr;
        right = nullptr;
        parent = nullptr;
    }

    ~RBNode() {
        delete left;
        delete right;
    }

    // 返回父节点的父节点
    RBNode *grandparent() const {
        if (!parent)
            return nullptr;
        return parent->parent;
    }

    // 返回父节点的兄弟
    RBNode *uncle() const {
        if (!grandparent())
            return nullptr;
        if (parent == grandparent()->right)
            return grandparent()->left;
        else
            return grandparent()->right;
    }

    // 返回自己的兄弟
    RBNode *sibling() const {
        if (!parent)
            return nullptr;
        if (parent->left == this)
            return parent->right;
        else
            return parent->left;
    }
};

class RBTree {
public:
    RBTree() : rb_root(nullptr) {}

    ~RBTree() { delete rb_root; }

    RBNode *getRoot() const { return rb_root; }

    // 查找数据。如果找到数据则返回数据所在节点的指针，如果没有找到则返回nullptr。
    RBNode *search(int data);

    // 插入数据。如果data已存在，则什么也不做。
    // 如果应用时为key-value组合可改为更新value
    void insert(int data);

    // 删除数据
    void erase(int data);

    // 删除节点
    void erase(RBNode *node);

private:
    RBNode *rb_root;

    // 左旋
    void leftRotate(RBNode *root);

    // 右旋
    void rightRotate(RBNode *root);

    // 插入节点的调整
    void insertionAdjust(RBNode *p);

    void erasionAdjust(RBNode *node);
};

// 左旋
void RBTree::leftRotate(RBNode *root) {
    if (!root || !root->right)
        return;

    // 右孩子变成新的根节点
    RBNode *new_root = root->right;
    RBNode *parent = root->parent;
    new_root->parent = parent;
    if (!parent) {
        rb_root = new_root;
    } else {
        if (parent->left == root)
            parent->left = new_root;
        else
            parent->right = new_root;
    }

    // 新的根节点的左孩子由原来的根节点收养为右孩子
    root->right = new_root->left;
    if (new_root->left)
        new_root->left->parent = root;

    // 原来的根节点变成新的根节点的左孩子
    new_root->left = root;
    root->parent = new_root;
}

// 右旋
void RBTree::rightRotate(RBNode *root) {
    if (!root || !root->left)
        return;

    // 左孩子变成新的根节点
    RBNode *new_root = root->left;
    RBNode *parent = root->parent;
    new_root->parent = parent;
    if (!parent) {
        rb_root = new_root;
    } else {
        if (parent->left == root)
            parent->left = new_root;
        else
            parent->right = new_root;
    }

    // 新的根节点的右孩子由原来的根节点收养为左孩子
    root->left = new_root->right;
    if (new_root->right)
        new_root->right = root;

    // 原来的根节点变成新的根节点的右孩子
    new_root->right = root;
    root->parent = new_root;
}

// 查找数据。
RBNode *RBTree::search(int data) {
    RBNode *p = rb_root;
    while (p && p->value != data) {
        if (data < p->value)
            p = p->left;
        else
            p = p->right;
    }
    return p;
}

// 插入数据。如果data已存在，则什么也不做。
void RBTree::insert(int data) {
    // 空树插入为根节点，并绘制为黑色
    if (!rb_root) {
        rb_root = new RBNode(data);
        rb_root->color = RBNode::BLACK;
        return;
    }

    RBNode *p = rb_root;
    while (true) {
        if (data == p->value)  // 值已经存在什么也不做
            return;
        else if (data < p->value) {
            if (p->left) {
                p = p->left;
            } else {
                p->left = new RBNode(data);
                p->left->parent = p;
                return insertionAdjust(p->left);
            }
        } else {
            if (p->right) {
                p = p->right;
            } else {
                p->right = new RBNode(data);
                p->right->parent = p;
                return insertionAdjust(p->right);
            }
        }
    }
}

void RBTree::insertionAdjust(RBNode *p) {
    if (!p->parent) {  // 要调整的节点是根节点，重绘成黑色即可
        rb_root = p;
        rb_root->color = RBNode::BLACK;
        return;
    } else if (p->parent->color == RBNode::RED) {
        // 父节点为黑色时什么也不用做，只考虑父节点为红色的情况，此时父节点不可能是
        // 根节点，即祖父节点必然存在
        if (p->uncle() && p->uncle()->color == RBNode::RED) {
            // 叔父节点存在且为红色，将父节点和叔父节点重绘为黑色，祖父节点重绘为红色，
            // 然后递归处理祖父节点
            p->parent->color = RBNode::BLACK;
            p->uncle()->color = RBNode::BLACK;
            p->grandparent()->color = RBNode::RED;
            insertionAdjust(p->grandparent());
        } else { // 叔父节点不存在或者为黑色
            if (p == p->parent->left && p->parent == p->grandparent()->left) {
                p->parent->color = RBNode::BLACK;
                p->grandparent()->color = RBNode::RED;
                rightRotate(p->grandparent());
            } else if (p == p->parent->right && p->parent == p->grandparent()->right) {
                p->parent->color = RBNode::BLACK;
                p->grandparent()->color = RBNode::RED;
                leftRotate(p->grandparent());
            } else if (p == p->parent->right && p->parent == p->grandparent()->left) {
                leftRotate(p->parent);
                p->color = RBNode::BLACK;
                p->parent->color = RBNode::RED;
                rightRotate(p->parent);
            } else { // p == p->parent->left && p->parent == p->grandparent()->right
                rightRotate(p->parent);
                p->color = RBNode::BLACK;
                p->parent->color = RBNode::RED;
                leftRotate(p->parent);
            }
        }
    }
}

// 删除节点
void RBTree::erase(RBNode *node) {
    if (!node)   // 空指针什么也不做
        return;

    // node既有左孩子又有右孩子，从右子树中选择最小的节点，交换它和node的值，然后删除它
    if (node->left && node->right) {
        RBNode *p = node->right;
        while (p->left)
            p = p->left;
        node->value = p->value;   // 如果不是内置类型考虑使用移动语义
        node = p;
    }

    // node至多只有一个孩子，根据周围的节点情况调整。几种使用孩子节点替换的情况不在
    // erasionAdjust中，必须单独考虑
    RBNode *parent = node->parent;
    if (RBNode::RED == node->color) {
        // 红色节点直接删除，其它什么也不做
    } else if (node->left && RBNode::RED == node->left->color) {
        // 待删除节点为黑色，左孩子存在且为红色。以左孩子替代它并重绘为黑色
        node->left->color = RBNode::BLACK;
    } else if (node->right && RBNode::RED == node->right->color) {
        // 待删除节点为黑色，右孩子存在且为红色。以右孩子替代它并重绘为黑色
        node->right->color = RBNode::BLACK;
    } else {
        erasionAdjust(node);
    }

    // 把node从红黑树中摘下来并删除
    if (!parent) {
        if (node->left)
            rb_root = node->left;
        else
            rb_root = node->right;
    } else {
        if (node == parent->left) {
            if (node->left)
                parent->left = node->left;
            else
                parent->left = node->right;
        } else {
            if (node->left)
                parent->right = node->left;
            else
                parent->right = node->right;
        }
    }
    node->left = nullptr;
    node->right = nullptr;
    delete node;
}

// 调整待删除节点周围的节点以满足红黑树的定义。被调整的节点不一定是将要被删除的节点，
// 有一种情况需要递归调整父节点，因此不能包含几种使用孩子节点替换的情况。
void RBTree::erasionAdjust(RBNode *node) {
    // 待删除节点为黑色，且孩子不为红色，此时如果左孩子或者右孩子存在且为黑色，则一条
    // 路径比另一条多一个黑色节点，所以左右孩子必定都不存在，待删除节点为叶子节点，此
    // 时如果待删除节点不是根节点则其兄弟节点必定存在，否则待删除节点所在路径多一个黑
    // 色节点。
    if (node == rb_root)  // 黑色节点可能为根节点，整棵树只有这一个节点，删除即可
        return;

    // 待删除节点不为根节点，则兄弟节点必然存在
    RBNode *parent = node->parent;
    RBNode *sibling = node->sibling();

    if (RBNode::RED == sibling->color) {
        // 兄弟节点为红色，此时父节点必为黑色。旋转父节点，交换父节点和兄弟节点的颜色，
        // 然后按其它情况处理。
        parent->color = RBNode::RED;
        sibling->color = RBNode::BLACK;

        if (node == parent->left)
            leftRotate(parent);
        else
            rightRotate(parent);

        // 旋转后兄弟节点变成了sibling的孩子，此节点和sibling的另一个孩子必存在且为黑色
        sibling = node->sibling();
    }

    // sibling->color == RBNode::BLACK必然成立，即兄弟节点必为黑色
    if (node == parent->left &&
        sibling->right && RBNode::RED == sibling->right->color) {
        // 待删除节点位于左子树，远侄子节点存在且为红色。此时父节点颜色不定，可黑可红。
        // 交换父节点和兄弟节点颜色，父节点左旋，远侄子重绘为黑色
        sibling->color = parent->color;
        parent->color = RBNode::BLACK;
        sibling->right->color = RBNode::BLACK;
        leftRotate(parent);
    } else if (node == parent->right &&
               sibling->left && RBNode::RED == sibling->left->color) {
        // 待删除节点位于右子树，远侄子节点存在且为红色。此时父节点颜色不定，可黑可红。
        // 交换父节点和兄弟节点的颜色，父节点右旋，远侄子重绘为黑色
        sibling->color = parent->color;
        parent->color = RBNode::BLACK;
        sibling->left->color = RBNode::BLACK;
        rightRotate(parent);
    } else if (node == parent->left &&
               sibling->left && RBNode::RED == sibling->left->color) {
        // 待删除节点位于左子树，远侄子节点不存在，近侄子节点存在且为红色。此时父节
        // 点颜色不定，可黑可红。交换兄弟和近侄子颜色，兄弟节点右旋，然后按远侄子为
        // 红色的情况处理
        sibling->left->color = parent->color;
        parent->color = RBNode::BLACK;
        rightRotate(sibling);
        leftRotate(parent);
    } else if (node == parent->right &&
               sibling->right && RBNode::RED == sibling->right->color) {
        // 待删除节点位于右子树，远侄子节点不存在，近侄子节点存在且为红色。此时父节
        // 点颜色不定，可黑可红。交换兄弟和近侄子颜色，兄弟节点左旋，然后按远侄子为
        // 红色的情况处理
        sibling->right->color = parent->color;
        parent->color = RBNode::BLACK;
        leftRotate(sibling);
        rightRotate(parent);
    } else if (RBNode::RED == parent->color) {
        // 侄子节点不存在或者全为黑色，父节点为红色。交换父节点和兄弟节点颜色
        parent->color = RBNode::BLACK;
        sibling->color = RBNode::RED;
    } else {
        // 侄子节点不存在或者全为黑色，父节点为黑色。兄弟节点重绘成红色，然后调整父节点
        sibling->color = RBNode::RED;
        erasionAdjust(parent);
    }
}

// 删除数据
void RBTree::erase(int data) {
    RBNode *node = search(data);
    erase(node);
}

§参考

[1] https://www.jianshu.com/p/e136ec79235c.

[2] https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91.

[3] https://www.cnblogs.com/qingergege/p/7351659.html.

相关文章：

加载评论