70 张图带你彻底掌握红黑树
原文链接：https://mp.weixin.qq.com/s/sjeZkcxj9RQ2AXcmWyZ_yA
前言
红黑树是工程中一种非常重要的数据结构，大家熟悉的 HashMap 在 Java 8 就引入了红黑树的数据结构，不过实话实说，红黑树确实不容易掌握，左旋，右旋等概念让人头发发麻，本文用图文并茂的形式以期让读者彻底掌握红黑树，希望大家看了有收获，这篇文章肝了十多天，非常不易，希望大家不要白嫖，三连走起，多谢支持!
开篇我们先来聊一聊和树相关的一些概念，来一步一步引入为什么要使用红黑树。这样能够让大家知其然而知其所以然，最后你会发现，红黑树的处理情况也就那几种，甚至可以说就固定那几种情况，多看看我的分析就能拿下了。话不多话，我们先从树的概念开始。
友情提示：本文篇幅比较长，但是总体而言简单易懂，还请各位坐稳。
1、树
树的定义如下
树是一种非线性的数据结构，它是由 n（n>=0）个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
1.每个节点有零个或多个子节点；
2.没有父节点的节点称为根节点；
3.每一个非根节点有且只有一个父节点；
4.除了根节点外，每个子节点可以分为多个不相交的子树
树的一些重要的名词解释
来结合一张图来更直观的理解下上面的各个名词的好含义
2、二叉树
虽然 H 节点只有一个子节点，但是它也是一个二叉树，因为满足最多只有个两个子节点
3、二叉搜索树
二叉搜索树其实就是二叉树，只不过又有一些额外的条件限制。其额外条件如下：
① 若它的左子树不为空，那么左子树上面的所有节点的值均小于它的根节点的值
② 若它的右子树不为空，那么右子树上面的所有的节点的值均大于它的根节点的值
③ 它的左右的树叶分别为二叉排序树
其中重点强调下二叉搜索树的中序遍历（因为这是最常见的）。中序遍历的规则是：先遍历左子树，再遍历根节点，然后遍历右子树
例如下面这个二叉搜索树的遍历的结果：D-H-B-E-A-F-C-G
如果从 A 的上面使用一个光源往下照，那么整个树的节点在地面上的投影其实就是中序遍历的结果。二叉搜索树的时间复杂度是 O（logn）
下面我们再来一起看下二叉搜索树的查找某个节点的算法（详细步骤全部使用注释写清楚了，因为红黑树就是基于二分查找树的，所以这里就多提一笔）
public class BinaryTreeDemo {
public static void main(String[] args) {
//前提这必须是一个有序的数组，否则是无法使用二分查找的
Integer[] searchArr = {1, 2, 3, 5, 6, 7, 9, 11, 23, 45, 67, 89};
//假设要查找 3 这个数据
Integer index = binarySearchTree(searchArr, 3);
System.out.println("index = " + index);
}
private static Integer binarySearchTree(Integer[] searchArr, int searchData) {
//定义数组的低位的索引
int lowBit = 0;
//定义数组的高位的索引
int heightBit = searchArr.length - 1;
//(heightBit - lowBit) / 2 得到的是两个位置的中间位置，再加上 low 就是实际的 heightBit 和 lowBit 的中间位置
//不懂的不用太纠结，重点是红黑树
while (lowBit <= heightBit) {
//这里为什么这么定义中间位置
//因为 （heightBit - lowBit）/2 结果是两者的相对中间点，再加上 lowBit 其实就是高位和低位的中间位置
//这里如果实在想不明白就去画画图，记住，不能写成（heightBit + lowBit）/2
int midBit = lowBit + (heightBit - lowBit) / 2;
//开始二分查找
//如果被查找的数据组的中间位置的值 小于 要搜索的值
//说明 searchData 在中间位置的右边
if (searchArr[midBit] < searchData) {
//这里为什么要 + 1 ？
// 因为 midBit 位置已经确定比 searchData 小了，所以需要从 midBit 的下一个索引位置开始继续找
// 也就是说 将 midBit 及 midBit 的左边的部分砍掉
lowBit = midBit + 1;
} else if (searchArr[midBit] == searchData) {
return midBit;
} else {
//这里的作用和 第一个 if 中的类似
//因为要查找的 searchData < 中间位置的索引，所以需要从索引位置的左边开始再次查找
//也就是说 直接将 midBit 及 midBit 右边的部分砍掉
heightBit = midBit - 1;
}
}
return null;
}
}
二分查找树的最大的缺点是依赖有序数组，而数组的缺点就是不能扩容，还有就是在添加和删除元素的时候需要移动数组，性能不理想。上面我们还说过一个问题，就是二叉树的特点就是每个节点的最多只有两个子节点，结合二叉搜索树的特点就是 左子节点 < 根节点 < 右子节点，那么在极端情况下，可能会出现下面这样的情况
在这种极端的情况下，可能会出现这种线性树结构，基本退化成链表了，那时间复杂度就变成了 O(n)。这个时间复杂度也太不稳定了，这种不稳定的东西在系统中就是定时炸弹。所以二叉搜索树被进一步的优化成 AVL 树
4、AVL 树
AVL 树也叫平衡二叉树，他的时间复杂度是 O(logn)
AVL 的左右树的高度差也叫平衡因子（平衡因子就是从某个节点开始，他的左右子树的节点数差），即平衡因子不大于 1。
但实际情况是根本不可能插入的数据这么巧的刚好一大一小的在左右树插入，所以 AVL 树在插入数据的时候会不断地调整，因为高度相差不大于 1 真的太严格了。那这样在频繁插入的时候必然需要一直调整树的结构，让其保持平衡。如下图（假设现在插入的不平衡的节点在左侧）
此时这种情况称之为左失衡，所以很显然需要进行右旋转（具体旋转会在红黑树中在介绍），右失衡的情况和此类似。可想而知不断地调整会导致性能低下。
说到这里，是不是机智的你也发现了树为啥会一步一步的进化演变，主要还是因为已有的功能无法满足新的需求，才会开始寻找新的解决办法。这就像架构一样，一开始是单体应用，随着业务量的提升，逐渐演变为了微服务架构。结构当前业务不断优化现有技术栈，才是架构的本质
5、2-3 树
有的小伙伴可能已经不耐烦了，怎么说好的红黑树，说半天还没到红黑树，难不成你是在摸鱼？
事实上如果上来就是红黑树我估计我自己看的都发懵，之所以一个又一个的铺垫，主要目的还是想让小伙伴们能有一次性拿下红黑树（手动滑稽）。好了，我们来继续说 2-3 树，2-3 树的特点是什么？它能够维持绝对的平衡，下面我们来演示下 2-3 树添加节点的过程
① 假设现在有一个节点 40，那啥也别说了，第一个节点啥都不做，老实呆着就行；
② 下一个节点 35 ，先从根节点开始，发现 40 > 35 ，此时理论上 35 应该添加到 40 的左子树上，但是对于 2-3 树，并不是你想的那样子，记住核心的一句话对于 2-3 树的添加，永远不会添加到一个空的节点去，只会跟最后找到的叶子节点做融合（不明白也没事，先把这个过程看完），那添加到哪里？实际上他们会这样存储：
现在这个变成了一个 3 节点。此时这颗树依旧是平衡的。
③ 下一个节点是 12 ，按照我们上面解释的 3 节点的含义，那既然 12 < 35 那是不是就是这样子的呢？
很显然不是，不要忘记了上面的那句核心的话（对于 2-3 树的添加，永远不会添加到一个空的节点去，只会跟最后找到的叶子节点做融合），因为此时 35 的左子节点是空，所以 12 是不可能添加进去的，实际上他是这么添加的
那这个时候按照 3 节点的定义，那这个岂不是 4 节点了？其实这个时候答案已经很明显了，就是此时该树会分裂成一个正常的二叉树，也就是这样子的，这棵树依旧是觉得平衡
④ 继续添加节点 18 ，自己能脑补下该怎么添加吗？这时候就很简单了，18 < 35 ，就添加到左子节点，此时左子节点不为空，那么就可以继续添加，而 18 > 12，理论上应该是添加到 12 的右子节点，但是由于对于 2-3 树的添加，永远不会添加到一个空的节点去，只会跟最后找到的叶子节点做融合。这个的理论指导，又因为此时 12 是一个 2 节点，所以即可进行融合，实际上它是这样子的
⑤ 继续添加 10 ，10 < 35， 到左子树查找，10 < 12 但是 12 的左子树为空，所以 10 先临时和 12 做一个融合
但是这个时候 12 节点已经变成了 4 节点，所以需要拆解，理论上是这样拆解的
但是这样的话 2-3 树就不是一颗绝对平衡的树了，显然不能这样拆解，或者是需要做其他操作来保持其绝对平衡。此时我们看上面的图，12 节点实际上是 10 和 18 的根节点了，接着往上查找，12 的父节点是 35 而其是一个 2 节点，所以 12 就顺理成章的和 35 融合起来，也就是下面这样子的
此时它又是一颗绝对平衡的 2-3 树了
⑥ 继续添加 11 ，那就很简单了，就不再一步一步解释了，添加后应该是这样子的
⑦ 別急，还没完，再来一个节点 8，那肯定就先是这样子的（一步一步画其转变的过程）
然后分裂，成这样子
但是很显然，此时的树已经失去平衡了，那就继续转换， 10 节点向上和根节点融合，但是此时 10 的父节点已经是一个 3 节点的树了，先融合进去再说
此时是 4 节点，已经不是 2-3 树了，所以下一步是这样演变的，直接将中间的（为什么是中间的？因为这个依旧符合二叉搜索树的特性，也就是左小右大）12 节点向上分裂，也就是最终是这样子的
到此，我忍不住喊了一声
2-3 树的时间复杂度是 Ologn，实际上红黑树就是由 2-3 树推导出来的，2-3 树和红黑树的关系是：2-3 树的插入和删除过程也可以对应到红黑树的旋转与颜色变换过程（至于红黑树的旋转和变色在红黑树中会重点讨论）。
那既然 2-3 树这么厉害，干嘛还要费那么大劲研究红黑树呢？那是因为对于 2-3 树我们需要维护两种不同类型的节点，查找和插入操作的实现需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。所以这才有个红黑树。
6、红黑树
上面为什么不常见的 2-3 树说了那么多？因为 2-3 树的插入和删除过程也可以对应到红黑树的旋转与颜色变换过程。下面我们先来了解下什么叫红黑树
红黑树的最大高度是 2logn，这看起来查找的效率并不是 AVL 树要好，红黑树的的添加和删除元素的时间复杂度是 O(logn)，因为他不会退化成想二叉搜索树的链表的结构
不要的自己听懂了，看完定义你一定一脸懵逼，别急，一步一步来，首先来画个图帮助大家理解
好，看到这里，小伙伴们一定是一头雾水，光说定义（网上到处都是）其实根本就无法解释清楚叫红黑树。
也就是说红黑树是一种平衡的检索树，上面的 AVL 树我们刚刚说了因为需要频繁的进行自平衡，所以在添加和删除节点的情况下性能是严重下降的，我们先来看下红黑树和 AVL 树的比较
那红黑树在添加和删除节点的时候是靠什么来维持平衡的呢？那就是左旋、右旋加变色
下面分别先来看下左旋、右旋加变色的定义
下图分别通过画图来拆解各个步骤（在演示旋转的时候我们先屏蔽掉颜色的干扰，单纯来看旋转的特性）
6.1、左旋
R 表示旋转节点，没有别的特殊的含义，以下的节点都是没有任何实际意义的
假设这是一个带旋转的树，假设以 R 点为旋转节点，根据左旋特性第一点：旋转节点的右子节点变为旋转节点的父节点
以上的图应该不难想象，先啥也不管，不是要左旋吗？那就直接找到旋转节点，然后将旋转节点的右子节点设置成旋转节点的父节点。下一步，将旋转节点的右子节点的左子节点设置为旋转节点的右子节点，再看下图
这就完事了，左旋的概念我们在一起加深下（因为这个对于红黑树的平衡起到核心作用）。左旋：以某个节点作为固定支撑点（围绕该节点旋转）,其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变
6.2、右旋
右旋：以某个节点作为固定支撑点（围绕该节点旋转），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。还是来看图
还是假设以 R 为旋转节点进行右旋，首先将 R 节点的左子节点 L 设置成 R 的父节点，完事后是下面这样子的
接着是第二小点，将 R 的左节点（L）的右子节点（LR）设置成 R 的左子节点，那根据上图应该直接就能想象出来了，那就是下面这样子的
就这？还头皮发麻不。
到此，这仅仅算是热身吧，这是万里长征的第一步，因为以下的所有的讲解都是在左旋右旋和变色的基础上讨论的（变色你不是还没介绍吗？黑色边红色，红色边黑色，介绍完了）
6.3、节点的查找
牢记一个原则，红黑树是基于二叉搜索树的，所以查找的特性和其是类似的，这个也不是重点，重点是红黑树的节点的添加，但是这里为啥非得提一嘴捏，因为插入节点的时候肯定要先查找定位嘛。
6.4、节点的添加
先回顾下红黑树的性质，为了不让各位来回翻页，小弟直接将其复制过来
添加实际上顺带了查找，所以在添加节点之前，必然要进行查找节点的位置，然后再插入节点，最后再自平衡。其中注意上面我自己添加的第 6 点，那就是新插入的节点一定是红色的（上面的第 6 点已经说的很清楚了，主要是为了防止一插入节点就破坏黑色完美平衡），不管后面怎么处理，新插入的节点只能是红色节点。
另外，我们还需要做如下的约定，假设新添加的节点为 I，I 的父节点为 P ，P 的兄弟节点为 U，P 父亲节点为（也就是 I 节点的爷爷节点） G，那这个结构是这样子的 （下图不要管字母的顺序，仅仅是表示一个节点的关系）
接下来是最难坚持的各种自平衡常见的分析了
下面开始进行各种情况的分析
第 1 种情况：红黑树为空树
那这还不好办嘛，插入的节点 I 就是根节点如下图：
咦？插入节点是红色节点没毛病，但是这个也是根节点啊？那就变色呗，所以当红黑树为空的时候新插入的节点直接变色即可。so easy~
第 2 种情况：插入的节点已经存在
还是画图来说，这样更直观
然后替换已有的 I 节点，如下图
此时很显然已经破坏了黑色完美平衡了，这个也好说，直接将 I 变色即可。第二种情况也不过如此嘛。
第 3 种情况：插入节点的父节点为黑色
假设待插入的节点为 Q ，那实际上应该是这样子的
完事了，为啥？因为这个树本来就是黑色完美平衡了，再新插入一个新的节点红色节点，并不会破坏树的平衡以及红黑树的特性（不要去研究为什么。科学家研究了好几年的东西，咱就不要再去深挖了）
第 4 种情况：插入节点的父节点为红色
万变不离其宗，继续回顾红黑树性质，插入的节点为红色，根节点为黑色，那既然插入的节点的父节点为红色节点，而红色节点一定不可能为根节点，所以可以推断出新插入节点的父节点一定还有父节点，也就是新插入的节点一定有爷爷节点。这里为什么这么强调，因为以后的平衡可能会涉及到类似的递归的自旋，直到平衡。类似这样子（不要关心字母的顺序，仅仅表示一个关系）
那现在很显然违反了上面的特性 3 每个【红色】节点的两个子节点一定都是【黑色】,而现在是两个红色节点相连了，这个该怎么处理？此时又继续拆分不同的情况了
第 4-1 种情况：插入节点的叔叔节点存在，且为红色
此时又可以推断出来叔叔节点的父节点一定是黑色，因为不能有两个红色节点相连（该特性和每个【红色】节点的两个子节点一定都是【黑色】是一个意思 ），所以这个时候你看的树大致是这样子的结构
以下的处理方式是固定的。只要是这种场景（我们以插入节点和插入节点的父节点以及插入节点的爷爷节点作为一个自旋整体），那么就按照这么处理：
① 将 P 和 U 变成黑色；② 将 PP 变成 红色。如下图：
那既然 PP 是根节点，那肯定不可能为红色了，接下来就是将 PP 当作是当前节点，然后继续判断处理。
先记住这个步骤，下面还会再说到，因为这个就是红色树的特性，既然性质都限制死了，那其实处理的方式也就那么几种。我们继续往下看
第 4-2 种情况：叔叔节点不存在或者为黑色，且插入节点的【父节点】是插入节点爷爷节点的【左子节点】
说了再多不如一张图搞定（不要忘记第四种情况的大前提，插入节点的父节点为红色）
实际上上图是稍微有点不合理的，因为这样子的就破坏了黑色完美平衡了，也就是说叔叔节点如果不是红色，那肯定也不可能是黑色的，那剩下的只能是 NULL，下面这张图才是比较合适的表达 4-2 的情况。
等等，为啥说是比较合适的？因为插入的节点可能为其父节点的左子节点，也可能是其父节点的右子节点。下面这样图才是完美的
那既然不确定是左子节点还是右子节点，那肯定是要继续分情况了呗，没错
第 4-2-1 种情况：插入节点为其父节点的左子节点，也即 LL 双红色的情况（第一个 L 表示插入节点的父节点，第二个 L 表示插入节点）
那这种情况肯定就是这样子的了
这个怎么搞了？我说接下来更简单你可能会不行，因为就像我刚刚上面说的，步骤都是固定的，接下来为了平衡，步骤为：
① 将 P 节点变成黑色，将 PP 节点变成 红色
② 对 PP 节点进行右旋（以 PP 节点为旋转节点，进行右旋）
右旋的特点还记得不？右旋：旋转节点的左子节点变成其父节点，旋转节点的左子节点的右子节点变成旋转节点的左子节点，那这个旋转节点的左子节点的右子节点不是为 NULL 嘛？那就不管呗，所以，以 PP 为旋转节点的旋转后的结果是：
其完整的变换流程如下：
第 4-2-2 种情况：插入节点为其父节点的左子节点，也即 LR 双红色的情况
这个时候处理方式依旧是固定的，就是将其变成 LL 双红的情况，然后按照 LL 双红的情况去处理。那么问题来了，该如何才能变成 LL 双红的情况呢？依旧是固定的套路，直接按照以下的步骤操作：
① 将 P 节点作为旋转节点，进行左旋，其结果是这样子的
② 这个时候就变成了了熟悉的味道了，接下来就按照 LL 双红的情况来处理：① 将 I 变成黑色，将 PP 变成红色，② 然后以 PP 为旋转节点，进行右旋
其完成的变换流程如下：
第 4-3 种情况：叔叔节点不存在或者为黑色，且插入节点的【父节点】是插入节点爷爷节点的【右子节点】
4-3 这种情况和 4-2 刚好反过来，但是我还是会一步一步来介绍的
这种情况依旧是继续区分插入节点是其父节点的左子节点还是右子节点
第 4-3-1 种情况：插入节点为其父节点的右子节点，也即 RR 双红色的情况（第一个 R 是插入节点的父节点，第二个 R 是插入节点）
也就是下面这样子的
处理步骤如下：
① 将 P 设置为 黑色，将 PP 设置为红色
② 以 PP 节点为旋转节点，进行左旋
其整个转换流程是这样的
第 4-3-1 种情况：插入节点为其父节点的右子节点，也即 RL 双红色的情况
你是不是觉得对于这种情况那不就是应该先将 RL 转换成 RR 这种情况吗？没错，就是这样，我发现你都开始学会抢答了。
这个时候处理的步骤是这样子的：首先以 P 节点为旋转节点，进行右旋，结果是这样子的
然后将 I 设置为 黑色，将 PP 设置为红色
然后以 PP 为旋转节点，进行左旋
其完整的转换流程是这样子的：
好了，我们赶紧做个总结，相信很多小伙伴看了上面的各种情况基本已经凌乱了，甚至都没看到这里就撤了。。下面我们将各个情况总结如下
6.5、结束语
最后我们再来对红黑树自平衡的各个情况做个总结：
还未添加个人签名 2020.09.02 加入
还未添加个人简介
评论