一篇文章彻底搞定红黑树
前言
红黑树警告！
虽说很多人都会把红黑树当作面经交流时的一个玩笑话，但是红黑树作为一个比较重要的点，还是有可能在面试时被提到的。JDK 1.8 后，HashMap 中，如果一条链表的长度大于 8，且哈希桶的个数大于等于 64 时，这条链表就会转化为红黑树。
红黑树在面试时一般会考察其基本的特性，进阶一点会考察左旋右旋的方式，极致的考察就会让面试者写出在红黑树中插入/删除节点的代码。
二叉查找树
我们首先从二叉查找树（Binary Search Tree，BST）开始。一棵红黑树，首先是一棵二叉查找树。
一棵二叉查找树具备以下特征：
- 左子树上所有节点的值均小于或等于它的根节点的值
- 右子树上所有节点的值均大于或等于它的根节点的值
- 左、右子树也分别为二叉查找树
一棵典型的二叉搜索树如下：
在一棵二叉搜索树中查找，类似于二分查找的过程，最多只需要搜索 二叉树层数 次，就可以找到目标。其搜索效率是
然而，二叉搜索树存在一个很严重的缺陷，当我们按顺序 “1，2，3，4，5，6” 将节点插入一棵空的二叉搜索树时，会出现下面的情况：
这种情况下，二叉搜索树的查找效率大打折扣，极端情况下甚至接近线性查找。导致这种情况的原因，是插入节点时导致的二叉查找树不平衡，例如上面这棵树，每个节点都没有左子树。
为了解决这种情况，红黑树出现了。
红黑树
红黑树其实就是一棵可以自平衡的二叉查找树，为了方便自平衡，它将其每个节点都标记了颜色，红色和黑色，红黑树由此得名。
《算法导论》上给出了红黑树的五条重要性质：
- 每个节点要么是黑色，要么是红色
- 根节点是黑色
- 每个叶子节点（NIL）都是黑色
- 每个红色节点的两个子节点都一定是黑色（从叶子到根的所有路径不能存在连续的红节点）
- 任意一节点到叶子节到每个叶子节点的路径都包含数量相同的黑色节点
由性质 5 又可以推出推论：
5.1 如果一个节点存在黑色子节点，那么该节点肯定有两个子节点
下图就是一棵简单的红黑树：
如图可以看出，红黑树并不是一棵完美平衡的二叉查找树，根节点 P 的左子树比右子树要高，但是根据性质 5 可以看出，左子树和右子树的黑色节点的层数是相等的，所以可以说，红黑树是 黑色节点完美平衡 的。
平衡的秘诀
红黑树的平衡主要靠三种操作：左旋、右旋和变色。
左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变
右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变
变色：节点的颜色由红变黑或由黑变红
可以看出，左旋和右旋只会影响目标节点的子树，而不会影响上层结构。其中，左旋只影响旋转节点和其右子树的结构，把右子树的节点往左子树挪了；同样，右旋只影响旋转节点和其左子树的结构，把左子树的节点向右子树挪。
所以旋转操作可以起到平衡两侧节点的作用：当一边节点少了，就可以通过旋转向另一边借来一些节点。当然，光是旋转是不够的，还需要通过变色来维持红黑树的几个基本性质。具体情况下面会分析。
作为示例，我们来实现左旋的操作：
public void leftRotate(Node x) {
// 设置x的右孩子为y
Node 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) {
this.mRoot = 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. 插入节点的 key 已经存在
3. 插入节点的父节点是黑色节点
4. 插入节点的父节点是红色节点
4.1 存在叔叔节点且叔叔节点是红色节点
4.2 叔叔节点不存在或叔叔节点是黑色节点，且插入节点的父节点是祖父节点的左子节点
4.2.1 插入节点是父节点的左子节点
4.2.2 插入节点是父节点的右子节点
4.3 叔叔节点不存在或叔叔节点是黑色节点，且插入节点的父节点是祖父节点的右子节点
4.3.1 插入节点是父节点的右子节点
4.3.2 插入节点是父节点的左子节点看起来情况很多，但实际上，情况 1、2、3 的处理很简单，而 4.2 和 4.3 只是方向相反，其他都可以类比。
为了方便叙述，我们将被插入的节点称为 I 节点，父节点称为 P 节点，叔叔节点为 S 节点，而祖父节点为 PP 节点。
以下我们来具体研究每个场景。
情况分析
情况 1
红黑树是空树，这时我们直接把插入节点当作空节点即可，根据红黑树性质 2，根节点应当是黑色，所以插入节点的颜色也应该设置为黑色。
情况 2
插入节点的 key 已经存在，由于在插入之前红黑树是平衡的，那么直接更新节点的值即可，不需要再调整树的平衡。
情况 3
插入节点的父节点是黑色节点，这种情况下，由于插入的节点是红色的，不会影响红黑树平衡，所以直接插入即可。
情况 4
插入节点的父节点是红色节点，根据性质 2，红色节点不可能是根节点，所以一定存在祖父节点。以下为具体情况：
情况 4.1
存在叔叔节点且叔叔节点为红色节点，根据红黑树性质 4，祖父节点肯定是黑节点。由于插入节点和父节点都是红色，最简单的方法就是变色。如下两图：
此时，以 PP 为根的子树已经平衡了，但是我们将祖父节点 PP 设置为红色，如果 PP 的父节点是黑色，那么就已经完美了；如果 PP 的父节点是红色，那么根据性质 4，将 PP 作为当前节点继续处理。
如果 PP 节点是整棵树的根节点，根据性质 2，必须再将 PP 节点重新设置为黑色节点。这时唯一一种会增杰黑色节点层数的情况。
情况 4.2
叔叔节点不存在或叔叔节点是黑色节点，且插入节点的父节点是祖父节点的左子节点。由于祖父节点一定是黑色节点，叔叔节点不是红色节点就一定是叶子节点（Nil）。因为如果叔叔节点是黑节点，而父节点是红色节点，叔叔节点所在的子树的黑色节点就会多于父节点所在子树，违反了性质 5。在插入前红黑树就不平衡了，这种情况不存在。所以 4.2 中，叔叔节点一定是 Nil 节点。情况 4.3 类似。
这时，就需要用到旋转操作了。情况 4.2 又细分为如下两种情况。
情况 4.2.1
插入节点是父节点的左子节点，对 PP 做右旋即可
当然，这种情况还有一种解法，就是将 P 设置为红色，I 和 PP 设置为黑色。但是这种解法将 P 变为红色，如果 P 的父节点也是红色，就必须向上调整了。
情况 4.2.2
插入节点是父节点的右子节点，这种情况可以转换为 4.2.1，如下：
接着按照 4.2.1 处理即可
情况 4.3
叔叔节点不存在或叔叔节点是黑色节点，且插入节点的父节点是祖父节点的右子节点。这种情况类似于 4.2，只是方向相反。
情况 4.3.1
插入节点是父节点的右子节点，对 PP 左旋即可：
情况 4.3.2
插入节点是父节点的左子节点，这种情况可以转换为 4.3.1，如下：
代码实现
我们讨论出了所有的情况，现在就可以用代码来实现了！
这里就不写插入的过程了，只写添加之后的自平衡过程，由于情况 1、2、3 插入之后不需要自平衡过程，所以这个方法针对情况 4。
/*
* 红黑树插入修正函数
*
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 插入的节点
*/
private void insertFixUp(Node node) {
Node parent, gparent;
// 若“父节点存在，并且父节点的颜色是红色”，情况 4
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父节点”是“祖父节点的左孩子”
if (parent == gparent.left) {
// Case 1 条件：叔叔节点是红色，情况 4.1
Node uncle = gparent.right;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是右孩子，情况 4.2.2
if (parent.right == node) {
Node tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是左孩子，情况 4.2.1
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else {
//若“z的父节点”是“z的祖父节点的右孩子”
Node uncle = gparent.left;
// Case 1条件：叔叔节点是红色，情况 4.1
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是左孩子，情况 4.3.2
if (parent.left == node) {
Node tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是右孩子，情况 4.3.1
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 将根节点设为黑色
setBlack(this.mRoot);
} 删除节点
插入节点已经够复杂了，但是插入节点还不是最复杂的操作。删除节点才是最复杂的操作。
删除节点的步骤与插入类似，也是首先查找到目标节点，删除后还需要自平衡。但是，删除节点之后，需要寻找一个节点来替代当前节点，否则子树和父节点之间就断开了。
替代节点有以下三种情形：
- 若删除的节点没有子节点，就无需替代节点
- 若删除节点只有一个子节点，用子节点替代删除节点
- 若删除节点有两个子节点，用后继节点（大于被删除节点的最小节点，即右子树的最左节点）替代删除节点
红黑树删除有一个重要的思路：删除节点被替代之后，在不考虑节点的键值的情况下，可以认为被删除的是替代节点。如下图：
如上图，不考虑键值的情况下，删除 P 的最终结果是删除了节点 Q。
基于这种思想，其实以上的三种替代情境都可以最终转换为情况 1：
- 情境 2，删除节点用其唯一子节点替换，相当于删除了子节点，如果子节点没有子节点，则相当于情况 1，如果子节点有子节点，相当于转换为情况 3
- 删除节点用后继节点替换，相当于删除后继节点，后继节点一定没有左子节点（否则就不是后继节点了），如果后继节点没有右子节点，则相当于情况 1，否则相当于情况 2
情况 2、3 可以不断相互转化，最终一定会转换成情况 1。
由以上思想，最终的替代节点一定在树的最下方。这个结论使我们讨论红黑树节点删除的情境少了很多，我们只需要考虑删除树末节点的情况。
更具体的情境如下：
1. 替换节点是红色
2. 替换节点是黑色
2.1 替换节点是父节点的左子节点
2.1.1 替换节点的兄弟节点是红色
2.1.2 替换节点的兄弟节点是黑色
2.1.2.1 替换节点的兄弟节点的右子节点是红色
2.1.2.2 替换节点的兄弟节点的右子节点是黑色，左子节点是红色
2.1.2.3 替换节点的兄弟节点的左右子节点都是黑色
2.2 替换节点是父节点的右子节点
2.2.1 替换节点的兄弟节点是红色
2.2.2 替换节点的兄弟节点是黑色
2.2.2.1 替换节点的兄弟节点的左子节点是红色
2.2.2.2 替换节点的兄弟节点的左子节点是黑色，右子节点是红色
2.2.2.3 替换节点的兄弟节点的左右子节点都是黑色同样为了方便叙述，我们将被替代的节点称为 R 节点，父节点称为 P 节点，兄弟节点为 S 节点，兄弟节点的左右子节点分别为 SL 和 SR。
以下我们来具体研究每个场景。
情况分析
情况 1
替换节点是红色节点，由于替换节点时红色，删除也了不会影响红黑树的平衡，所以直接把替换节点设置为被删除节点的颜色即可。
情况 2
替换节点是黑色节点，此时就必须进行自平衡处理，同时还得考虑到替换节点是父节点的左子树还是右子树，来进行不同的旋转。
情况 2.1
替换节点是其父节点的左子节点
情况 2.1.1
替换节点的兄弟节点是红色，根据性质 4，兄弟节点的父节点和子节点也肯定是黑色，做如下处理即可获得情况 2.1.2.3（此时 R 仍是替代节点）
情况 2.1.2
替换节点的兄弟节点是黑色，由于此时兄弟节点是黑色，无法确定兄弟节点的父节点和子节点的颜色，需要进一步分情况考虑
情况 2.1.2.1
替换节点的兄弟节点的右子节点是红节点，我们将要删除的是左子树的黑色节点，此时左子树的黑色节点就少了一个，这时就可以通过对 P 左旋向右子树借一个黑色节点。如下
注意这时的树看起来是不平衡的，S 的左子树有两个黑色节点，但实际上，R 节点是要被替换掉的节点，在实际操作之后，可以看作 R 最终被删除了。
情况 2.1.2.2
替换节点的兄弟节点的右子节点为黑节点，左子节点为红节点。兄弟节点所在的子树有红节点，我们总是可以向兄弟子树借个红节点过来，此情景就可以转换为 2.1.2.1，如下：
情况 2.1.2.3
替换节点的兄弟节点的子节点都为黑节点。这时兄弟子树就没有节点可借，无法通过旋转平衡红黑树。这种情景我们把兄弟节点设为红色，再把父节点当作替代节点，自底向上处理，去找叔叔节点去借。但为什么需要把兄弟节点设为红色呢？显然是为了在 P 所在的子树中保证平衡（R 即将删除，少了一个黑色节点，子树也需要少一个），处理如下：
此时 P 作为替换节点，继续向上调整子树。
情况 2.2
替换节点是其父节点的右子节点，方向与 2.1 相反而已，其他基本一致
情况 2.2.1
替换节点的兄弟节点是红节点，如下：
情况 2.2.2
替换节点的兄弟节点是黑节点
情况 2.2.2.1
替换节点的兄弟节点的左子节点是红节点
情况 2.2.2.2
替换节点的兄弟节点的左子节点为黑节点，右子节点为红节点
情况 2.2.2.3
替换节点的兄弟节点的子节点都为黑节点
代码实现
这里只展示已经删除完成并寻找到替代节点的情况，传入的参数是替代节点：
/*
* 红黑树删除修正函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明：
* node 待修正的节点
*/
private void removeFixUp(Node node, Node parent) {
Node other;
while ((node==null || isBlack(node)) && (node != this.mRoot)) {
// 情况 2.1
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// 情况 2.1.1
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// 情况 2.1.2.3
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.right==null || isBlack(other.right)) {
// 情况 2.1.2.2
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
// 情况 2.1.2.1
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mRoot;
break;
}
} else { // 情况 2.2
other = parent.left;
if (isRed(other)) {
// 情况 2.2.1
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// 情况 2.2.2.3
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left==null || isBlack(other.left)) {
// 情况 2.2.2.2
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// 情况 2.2.2.1
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mRoot;
break;
}
}
}
if (node!=null)
setBlack(node);
} END
最后祝大家面试的时候不会被问到红黑树。
#春招##Java##Java工程师#
投递快手等公司10个岗位