Java 集合 | 红黑树 | 前置知识
一、前言
为啥要学红黑树吖？
因为笔者最近在赶项目的时候，不忘抽出时间来复习 Java 基础知识，现在准备看集合的源码啦啦。听闻，HashMap 在 jdk 1.8 的时候，底层的数据结构发生了变化，变成了数组+链表+红黑树。很好，没了解过红黑树，所以就趁今天闲暇学习一下啦
二、什么是红黑树？
2.1 有啥用处？
红黑树从本质上来说就是一颗二叉查找树，但是在二叉树的基础上增加了着色相关的性质，使得红黑树可以保证相对平衡，从而保证红黑树的增删改查的时间复杂度最坏也能达到 O(log N)。
2.2 红黑树的六条性质你知道吗？
-
每个节点要么是黑的，要么是红的 -
根节点是黑的 -
叶节点是黑的 -
如果一个节点是红的，他的两个儿子节点都是黑的 -
对于任一节点而言，其到叶节点树尾端NIL指针的每一条路径都包含相同数目的黑节点。这其实就是黑高啦！ -
新插入的节点必须是红色噢！
2.3 插入操作
首先，先看这个图吧，这就是全部的插入操作后，平衡的方法啦！其实我还是喜欢用笔画 hhh
红黑树的概念理解起来较为复杂，我们以一个简单的示例，看看如何构造一棵红黑树。
现有数组int[] a = {1, 10, 9, 2, 3, 8, 7, 4, 5, 6};我们要将其变为一棵红黑树。
首先插入1，此时树是空的，1就是根结点，根结点是黑色的：
首先插入 1，此时树是空的，1 就是根结点，根结点是黑色的：
插入 1
然后插入元素 10，此时依然符合规则，结果如下：
插入 10
当插入元素 9 时，这时是需要调整的第一种情况，结果如下：
插入 9
红黑树规则 4 中强调不能有两个相邻的红色结点，所以此时我们需要对其进行调整。调整的原则有多个相关因素，这里的情况是，父结点 10 是其祖父结点 1（父结点的父结点）的右孩子，当前结点 9 是其父结点 10 的左孩子，且没有叔叔结点（父结点的兄弟结点），此时需要进行两次旋转，第一次，以父结点 10 右旋：
右旋
然后将父结点**（此时是 9）**染为黑色，祖父结点 1 染为红色，如下所示：
染色
然后以祖父结点 1 左旋：
左旋
下一步，插入元素 2，结果如下：
插入 2
此时情况与上一步类似，区别在于父结点 1 是祖父结点 9 的左孩子，当前结点 2 是父结点的右孩子，且叔叔结点 10 是红色的。这时需要先将叔叔结点 10 染为黑色，再进行下一步操作，具体做法是将父结点 1 和叔叔结点 10 染为黑色，祖父结点 9 染为红色，如下所示：
染色
由于结点 9 是根节点，必须为黑色，将它染为黑色即可：
染色
下一步，插入元素 3，如下所示：
插入 3
这和我们之前插入元素 10 的情况一模一样，需要将父结点 2 染为黑色，祖父结点 1 染为红色，如下所示：
染色
然后左旋：
左旋
下一步，插入元素 8，结果如下：
插入 8
此时和插入元素 2 有些类似，区别在于父结点 3 是右孩子，当前结点 8 也是右孩子，这时也需要先将叔叔结点 1 染为黑色，具体操作是先将 1 和 3 染为黑色，再将祖父结点 2 染为红色，如下所示：
染色
此时树已经平衡了，不需要再进行其他操作了，现在插入元素 7，如下所示：
插入 7
这时和之前插入元素 9 时一模一样了，先将 7 和 8 右旋，如下所示：
右旋
然后将 7 染为黑色，3 染为红色，再进行左旋，结果如下：
左旋
下一步要插入的元素是 4，结果如下：
插入 4
这里和插入元素 2 是类似的，先将 3 和 8 染为黑色，7 染为红色，如下所示：
染色
但此时 2 和 7 相邻且颜色均为红色，我们需要对它们继续进行调整。这时情况变为了父结点 2 为红色，叔叔结点 10 为黑色，且 2 为左孩子，7 为右孩子，这时需要以 2 左旋。这时左旋与之前不同的地方在于结点 7 旋转完成后将有三个孩子，结果类似于下图：
错误示意图
这种情况处理起来也很简单，只需要把 7 原来的左孩子 3，变成 2 的右孩子即可，结果如下：
调整
然后再把 2 的父结点 7 染为黑色，祖父结点 9 染为红色。结果如下所示：
染色
此时又需要右旋了，我们要以 9 右旋，右旋完成后 7 又有三个孩子，这种情况和上述是对称的，我们把 7 原有的右孩子 8，变成 9 的左孩子即可，如下所示：
右旋
下一个要插入的元素是 5，插入后如下所示：
插入 5
有了上述一些操作，处理 5 变得十分简单，将 3 染为红色，4 染为黑色，然后左旋，结果如下所示：
左旋
最后插入元素 6，如下所示：
插入 6
又是叔叔结点 3 为红色的情况，这种情况我们处理过多次了，首先将 3 和 5 染为黑色，4 染为红色，结果如下：
染色
此时问题向上传递到了元素 4，我们看 2、4、7、9 的颜色和位置关系，这种情况我们也处理过，先将 2 和 9 染为黑色，7 染为红色，结果如下：
染色
最后 7 是根结点，染为黑色即可，最终结果如下所示：
2.4 删除操作
删除的规则如下：
要从一棵红黑树中删除一个元素，主要分为三种情况。
情况 1：待删除元素没有孩子
没有孩子指的是没有值不为 NIL 的孩子。这种情况下，如果删除的元素是红色的，可以直接删除，如果删除的元素是黑色的，就需要进行调整了。
例如我们从下图中删除元素 1：
红黑树
删除元素 1 后，2 的左孩子为 NIL，这条支路上的黑色结点数就比其他支路少了，所以需要进行调整。
这时，我们的关注点从叔叔结点转到兄弟结点，也就是结点 4，此时 4 是红色的，就把它染为黑色，把父结点 2 染为红色，如下所示：
染色
然后以 2 左旋，结果如下：
左旋
此时兄弟结点为 3，且它没有红色的孩子，这时只需要把它染为红色，父结点 2 染为黑色即可。结果如下所示：
调整完毕
情况 2：待删除元素有一个孩子
这应该是删除操作中最简单的一种情况了，根据红黑树的定义，我们可以推测，如果一个元素仅有一个孩子，那么这个元素一定是黑色的，而且其孩子是红色的。
假设我们有一个红色节点，它是树中的某一个节点，且仅有一个孩子，那么根据红色节点不能相邻的条件，它的孩子一定是黑色的，如下所示：
红色节点仅一个孩子
但这个子树的黑高却不再平衡了（注意每个节点的叶节点都是一个 NIL 节点），因此红色节点不可能只有一个孩子。
而若是一个黑色节点仅有一个孩子，如果其孩子是黑色的，同样会打破黑高的平衡，所以其孩子只能是红色的，如下所示：
黑色节点仅一个孩子
只有这一种情况符合红黑树的定义，这时要删除这个元素，只需要使用其孩子代替它，仅代替值而不代替颜色即可，上图的情况删除完后变为：
删除完毕
可以看到，树的黑高并没有发生变化，因此也不需要进行调整。
情况 3：待删除元素有两个孩子
我们在讨论二叉排序树时说过，如果删除一个有两个孩子的元素，可以使用它的前驱或者后继结点代替它。因为它的前驱或者后继结点最多只会有一个孩子，所以这种情况可以转为情况 1 或情况 2 处理。
删除元素最复杂的是情况 1，这主要由其兄弟结点以及兄弟结点的孩子颜色共同决定。这里简要做下总结。
我们以 N 代表当前待删除节点，以 P 代表父结点，以 S 代表兄弟结点，以 SL 代表兄弟结点的左孩子，SR 代表兄弟结点的右孩子，如下所示：
图样
根据红黑树定义，这种情况下 S 要么有红色的子结点，要么只有 NIL 结点，以下对 S 有黑色结点的情况均表示 NIL
主要有以下几种：
-
S 是红色，P 一定是黑色，S 也不会有红色的孩子，如下：
红色兄弟结点
此时把 P 和 S 颜色变换，再左旋，如下：
左旋
这样变换后，N 支路上的黑色结点并没有增加，所以依然少一个，
-
P，S 以及 S 的全部孩子都是黑色
无论 S 有几个孩子，或者没有孩子，只要不是红色都是这种情况，此时情况如下：
全黑色
我们把 S 染为红色，这样一来，N 和 S 两个支路都少了一个黑色结点，所以可以把问题向父结点转移，通过递归解决。染色后如下：
染色
-
P 为红（S 一定为黑），S 的孩子都为黑
这种情况最为简单，只需要把 P 和 S 颜色交换即可。这样 N 支路多了一个黑色元素，而 S 支路没有减少，所以达到了平衡。
交换前
交换后
-
P 任意色，S 为黑，N 是 P 的左孩子，S 的右孩子 SR 为红，S 的左孩子任意
如下所示
任意色
此时将 S 改为 P 的颜色，SR 和 P 改为黑色，然后左旋，结果如下：
左旋
可以发现，此时 N 支路多了一个黑色结点，而其余支路均没有收到影响，所以调整完毕。
-
P 任意色，S 为黑，N 是 P 的左孩子，S 的左孩子 SL 为红，S 的右孩子 SR 为黑，如下所示：
img SR 黑色
此时变换 S 和 SL 的颜色，然后右旋，结果如下：
右旋
这时，所有分支的黑色结点数均没有改变，但情况 5 转为了情况 4，再进行一次操作即可。
还有一些情况与上述是对称的，我们进行相应的转换即可。
红黑树的操作比较复杂，插入元素可能需要多次变色与旋转，删除也是。这些操作的目的都是为了保证红黑树的结构不被破坏。这些复杂的插入与删除操作希望大家可以亲手尝试一下，以加深理解。
三、结语
红黑树其实一开始看起来有点懵逼懵逼的，但是，其实你看完了全文，然后手动模拟一下插入删除操作，发现也不是想象中的很难啦！
附上笔者学习红黑树做的草稿hhh 如果还是看不明白，推荐一个视频：红黑树原理源码讲解（java），全B站讲解最细致版本，看完月薪最少涨5k！
如果文章对您有一点帮助的话，希望您能点一下赞，您的点赞，是我前进的动力
本文参考链接：
本文使用 mdnice 排版
