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