转载：
http://www.cnblogs.com/skywang12345/p/3245399.html
http://blog.csdn.net/v_july_v/article/details/6105630
简介
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以O(lgn) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。
性质
红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。
除了具备该特性之外，红黑树还包括许多额外的信息。
红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。
红黑树的特性:
- 每个节点或是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有简单路径上包含相同数目的黑节点。
关于它的特性，需要注意的是：
-
特性(3)中的叶子节点，是只为空(NIL或null)的节点。
-
特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
应用
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
基本结构定义
1
2
3
4
5
6
7
8
9
10
11
12
|
enum RBTColor{RED, BLACK};
template <class T>
class RBTNode{
public:
RBTColor color; // 颜色
T key; // 关键字(键值)
RBTNode *left; // 左孩子
RBTNode *right; // 右孩子
RBTNode *parent; // 父结点
RBTNode(T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r):
key(value),color(c),parent(),left(l),right(r) {}
};
|
基本旋转操作
当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。
树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。
左旋
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
|
/*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋)：
* px px
* / /
* x y
* / \ --(左旋)--> / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
template <class T>
void RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x)
{
// 设置x的右孩子为y
RBTNode<T> *y = x->right;
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y->parent = x->parent;
if (x->parent == NULL)
{
root = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
}
else
{
if (x->parent->left == x)
x->parent->left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else
x->parent->right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
}
// 将 “x” 设为 “y的左孩子”
y->left = x;
// 将 “x的父节点” 设为 “y”
x->parent = y;
}
|
右旋
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
|
/*
* 对红黑树的节点(y)进行右旋转
*
* 右旋示意图(对节点y进行左旋)：
* py py
* / /
* y x
* / \ --(右旋)--> / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
template <class T>
void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y)
{
// 设置x是当前节点的左孩子。
RBTNode<T> *x = y->left;
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
// 将 “y的父亲” 设为 “x的父亲”
x->parent = y->parent;
if (y->parent == NULL)
{
root = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
}
else
{
if (y == y->parent->right)
y->parent->right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
else
y->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
// 将 “y” 设为 “x的右孩子”
x->right = y;
// 将 “y的父节点” 设为 “x”
y->parent = x;
}
|
添加操作
将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过”旋转和重新着色”等一系列操作来修正该树，使之重新成为一颗红黑树。详细描述如下：
第一步: 将红黑树当作一颗二叉查找树，将节点插入
红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。
好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！
第二步：将插入的节点着色为”红色”
将插入的节点着色为红色，不会违背”特性(5)”！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树
第二步中，将插入节点着色为”红色”之后，不会违背”特性(5)”。那它到底会违背哪些特性呢？
对于”特性(4)”，是有可能违背的！想办法使之”满足特性(4)”，就可以将树重新构造成红黑树了。
根据被插入节点的父节点的情况，可以将”当节点z被着色为红色节点，并插入二叉树”划分为三种情况来处理。
-
被插入的节点是根节点。（即之前是空树）
处理方法：直接把此节点涂为黑色。
-
被插入的节点的父节点是黑色。
处理方法：什么也不需要做。节点被插入后，仍然是红黑树。
-
被插入的节点的父节点是红色。
处理方法：那么，该情况与红黑树的“特性(5)”相冲突。这种情况下，被插入节点是一定存在非空祖父节点的；被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据”叔叔节点的情况”，将这种情况进一步划分为3种情况(Case)。
上面三种情况(Case)处理问题的核心思路都是：将红色的节点移到根节点；然后，将根节点设为黑色。下面对它们详细进行介绍。
详细介绍父节点为红色的处理方法
叔叔是红色
-
将“父节点”设为黑色。
-
将“叔叔节点”设为黑色。
-
将“祖父节点”设为“红色”。
-
将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。
下面谈谈为什么要这样处理：
“当前节点”和“父节点”都是红色，违背“特性(4)”。所以，将“父节点”设置“黑色”以解决这个问题。
但是，将“父节点”由“红色”变成“黑色”之后，违背了“特性(5)”：因为，包含“父节点”的分支的黑色节点的总数增加了1。 解决这个问题的办法是：将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”。
关于这里，说明几点：
-
为什么“祖父节点”之前是黑色？这个应该很容易想明白，因为在变换操作之前，该树是红黑树，“父节点”是红色，那么“祖父节点”一定是黑色。
-
为什么将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。
这个道理也很简单。“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”，既然这样，我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题； 但是，这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”，现在我们已知“叔叔节点”是“红色”，将“叔叔节点”设为“黑色”就能解决这个问题。 所以，将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；就解决了该问题。
按照上面的步骤处理之后：当前节点、父节点、叔叔节点之间都不会违背红黑树特性，但祖父节点却不一定。若此时，祖父节点是根节点，直接将祖父节点设为“黑色”，那就完全解决这个问题了；若祖父节点不是根节点，那我们需要将“祖父节点”设为“新的当前节点”，接着对“新的当前节点”进行分析。
转化为：
叔叔是黑色，且当前节点是右孩子
- 将“父节点”作为“新的当前节点”。
- 以“新的当前节点”为支点进行左旋。
下面谈谈为什么要这样处理：
首先，将“父节点”作为“新的当前节点”；接着，以“新的当前节点”为支点进行左旋。 为了便于理解，我们先说明第(02)步，再说明第(01)步；为了便于说明，我们设置“父节点”的代号为F(Father)，“当前节点”的代号为S(Son)。
为什么要“以F为支点进行左旋”呢？根据已知条件可知：S是F的右孩子。而之前我们说过，我们处理红黑树的核心思想：将红色的节点移到根节点；然后，将根节点设为黑色。既然是“将红色的节点移到根节点”，那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)。 而S又是一个右孩子，因此，我们可以通过“左旋”来将S上移！
按照上面的步骤(以F为支点进行左旋)处理之后：若S变成了根节点，那么直接将其设为“黑色”，就完全解决问题了；若S不是根节点，那我们需要执行步骤(01)，即“将F设为‘新的当前节点’”。
那为什么不继续以S为新的当前节点继续处理，而需要以F为新的当前节点来进行处理呢？这是因为情况2的处理措施无法解决违反性质4的错误，只是将错误转移到了“新的当前节点”，接下来的情况3正是对应了这种情况。
转化为：
叔叔是黑色，且当前节点是左孩子
-
将“父节点”设为“黑色”。
-
将“祖父节点”设为“红色”。（由性质4可知，祖父节点必为黑色）
-
以“祖父节点”为支点进行右旋。
下面谈谈为什么要这样处理。
为了便于说明，我们设置“当前节点”为S(Original Son)，“兄弟节点”为B(Brother)，“叔叔节点”为U(Uncle)，“父节点”为F(Father)，祖父节点为G(Grand-Father)。
S和F都是红色，违背了红黑树的“特性(4)”，我们可以将F由“红色”变为“黑色”，就解决了“违背‘特性(4)’”的问题；但却引起了其它问题：违背特性(5)，因为将F由红色改为黑色之后，所有经过F的分支的黑色节点的个数增加了1。那我们如何解决“所有经过F的分支的黑色节点的个数增加了1”的问题呢？ 我们可以通过“将G由黑色变成红色”，同时“以G为支点进行右旋”来解决。
经过“以G为支点进行右旋”，新的祖父节点为F，和之前的G都为黑色，所以性质4不会违背，而且变为红色的祖父节点G旋转到右支不会对性质4产生任何影响。
转化为
代码实现
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
|
/*
* 将结点插入到红黑树中
*
* 参数说明：
* root 红黑树的根结点
* node 插入的结点 // 对应《算法导论》中的node
*/
template <class T>
void RBTree<T>::insert(RBTNode<T>* &root, RBTNode<T>* node)
{
RBTNode<T> *y = NULL;
RBTNode<T> *x = root;
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x != NULL)
{
y = x;
if (node->key < x->key)
x = x->left;
else
x = x->right;
}
node->parent = y;
if (y!=NULL)
{
if (node->key < y->key)
y->left = node;
else
y->right = node;
}
else
root = node;
// 2. 设置节点的颜色为红色
node->color = RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(root, node);
}
/*
* 红黑树插入修正函数
*
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* root 红黑树的根
* node 插入的结点 // 对应《算法导论》中的z
*/
template <class T>
void RBTree<T>::insertFixUp(RBTNode<T>* &root, RBTNode<T>* node)
{
RBTNode<T> *parent, *gparent;
// 若“父节点存在，并且父节点的颜色是红色”
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
gparent = rb_parent(parent);
//若“父节点”是“祖父节点的左孩子”
if (parent == gparent->left)
{
// Case 1条件：叔叔节点是红色
{
RBTNode<T> *uncle = gparent->right;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// Case 2条件：叔叔是黑色，且当前节点是右孩子
if (parent->right == node)
{
RBTNode<T> *tmp;
leftRotate(root, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是左孩子。
rb_set_black(parent);
rb_set_red(gparent);
rightRotate(root, gparent);
}
else//若“z的父节点”是“z的祖父节点的右孩子”
{
// Case 1条件：叔叔节点是红色
{
RBTNode<T> *uncle = gparent->left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// Case 2条件：叔叔是黑色，且当前节点是左孩子
if (parent->left == node)
{
RBTNode<T> *tmp;
rightRotate(root, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是右孩子。
rb_set_black(parent);
rb_set_red(gparent);
leftRotate(root, gparent);
}
}
// 将根节点设为黑色
rb_set_black(root);
}
|
删除操作
将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：
第一步：将红黑树当作一颗二叉查找树，将节点删除
这和”删除常规二叉查找树中删除节点的方法是一样的”。分3种情况：
-
被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
-
被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
-
被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给”被删除节点”之后，再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了，下面就考虑后继节点。
在”被删除节点”有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空，就意味着”该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按”情况1 “进行处理；若只有一个儿子，则按”情况2”进行处理。
第二步：通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树
因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树。
前面我们将”删除红黑树中的节点”大致分为两步，在第一步中”将红黑树当作一颗二叉查找树，将节点删除”后，可能违反”特性(2)、(4)、(5)”三个特性。第二步需要解决上面的三个问题，进而保持红黑树的全部特性。
为了便于分析，我们假设”x包含一个额外的黑色”(x原本的颜色还存在)，这样就不会违反”特性(5)”。为什么呢？
通过RB-DELETE算法，我们知道：删除节点y之后，x占据了原来节点y的位置。 既然删除y(y是黑色)，意味着减少一个黑色节点；那么，再在该位置上增加一个黑色即可。这样，当我们假设”x包含一个额外的黑色”，就正好弥补了”删除y所丢失的黑色节点”，也就不会违反”特性(5)”。 因此，假设”x包含一个额外的黑色”(x原本的颜色还存在)，这样就不会违反”特性(5)”。
现在，x不仅包含它原本的颜色属性，x还包含一个额外的黑色。即x的颜色属性是”红+黑”或”黑+黑”，它违反了”特性(1)”。
现在，我们面临的问题，由解决”违反了特性(2)、(4)、(5)三个特性”转换成了”解决违反特性(1)、(2)、(4)三个特性”。
RB-DELETE-FIXUP需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是：将x所包含的额外的黑色不断沿树上移(向根方向移动)，直到出现下面的姿态：
-
额外的黑色指向一个红节点，成为新的x。此时，将x设为一个”黑”节点即可。
-
额外的黑色指向根，成为新的x。此时，将x设为一个”黑”节点即可。
-
额外的黑色指向一个黑色的非根节点，成为新的x。
将上面的姿态，可以概括为3种情况。
-
x是“红+黑”节点。
直接把x设为黑色，结束。此时红黑树性质全部恢复。
-
x是“黑+黑”节点，且x是根。
什么都不做，结束。此时红黑树性质全部恢复。
-
x是“黑+黑”节点，且x不是根。
这种情况又可以划分为4种子情况。这4种子情况如下表所示：
详细介绍“黑+黑”非根节点的处理方法
x是”黑+黑”节点，x的兄弟节点是红色
-
将x的兄弟节点设为“黑色”。
-
将x的父节点设为“红色”。
-
对x的父节点进行左旋。
这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”，从而进行进一步的处理。对x的父节点进行左旋；左旋后，为了保持红黑树特性，就需要在左旋前“将x的兄弟节点设为黑色”，同时“将x的父节点设为红色”；此变换后原红黑树性质5不变，而把问题转化为兄弟节点为黑色的情况(注：变化前，原本就未违反性质5，只是为了把问题转化为兄弟节点为黑色的情况)。之后以x为节点重新进入算法
转化为：
x是”黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色
-
将x的兄弟节点设为“红色”。
-
设置“x的父节点”为“新的x节点”。
这个情况的处理思想：是将“x中多余的一个黑色属性上移(往根方向移动)”。 x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；若x的父节点原先是“红”，则此时变成了“红+黑”)。 此时，需要注意的是：所有经过x的分支中黑节点个数没变化；但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
经过上面的步骤(将x的兄弟节点设为红色)，多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”，直接将“新的x节点”设为黑色，即可完全解决该问题；若“新的x节点”是“黑+黑”，则需要对“新的x节点”进行进一步处理。
转化为：
x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的
-
将x兄弟节点的左孩子设为“黑色”。
-
将x兄弟节点设为“红色”。
-
对x的兄弟节点进行右旋。
我们处理“Case 3”的目的是为了将“Case 3”进行转换，转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋；为了保证右旋后，它仍然是红黑树，就需要在右旋前“将x的兄弟节点的左孩子设为黑色”，同时“将x的兄弟节点设为红色”；右旋后，之后以x为节点重新进入算法。
转化为：
x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色
-
将x父节点颜色 赋值给x的兄弟节点。
-
将x父节点设为“黑色”。
-
将x兄弟节点的右子节设为“黑色”。
-
对x的父节点进行左旋。
我们处理“Case 4”的目的是：去掉x中额外的黑色，将x变成单独的黑色。处理的方式是：进行颜色修改，然后对x的父节点进行左旋。下面，我们来分析是如何实现的。
为了便于说明，我们设置“当前节点”为S(Original Son)，“兄弟节点”为B(Brother)，“兄弟节点的左孩子”为BLS(Brother’s Left Son)，“兄弟节点的右孩子”为BRS(Brother’s Right Son)，“父节点”为F(Father)。
我们要对F进行左旋。但在左旋前，我们需要调换F和B的颜色，并设置BRS为黑色。为什么需要这样处理呢？因为左旋后，F和BLS是父子关系，若BLS是红色，如果F是红色，则违背了“特性(4)”；为了解决这一问题，我们将“F设置为黑色”。 但是，F设置为黑色之后，为了保证满足“特性(5)”，即为了保证左旋之后：
-
“同时经过根节点和S的分支的黑色节点个数不变”。
若满足“第一”，只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”，而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1；现在，只需将S由“黑+黑”变成单独的“黑”节点，即可满足“第一”。
-
“同时经过根节点和BLS的分支的黑色节点数不变”。
若满足“第二”，只需要调换F和B的颜色。因为F成为BLS的父节点后，B成为了BLS的祖父节点，B和F在路径中只是调换位置。在上述4步中已经实现
-
“同时经过根节点和BRS的分支的黑色节点数不变”。
若满足“第三”，只需要将BRS设为黑色，因为左旋过程中原来的B替代了F，而没有节点替代B，所以要使黑色节点数不变，需要将BRS本身设为黑色。
经过，上面的处理之后。红黑树的特性全部得到的满足！接着，我们将x设为根节点，就可以跳出while循环(参考伪代码)；即完成了全部处理。
至此，我们就完成了Case 4的处理。理解Case 4的核心，是了解如何“去掉当前节点额外的黑色”。
转化为:
代码实现
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
|
/*
* 删除结点(node)，并返回被删除的结点
*
* 参数说明：
* root 红黑树的根结点
* node 删除的结点
*/
template <class T>
void RBTree<T>::remove(RBTNode<T>* &root, RBTNode<T> *node)
{
RBTNode<T> *child, *parent;
RBTColor color;
// 被删除节点的"左右孩子都不为空"的情况。
if ( (node->left!=NULL) && (node->right!=NULL) )
{
// 被删节点的后继节点。(称为"取代节点")
// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
RBTNode<T> *replace = node;
// 获取后继节点
replace = replace->right;
while (replace->left != NULL)
replace = replace->left;
// "node节点"不是根节点(只有根节点不存在父节点)
if (rb_parent(node))
{
if (rb_parent(node)->left == node)
rb_parent(node)->left = replace;
else
rb_parent(node)->right = replace;
}
else
// "node节点"是根节点，更新根节点。
root = replace;
// child是"取代节点"的右孩子，也是需要"调整的节点"。
// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
child = replace->right;
parent = rb_parent(replace);
// 保存"取代节点"的颜色
color = rb_color(replace);
// "被删除节点"是"它的后继节点的父节点"
if (parent == node)
{
parent = replace;
}
else
{
// child不为空
if (child)
rb_set_parent(child, parent);
parent->left = child;
replace->right = node->right;
rb_set_parent(node->right, replace);
}
replace->parent = node->parent;
replace->color = node->color;
replace->left = node->left;
node->left->parent = replace;
if (color == BLACK)
removeFixUp(root, child, parent);
delete node;
return ;
}
if (node->left !=NULL)
child = node->left;
else
child = node->right;
parent = node->parent;
// 保存"取代节点"的颜色
color = node->color;
if (child)
child->parent = parent;
// "node节点"不是根节点
if (parent)
{
if (parent->left == node)
parent->left = child;
else
parent->right = child;
}
else
root = child;
if (color == BLACK)
removeFixUp(root, child, parent);
delete node;
}
/*
* 红黑树删除修正函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* root 红黑树的根
* node 待修正的节点
*/
template <class T>
void RBTree<T>::removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent)
{
RBTNode<T> *other;
while ((!node || rb_is_black(node)) && node != root)
{
if (parent->left == node)
{
other = parent->right;
if (rb_is_red(other))
{
// Case 1: x的兄弟w是红色的
rb_set_black(other);
rb_set_red(parent);
leftRotate(root, parent);
other = parent->right;
}
if ((!other->left || rb_is_black(other->left)) &&
(!other->right || rb_is_black(other->right)))
{
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->right || rb_is_black(other->right))
{
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
rb_set_black(other->left);
rb_set_red(other);
rightRotate(root, other);
other = parent->right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->right);
leftRotate(root, parent);
node = root;
break;
}
}
else
{
other = parent->left;
if (rb_is_red(other))
{
// Case 1: x的兄弟w是红色的
rb_set_black(other);
rb_set_red(parent);
rightRotate(root, parent);
other = parent->left;
}
if ((!other->left || rb_is_black(other->left)) &&
(!other->right || rb_is_black(other->right)))
{
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->left || rb_is_black(other->left))
{
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
rb_set_black(other->right);
rb_set_red(other);
leftRotate(root, other);
other = parent->left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->left);
rightRotate(root, parent);
node = root;
break;
}
}
}
if (node)
rb_set_black(node);
}
|