“Look up at the stars, not down at your feet.”
红黑树
红黑树，一种二叉查找树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而接近是平衡的。
红黑树作为一棵二叉查找树，其满足二叉查找树的一般性质。为此，我们来了解一下二叉查找树的一般性质。
1.二叉查找树
二叉查找树(BST, Binary Search Tree)，又称为有序二叉树或者排序二叉树，是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
因为一棵由n个节点随机构造的二叉查找树的高度为lgn,所以二叉查找树一般操作的执行时间为O(log n)。但是二叉查找树若是退化成为一棵具有n个节点的线性链后，则这些操作最坏情况下为O(n).
为此，红黑树的引入就很有必要。虽然它本质上是一种二叉查找树，但是它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏的情况为O(log n)。
但是红黑树是如何保证一棵n个节点的红黑树高度始终保持在log n呢，这就引出了红黑树的5个性质。
2. 红黑树的特点
红黑树除了符合二叉查找树的特性之外，还具有下面的五个特性：
- 每个节点要么是红的要么是黑色的；
- 根节点是黑色的；
- 每个叶节点(叶子节点即指树尾端NIL指针或NULL节点)都是黑的；
- 如果一个节点是红色的，那么它的两个儿子都是黑的；
- 对于任意节点而言，其到叶节点树尾端NIL指针的每条路径都包含相同数目的黑色节点。
注意：
- 特性3中的叶子节点，是只为空(NIL或NULL)的节点。
- 特性5确保了没有一条路径会比其他路径长出两倍。因而，红黑树是相对接近平衡的二叉树。
正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。给出红黑树示意图如下所示：
在树的结构发生变化时(插入或者删除操作)，往往会破坏上述特性4和特性5，需要通过调整使得查找树重新满足红黑树的条件。
3.红黑树的基本操作与Java实现
红黑树的基本操作是添加,删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。
给出基本定义如下所示：
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
public class MyRBTree<T extends Comparable<T>> {
private RBTNode<T> root;
private static final boolean RED = false;
private static final boolean BLACK = true;
public class RBTNode<T extends Comparable<T>> {
boolean color; //颜色
T key;
RBTNode<T> left; //左孩子
RBTNode<T> right;//右孩子
RBTNode<T> parent;//父节点
public RBTNode(T key, boolean color, RBTNode<T> parent,RBTNode<T> left, RBTNode<T> right){
this.key = key;
this.color = color;
this.parent = parent;
this.right = right;
this.left = left;
}
public T getKey() {
return key;
}
@Override
public String toString(){
return "" + key +(this.color==RED ? "(Red)" : "(Black)");
}
}
...
}
其旋转主要包括两种：左旋和右旋。下面先分别对他们进行介绍：
3.1 左旋
左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的特性依然能够满足。
给出一个我认为很生动的例子过程：
在算法导论上，给出了下面的伪代码，来理解“红黑树T的节点x进行左旋”是如何进行的。参考下面的示意图：
1
2
3
4
5
6
7
8
9
10
11
12
LEFT-ROTATE(T x)
y <- right[x] //前提：这里假设x的右孩子为y，下面正式开始操作
right[x] <- left[y] // 将y的左孩子设为x的右孩子，即 将β设为x的右孩子
p[left[y]] <- x // 将 x设为y的左孩子的父亲， 即将β的父亲设为x
p[y] <- p[x] // 将x的父亲设为y的父亲
if p[x] = nil[T]
then root[T] <- y //情况1： 如果 x的父亲是空节点，则将y设置为根节点
else if x = left[p[x]]
then left[p[x]] <- y //情况2： 如果x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else right[p[x]] <- y //情况3： 如果x是它父节点的右孩子，则将y设为“x的父节点的右孩子”
left[y] <- x //将x设为y的左孩子
p[x] <- y //将y设置为x的父节点
根据上面伪代码，实现左旋的操作代码如下：
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
private void leftRotate(RBTNode<T> x){
if(x != null){
//设置x的右孩子为变量y
RBTNode<T> y = x.right;
//如果y的左孩子不为空，则将其设置为x的右孩子
if(y.left != null){
x.right = y.left;
}
//将x的父亲设为y的父亲
y.parent = x.parent;
if(x.parent == null){
//如果 x的父亲是空节点，则将y设置为根节点
this.root = y;
}else{
if(x.parent.left == x){
// 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
x.parent.left = y;
}else {
// 如果 x是它父节点的右孩子，则将y设为“x的父节点的右孩子”
x.parent.right = y;
}
}
//将x设为y的左孩子
y.left = x;
//将y设置为x的父节点
x.parent = y;
}
}
3.2 右旋
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
给出一个我认为很生动的例子过程：
在算法导论上，给出了下面的伪代码，来理解“红黑树T的节点y进行右旋”是如何进行的。参考下面的示意图：
1
2
3
4
5
6
7
8
9
10
11
12
RIGHT-ROTATE(T, y)
x <- left[y] //前提：这里假设y的左节点为x，下面开始正式操作
left[y] <- right[x] //将x的右孩子设为y的左孩子，即将β设为y的左孩子
p[right[x]] <- y // 将y设置为x右孩子的父亲，即将β的父亲设为y
p[x] <- p[y] //将y的父亲设为x的父亲
if p[y] = nil[T]
then root[T] <- x //情况1： 如果y的父亲是空节点，则将x设为根节点
else if y = right[p[y]]
then right[p[y]] <- x //情况2： 如果y是它的父亲节点的右孩子，则将x设为"y的父节点的右孩子"
else left[p[y]] <- x //情况3： 如果y是它的父亲节点的左孩子，则将x设为"y的父节点的左孩子"
right[x] <- y //将y设为x的右孩子
p[y] = x //将x设为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
private void rightRotate(RBTNode<T> y){
if (y != null) {
//设置x为当前节点的左孩子
RBTNode<T> x = y.left;
//将x的右孩子设置为y的左孩子
y.left = x.right;
if(x.right != null){
x.right.parent = y;
}
//将y的父亲设置为x的父亲
x.parent = y.parent;
if (y.parent == null){
//如果y的父亲节点是空节点，则将x设为根节点
this.root = x;
}else{
if (y == y.parent.right) {
// 如果y是y的父亲节点的右孩子，则将x设为“y的父节点的右孩子”
y.parent.right = x;
}else{
// 如果y是y的父亲节点的左孩子，则将x设为“y的父节点的左孩子”
y.parent.left = x;
}
}
// 将 “y” 设为 “x的右孩子”
x.right = y;
// 将 “y的父节点” 设为 “x”
y.parent = x;
}
}
在实际应用中，若没有彻底理解 左旋 和 右旋，可能会将它们混淆。下面谈谈我对如何区分左旋和右旋的理解。
3.3 区分左旋和右旋
仔细观察上面”左旋”和”右旋”的示意图。我们能清晰的发现，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。
左旋示意图(以x节点进行左旋)：(这里可能会有一点点误解，看上面吧)
1
2
3
4
5
z
x /
/ \ --(左旋)--> x
y z /
y
对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)。 因此，左旋中的“左”，意味着被旋转的节点将变成一个左节点。
右旋示意图(以x节点进行右旋)：(这里可能会有一点点误解，看上面吧)
1
2
3
4
5
y
x \
/ \ --(右旋)--> x
y z \
z
对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为y的右孩子)。 因此，右旋中的“右”，意味着被旋转的节点将变成一个右节点。
3.4 添加
将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一棵二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重写着色等方法来修正该树，使之重新成为一棵红黑树。其详细步骤如下所示：
1. 将红黑树当做一棵二叉查找树，将节点插入
红黑树本身就是一棵二叉查找树，将节点插入后，该树仍然是一棵二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树，这也就意味着，任何的旋转和着色操作，都不会改变它仍然是一棵二叉查找树的事实。
2. 将插入的节点着色为“红色”
为什么着色成红色，而不是黑色呢？这是因为红黑树的特性第5条(从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点)。如果我们将插入的节点着色为红色，将不会违背特性5.
少违背一条特性，就意味着我们需要处理的情况就越少。接下来，就要努力的让这棵树满足其他性质即可；满足了的话，它就是一棵红黑树了。
3. 通过一系列的旋转和着色等操作，使之重新成为一棵红黑树
在第二步中，将插入节点着色为“红色之后”，不会违背特性5.那它到底会违背哪些特性呢？
- 对于特性1，显然不会违背了。因为我们已经将它涂成红色了。
- 对于特性2，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
- 对于特性3，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。
- 对于特性4，是有可能违背的。
那接下来，就是想办法使之满足特性4，就可以将树重新构造成红黑树了。下面我们先来看看伪代码是如何实现这三步的。
添加操作的伪代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
RB-INSERT(T, z)
y <- nil[T] //新建节点y,将y设为空节点
x <- root[T] //设红黑树T的根节点为x
while x ≠ nil[T] //找出要插入的节点z在二叉树T中的位置y
do y <- x
if key[z] < key[x]
then x <- left[x]
else x <- right[x]
p[z] <- y //将y设置为z的父亲
if y = nil[T]
then root[T] <- z //情况1： 若y是空节点，则将z设为根
else if key[z] < key[y]
then left[y] <- z //情况2： 若“z所包含的值” < “y所包含的值”，则将z设为y的左孩子
else right[y] <- z //情况3： 若“z所包含的值” > “y所包含的值”，则将z设为y的右孩子
left[z] <- nil[T] //z的左孩子为空
right[z] <- nil[T] //z的右孩子设为空，至此，目前已经完成将“节点z插入到二叉树中了”
color[z] <- RED //将z着色为红色
RB-INSERT-FIXUP(T, z) //通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改已经旋转，让树T仍然是一棵红黑树
根据上面的伪代码，实现添加操作的代码如下：
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
private void insert(RBTNode<T> node){
int cmp;
RBTNode<T> y = null;
RBTNode<T> x = this.root;
//将红黑树当做一棵二叉搜索树，将节点添加到二叉查找树中
//找出要插入的节点node在二叉树T中的位置y
while (x != null){
y = x;
cmp = node.key.compareTo(x.key);
if(cmp < 0){
x = x.left;
}else{
x = x.right;
}
}
//将y设置为node的父亲
node.parent = y;
if(y != null){
cmp = node.key.compareTo(y.key);
if(cmp < 0){
//情况2： 若“node所包含的值” < “y所包含的值”，则将node设为y的左孩子
y.left = node;
}else{
//情况3： 若“node所包含的值” > “y所包含的值”，则将node设为y的右孩子
y.right = node;
}
}else{
//情况1： 若y是空节点，则将z设为根
this.root = node;
}
// 2. 设置节点的颜色为红色
node.color = RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(node);
}
在理解了RB-INSERT之后，我们接着对RB-INSERT-FIXUP的伪代码进行说明：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
RB-INSERT-FIXUP(T , z)
while color[p[z]] = RED //若当前节点z的父节点是红色，则进行以下处理
do if p[z] = left[p[p[z]]] //若“z的父节点”是“z的祖父节点的左孩子”，则进行以下处理
then y <- right[p[p[z]]] //将y设置为“z的祖父节点的右孩子”
if color[y] = RED //Case 1条件：叔叔是红色
then color[p[z]] <- BLACK ▹ Case 1 // (01) 将父节点设为黑色
color[y] <- BLACK ▹ Case 1 // (02) 将叔叔节点设为黑色
color[p[p[z]]] <- RED ▹ Case 1 // (03) 将祖父节点设为红色
z <- p[p[z]] ▹ Case 1 // (04) 将祖父节点设为当前节点(红色节点)
else if z = right[p[z]] //Case 2条件： 叔叔是黑色，且当前节点是右孩子
then z <- p[z] ▹ Case 2 // (01) 将父节点作为新的当前节点z
LEFT-ROTATE(T,z) ▹ Case 2 // (02) 以“新的当前节点”为支点进行左旋
color[p[z]] <- BLACK ▹ Case 3 //Case 3条件： 叔叔是黑色，且当前节点是左孩子(01) 将“父节点设为黑色”
color[p[p[z]]] <- RED ▹ Case 3 // (02) 将祖父节点设为红色
RIGHT-ROTATE(T,p[p[z]]) ▹ Case 3 // (03) 以祖父节点为支点进行右旋
else (same as then clause with "right" and "left" exchanged) // 若z的父节点是“z的祖父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。
color[root[T]] <- BLACK
根据被插入节点的父节点的情况，可以将“当前节点z被着色为红色节点，并插入二叉树”划分为三种情况来处理。
- 情况说明：当被插入的节点是根节点时，直接把此节点涂为黑色。
- 情况说明：当被插入的节点的父节点是黑色时，这时候什么也不需要做，节点被插入后，仍然是红黑树。
- 情况说明：当被插入的节点的父节点是红色时，那么该情况与“红黑树的特性4”冲突。这种情况下，被插入节点是一定存在非空祖父节点；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解了这点之后，我们依据“叔叔节点的情况”，将这种情况进一步划分为3种情况(Case)。(注意：下文的分析都是基于插入节点z的父节点是其祖父节点的左孩子，如果是祖父节点的右孩子。则将下文中的左换成右，右换成左即可)
| 标号 | 现象说明 | 处理策略 |
|---|---|---|
| Case 1 | 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色 | (01) 将“父节点”设为黑色。 (02) 将“叔叔节点”设为黑色。(03) 将“祖父节点”设为红色。 (4) 将“祖父节点”设为当前节点(红色节点);即，之后继续对“当前节点”进行操作。 |
| Case 2 | 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子 | (01) 将“父节点”作为“新的当前节点”。 (02) 以“新的当前节点”为支点进行左旋。 |
| Case 3 | 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子 | (01) 将“父节点”设为黑色。 (02)将“祖父节点”设为红色。 (03)以“祖父节点”为支点进行右旋。 |
上面三种情况(Case)处理问题的核心都是：将红色的节点移到根节点；然后，将根节点设为黑色。下面将对它们详细进行介绍。
1. (Case 1)叔叔是红色
现象说明：当前节点(即被插入节点)的父节点是红色，且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。
处理策略：
- (1) 将父节点设为黑色；
- (2) 将叔叔节点设为黑色；
- (3) 将祖父节点设为红色；
- (4) 将祖父节点设为当前节点(红色节点)；即，之后继续对“当前节点”进行操作。
下面，具体来阐述为什么要这样处理：
首先，因为当前节点和父节点都是红色，违背了“特性4”。所以，将父节点设置为黑色，能够解决这个问题。但是，将父节点由红色变为黑色之后，违背了特性5：因为包含父节点的分支的黑色节点的总数增加了1。为此，解决这个问题的办法就是：将“祖父节点”由黑色变为红色，同时，将“叔叔节点”由红色变为黑色。
关于这里，说明几点：
- 第一，为什么祖父节点之前是黑色？因为在变换操作之前，该树是红黑树，“父节点”是红色，那么祖父节点一定是黑色。
- 第二，为什么将祖父节点由黑色变为红色，同时将叔叔节点由红色变为黑色，就能解决“包含”父节点的分支的黑色节点的总数增加了1的问题？“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”，既然这样，我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题； 但是，这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”，现在我们已知“叔叔节点”是“红色”，将“叔叔节点”设为“黑色”就能解决这个问题。 所以，将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；就解决了该问题。
按照上面的步骤处理之后：当前节点、父节点、叔叔节点之间都不会违背红黑树的特性，但是祖父节点却不一定。若此时，祖父节点是根节点，直接将祖父节点设为“黑色”，即可完全解决这个问题了；若祖父节点不是根节点，那我们需要将祖父节点设为“新的当前节点”，接着对“新的当前节点”进行分析。
给出示意图如下所示：
2. (Case 2)叔叔是黑色，且当前节点是右孩子
现象说明：当前节点(即被插入节点)的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子。
处理策略：
- (01)将父节点作为新的当前节点；
- (02)以新的当前节点作为支点进行左旋。
下面，具体来阐述为什么要这样处理：
首先，将“父节点”作为“新的当前节点”；接着，以“新的当前节点”为支点进行左旋。 为了便于理解，我们先说明第(02)步，再说明第(01)步；为了便于说明，我们设置“父节点”的代号为F(Father)，“当前节点”的代号为S(Son)。
为什么要“以F为支点进行左旋”呢？根据已知条件可知：S是F的右孩子。而之前我们说过，我们处理红黑树的核心思想：将红色的节点移到根节点；然后将根节点设为黑色。既然是将“红色的节点移到根节点”，那么就是说要不断地将破坏红黑树特性的红色节点上移(即是向根方向移动)。而S又是一个右孩子，因此，我们就可以通过“左旋”来将S上移。
按照上面的步骤(以F为支点进行左旋)处理之后：若S变成了根节点，那么直接将其设为“黑色”，就完全解决问题了；若S不是根节点，那我们需要执行步骤(01),即“将F设为新的当前节点”。那为什么不继续以S为新的当前节点继续处理，而需要以F为新的当前节点来进行处理呢？这是因为左旋之后，F变成了S的子节点，即S变成了F的父节点；而我们处理问题的时候，需要从下至上(由叶到根)方向进行处理；也就是说，必须先解决“孩子”的问题，再解决“父亲”的问题；所以，我们执行步骤(01):将父节点作为新的当前节点。
给出示意图如下所示：
3. (Case 3)叔叔是黑色，且当前节点是左孩子
现象说明：当前节点(即被插入节点)的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子。
处理策略：
- (01)将父节点设为黑色；
- (02)将祖父节点设为红色；
- (03)以祖父节点为支点进行右旋。
下面，来谈谈为什么需要这样处理：
首先，为了便于说明。我们设置当前节点为S(Oringinal Son),兄弟节点为B(Brother),叔叔节点为U(Uncle),父节点为F(Father),祖父节点为G(GrandFather).
S和F都为红色，违背了红黑树的“特性4”，我们可以将F由红色变为黑色，就解决了违背特性4的问题；但是却引起了其他问题，违背特性5，因为将F由红色改为黑色后，所有经过F的分支的黑色节点的个数增加了1。那我们如何解决“所有经过F的分支的黑色节点的个数增加了1”的问题？我们可以通过“将G由黑色变为红色”，同时以G为支点进行右旋来解决。
给出示意图如下所示：
给出添加修正操作的实现代码如下所示：
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
private void insertFixUp(RBTNode<T> node){
RBTNode<T> parent, gparent;
//若父节点存在，且父节点的颜色是红色
while (node != null && (parent = parentOf(node)) != null && isRed(node)){
gparent = parentOf(parent);
//若父节点是祖父节点的左孩子
if (parent == gparent.left) {
RBTNode<T> uncle = gparent.right;
//Case 1条件:叔叔节点是红色
if(colorOf(uncle) == RED){
setBlack(parent);
setBlack(uncle);
setRed(gparent);
node = gparent;
}else{
if(parent.right == node){
//Case 2条件：叔叔是黑色，且当前节点是右孩子
node = parentOf(node);
leftRotate(node);
}
//Case 3条件：叔叔是黑色，且当前节点是左孩子
setBlack(parentOf(node));
setRed(gparent);
rightRotate(gparent);
}
}else{
// 若父节点是祖父节点的右孩子
RBTNode<T> uncle = gparent.left;
//Case 1条件：叔叔节点是红色
if(colorOf(uncle) == RED){
setBlack(parent);
setBlack(uncle);
setRed(gparent);
node = gparent;
}else{
if(parent.left == node){
//Case 2条件：叔叔是黑色，且当前节点是左孩子
node = parentOf(node);
rightRotate(node);
}
// Case 3条件：叔叔是黑色，且当前节点是右孩子
setBlack(parentOf(node));
setRed(gparent);
leftRotate(gparent);
}
}
}
//将根节点颜色设为黑色
setBlack(this.root);
}
3.5 删除
将红黑树内的某一个节点删除，需要执行的操作依次是：首先，把红黑树当做一棵二叉搜索树，讲该节点从二叉查找树中删除；然后，通过旋转和重新着色等一系列操作来修正该树，使之重新成为一棵红黑树，详细描述如下：
1. 将红黑树当做一棵二叉查找树，将节点删除
这和“删除常规二叉查找树中删除节点的方法是一样的”。分3种情况：
- (1) 被删除节点没有儿子，即为叶子节点。那么直接将该节点删除就行了；
- (2) 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置；
- (3) 被删除节点由两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给“被删除节点”之后，再将后继节点删除。这样就巧妙地将问题转换成“删除后继节点”的情况了，下面就考虑后继节点。在“被删除节点”有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然“它的后继节点”不可能双子都非空，就意味着“该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按照情况(1)来处理；若只有一个儿子，则按情况(2)处理。
2. 通过旋转和重新着色等一系列操作来修正该树，使得重新成为一棵红黑树
因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树。
下面先来看看删除操作的伪代码：(删除操作的伪代码有多种，下面给出本文所参考文章的一种)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
RB-DELETE(T, z)
if left[z] = nil[T] or right[T] = nil[T]
then y <- z //若z的左孩子或者z的右孩子为空，则将z赋值给y
else y <- TREE-SUCCESSOR(z) //否则，将z的后继节点赋值给y
if left[y] ≠ nil[T]
then x <- left[y] //若y的左孩子不为空，则将y的左孩子赋值给x;
else x <- right[y] //否则，y的右孩子赋值给给x
p[x] <- p[y] //将y的父节点设置为x的父节点
if p[y] = nil[T]
then root[T] <- x //情况1： 若y的父节点为空，则设置x为“根节点”
else if y = left[p[y]]
then left[p[y]] <- x //情况2： 若y是它的父节点的左孩子，则设置x为“y的父节点的左孩子”
else right[p[y]] <- x //情况3： 若y是它的父节点的右孩子，则设置x为“y的父节点的右孩子”
if y ≠ z
then key[z] <- key[y] //y与z不相同时，y的值赋值给z.注意：这里只拷贝z的值给y，而没有拷贝z的颜色！！！
copy y's satellite data into z
if color[y] = BLACK
then RB-DELETE-FIXUP(T,x) //若y为黑节点，则调用RB-DELETE-FIXUP
根据上面的伪代码，实现删除操作如下所示：
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
private void remove(RBTNode<T> node){
RBTNode<T> x = null;
RBTNode<T> y = null;
if(node.left == null || node.right == null){
y = node;
}else{
y = successor(node);
}
x = (y.left != null ? y.left : y.right);
if(x != null){
x.parent = y.parent;
}
if(y.parent == null){
this.root = x;
}else if(y == y.parent.left){
y.parent.left = x;
}else {
y.parent.right = x;
}
if(y != node){
node.key = y.key;
}
if(y.color == BLACK){
removeFixUp(x);
}
}
private RBTNode<T> successor(RBTNode<T> x){
if(x == null){
return null;
}else if(x.right != null){
//如果存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
RBTNode<T> p = x.right;
while (p.left != null){
p = p.left;
}
return p;
}else{
// 如果x没有右孩子。则x有以下两种可能：
// (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
// (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
RBTNode<T> p = x.parent;
while ((p != null) && x == p.right){
x = p;
p = p.parent;
}
return p;
}
}
在理解了RB-DELETE之后，我们接着对RB-DELETE-FIXUP的伪代码进行说明。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
RB-DELETE-FIXUP(T, x)
while x ≠ root[T] and color[x] = BLACK
do if x = left[p[x]]
then w <- right[p[x]] //若x是它的父节点的左孩子，则设置w为x的兄弟(即w为x的父节点的右孩子)
if color[w] = RED // Case 1: x是“黑+黑”节点，x的兄弟节点是红色(此时，x的父节点和x的兄弟节点下的子节点都是黑节点)
then color[w] <- BLACK ▹ Case 1 // (01) 将x的兄弟节点设为黑色
color[p[x]] <- RED ▹ Case 1 // (02) 将x的父亲节点设为红色
LEFT-ROTATE(T, p[x]) ▹ Case 1 // (03) 对x的父节点进行左旋
w <- right[p[x]] ▹ Case 1 // (04) 左旋后，重新设置x的兄弟节点
if color[left[w]] = BLACK and color[right[w]] = BLACK // Case 2: x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色
then color[w] <- RED ▹ Case 2 // (01) 将x的兄弟节点设为红色
x <- p[x] ▹ Case 2 // (02) 设置x的父节点为“新的x节点”
else if color[right[w]] = BLACK // Case 3： x是“黑+黑”节点，x的兄弟节点是黑色; x的兄弟节点的左孩子是红色，右孩子是黑色
then color[left[w]] <- BLACK ▹ Case 3 // (01) 将x的兄弟节点的左孩子设为黑色
color[w] <- RED ▹ Case 3 // (02) 将x的兄弟节点 设为红色
RIGHT-ROTATE(T,w) ▹ Case 3 // (03) 对x的兄弟节点进行右旋
w <- right[p[x]] ▹ Case 3 // (04) 右旋后重新设置x的兄弟节点
color[w] <- color[p[x]] ▹ Case 4 //Case 4：x是“黑+黑”节点，x的兄弟节点是黑色; x的兄弟节点的右孩子是红色。(01)将x父节点颜色赋给 x的兄弟节点
color[p[x]] <- BLACK ▹ Case 4 // (02) 将x的父节点设为黑色
color[right[w]] <- BLACK ▹ Case 4 // (03) 将x的兄弟节点的右孩子设为黑色
LEFT-ROTATE(T, p[x]) ▹ Case 4 // (04) 对x的父节点进行左旋
x <- root[T] ▹ Case 4 // (05) 设置x为根节点
else (same as then clause with "right" and "left" exchanged) // 若 “x”是“它父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。
color[x] <- BLACK
下面对删除函数继续分析。在分析之前，我们再来看一遍红黑树的几个特性：
- 每个节点要么是红的要么是黑色的；
- 根节点是黑色的；
- 每个叶节点(叶子节点即指树尾端NIL指针或NULL节点)都是黑的；
- 如果一个节点是红色的，那么它的两个儿子都是黑的；
- 对于任意节点而言，其到叶节点树尾端NIL指针的每条路径都包含相同数目的黑色节点。
前面我们将”删除红黑树中的节点”大致分为两步，在第一步中”将红黑树当作一颗二叉查找树，将节点删除”后，可能违反”特性(2)、(4)、(5)”三个特性。第二步需要解决上面的三个问题，进而保持红黑树的全部特性。
为了便于分析，我们假设”x包含一个额外的黑色”(x原本的黑色还存在)，这样就不会违反特性5.为什么呢？通过RB-DELETE算法，我们知道：删除节点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设为一个黑色节点即可。
- 非前面的两种姿态。
根据上面的姿态，可以概括为3种情况：
- 情况说明：x是“红+黑”节点。直接把x设为黑色，结束。此时红黑树性质全部恢复。
- 情况说明：x是“黑+黑”节点，且x是根。什么都不做，结束。此时红黑树性质全部恢复。
- 情况说明：x是“黑+黑”节点，且x不是根。这种情况的话又可以划分为4种子情况。(注意：下文的分析都是基于节点x是其父节点的左孩子，如果是父节点的右孩子。则将下文中的左换成右，右换成左即可)
| 标号 | 现象说明 | 处理策略 |
|---|---|---|
| Case 1 | x是“黑+黑”节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。 | (01) 将x的兄弟节点设为黑色；(2) 将x的父节点设为红色; (3) 对x的父节点进行左旋; (4) 左旋后，重新设置x的兄弟节点。 |
| Case 2 | x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。 | (01) 将x的兄弟节点设为红色； (02) 设置”x的父节点”为”新的x节点”。 |
| Case 3 | x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。 | (01) 将x的兄弟节点的左孩子设为“黑色”；(02) 将x兄弟节点设为红色。(3) 对x的兄弟节点进行右旋；(4)右旋后，重新设置x的兄弟节点。 |
| Case 4 | x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色，x的兄弟节点的左孩子任意颜色。 | (01) 将x父节点颜色赋值给x的兄弟节点；(02) 将x父节点设为黑色；(03) 将x的兄弟节点的右孩子设为黑色；(04) 对x的父节点进行左旋。(05) 设置x为根节点。 |
1. (Case 1)x是”黑+黑”节点，x的兄弟节点是红色
现象说明：x是“黑+黑”节点，x的兄弟节点是红色。(此时，x的父节点和x的兄弟节点的子节点都是黑节点)
处理策略：
- (01) 将x的兄弟节点设为黑色；
- (02) 将x的父节点设为红色；
- (03) 对x的父节点进行左旋；
- (04) 左旋后，重新设置x的兄弟节点。
这样做的目的是为了将”Case 1”转换成“Case 2”、“Case 3”或者“Case 4”，从而进行进一步的处理。对x的父节点进行左旋；左旋后，为了保持红黑树特性，就需要在左旋前“将x的兄弟节点设为黑色”，同时”将x的父节点设为红色”；左旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。
给出示意图如下所示：
2. (Case 2)x是”黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色
现象说明：x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
处理策略：
- (01) 将x的兄弟节点设为红色
- (02) 设置”x的父节点”为”新的x节点”。
这个情况的处理思想是：是将“x中多于的一个黑色属性上移(往根的方向移动)”。x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；若x的父节点原先时“红”，则此时变成了“红+黑”)。 此时，需要注意的是：所有经过x的分支中黑节点个数没变化；但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
经过上面的步骤(将x的兄弟节点的颜色设为红色)，多余的一个颜色属性已经跑到x的父节点中。我们需要将x的父节点设为新的x节点进行处理。若“新的x节点”是“黑+红”，直接将新的x节点设为黑色，即可完全解决问题；若新的x节点是“黑+黑”，则需要对“新的x节点”进行进一步处理。
给出示意图如下所示：
3. (Case 3)x是”黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的左孩子是红色的，右孩子是黑色的
现象说明：x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
处理策略：
- (01) 将x的兄弟节点的左孩子设为“黑色”;
- (02) 将x的兄弟节点设为红色；
- (03) 对x的兄弟节点进行右旋;
- (04) 右旋后，重新设置x的兄弟节点。
我们处理“Case 3”的目的是为了将“Case 3”进行转换，转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋；为了保证右旋后,它仍然是红黑树，就需要在右旋前将x的兄弟节点的左孩子设为黑色，同时“将x的兄弟节点设为红色”；右旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。
给出示意图如下所示：
4. (Case 4)x是”黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色
现象说明：x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。
处理策略：
- (01) 将x父节点颜色赋值给x的兄弟节点;
- (02) 将父节点颜色设为黑色；
- (03) 将x兄弟节点的右孩子设为黑色；
- (04) 对x的父节点进行左旋；
- (05) 设置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是父子关系，而我们假设BL是红色，如果F是红色，则会违背特性4；为了解决这一问题，我们将F设置为黑色。但是，F设置为黑色之后，为了满足特性5，即为了保证左旋之后：
- 第一，同时经过根节点和S的分支的黑色节点个数不变。若满足第一，只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”，而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1；现在，只需将S由“黑+黑”变成单独的“黑”节点，即可满足“第一”。
- 第二，同时经过根节点和BLS的分支的黑色节点数不变。若满足第二，只需要将“F的原始颜色”赋值给B即可。之前，我们已经将“F设置为黑色”(即，将B的颜色”黑色”，赋值给了F)。至此，我们算是调换了F和B的颜色。
- 第三，“同时经过根节点和BRS的分支的黑色节点数不变”。在“第二”已经满足的情况下，若要满足“第三”，只需要将BRS设置为“黑色”即可。
经过，上面的处理之后。红黑树的特性全部得到的满足！接着，我们将x设为根节点，就可以跳出while循环(参考伪代码)；即完成了全部处理。
给出示意图如下所示：
给出删除修正操作的实现代码如下所示：
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
private void removeFixUp(RBTNode<T> node){
RBTNode<T> other;
while (node != this.root && colorOf(node) == BLACK){
if(parentOf(node).left == node){
other = parentOf(node).right;
if(isRed(other)){
//Case 1:x的兄弟w是红色的
setBlack(other);
setRed(parentOf(node));
leftRotate(parentOf(node));
other = parentOf(node).right;
}
if(colorOf(other.left) == BLACK && colorOf(other.right) == BLACK){
//Case 2:x的兄弟节点w是黑色，且w的两个孩子也都是黑色的
setRed(other);
node = parentOf(node);
}else{
if (colorOf(other.right) == BLACK){
//Case 3:x的兄弟节点w是黑色,且w的左孩子为红色，右孩子是黑色
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parentOf(node).right;
}
// Case 4:x的兄弟节点w是黑色,且w的右孩子为红色，左孩子任意颜色
setColor(other,colorOf(parentOf(node)));
setBlack(parentOf(node));
setBlack(other.right);
leftRotate(parentOf(node));
node = this.root;
}
}else{
other = parentOf(node).left;
if(isRed(other)){
//Case 1:x的兄弟w是红色的
setBlack(other);
setRed(parentOf(node));
rightRotate(parentOf(node));
other = parentOf(node).left;
}
if(colorOf(other.left) == BLACK && colorOf(other.right) == BLACK){
//Case 2:x的兄弟节点w是黑色，且w的两个孩子也都是黑色的
setRed(other);
node = parentOf(node);
}else{
if(colorOf(other.left) == BLACK){
//Case 3:x的兄弟节点w是黑色,且w的右孩子为红色，左孩子是黑色
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parentOf(node).left;
}
// Case 4:x的兄弟节点w是黑色,且w的左孩子为红色，右孩子任意颜色
setColor(other,colorOf(parentOf(node)));
setBlack(parentOf(node));
setBlack(other.left);
rightRotate(parentOf(node));
node = this.root;
}
}
}
if(node != null){
setBlack(node);
}
}
给出删除操作的一个综合例子：
至此，以上就是红黑树的核心内容。
参考文章：
