图解红黑树
写在前面
红黑树也是一棵二叉查找树，既然有了 AVL 树为什么还需要红黑树呢？
之前在了平衡二叉树AVL实现中讲到了为什么使用平衡二叉树 AVL（解决二叉查找树退化为类似链表的问题），最大的作用就是用于查找，其时间复杂度为 O(logn)，但 AVL 树插入或删除节点后，若使得高度之差大于 1，此时，AVL 树的平衡状态就被破坏，需要旋转才能达到平衡。因此如果在插入和删除频繁的场景中就需要频繁的调整使之达到平衡，性能也随之下降。
因此，红黑树的提出是为了解决平衡树在插入和删除等操作频繁的情况。
在了解红黑之前先看看 2-3-4 树。
2-3-4 树
在二叉树中，每个节点有一个数据项（可以理解为节点的值，key），最多有 2 个子节点。如果允许每个节点可以有更多的数据项和子节点，就是多叉树，2-3-4 树就属于多叉树，并且还是平衡树（B 树）。
2-3-4 树是一种阶（阶，可以理解为节点的分支）为 4 的 B 树，所以也可称它为 4 叉树，主要具备以下性质：
有 1 个 key 的节点有 2 个子节点，有 2 个 key 的有 3 个子节点，有 3 个 key 的有 4 个子节点，对应 key 的节点分别称为 2 节点，3 节点，4 节点，这也是为什么叫 2-3-4 树的原因
所有的叶子节点总在同一层
每个节点的值从左到右保持了从小到大的顺序，两个 key 之间的子树中所有的 key 一定大于它的父节点的左 key，小于父节点的右 key。如下
如下面这棵 2-3-4 树：
在上图中：
有 2 个链接的为 2 节点
有 3 个链接的为 3 节点
有 4 个链接的为 4 节点
插入操作
2-3-4 树的插入总是在叶子节点且一般不允许插入重复的 key。
若插入时的叶子节点不是满节点（即 4 节点），如插入数据 45，如下：
节点分裂
如果插入节点是 4 节点，这时候节点就需要分裂才能保证树的平衡（这里假设分裂的节点不是根节点），一个 4 节点可以分裂成一个根节点和两个子节点（这三个节点各含一个 key）然后在子节点中插入。若分裂的节点数据分别用 ABC 来表示：
若分裂节点的父节点也是满节点，则按照分裂操作继续分裂即可。
2-3-4 树的删除如果感兴趣的可自己去百度，网上很多
红黑树
红黑树也是一棵二叉查找树，也是一棵自平衡树，具备以下性质：
节点是红色或黑色（非黑即红）
根节点是黑色
所有的 null 节点称为叶子节点，且都是黑色
所有红色节点的子节点都是黑色（即没有连续的红色节点）
任意一个节点到其叶子节点的所有路劲都包含相同数目的黑色节点
如下面这个常见的红黑树：
通过以上性质，可以推出：从根节点到叶子节点的最长路径不会超过最短路径的 2 倍
为什么？
根据上面的性质 5 我们知道下图的红黑树每条路径上都是 3 个黑结点。因此最短路径长度为 2(没有红结点的路径)。再根据性质 4(没有连续的红色节点)和性质 2，3(叶
子和根必须是黑结点)。那么我们可以得出：
最短路径：一条具有 3 个黑结点的路径上最多只能有 2 个红结点(红黑间隔存在)，最短路径为 2。
最长路径：黑深度为 2（根结点也是黑色）的红黑树最长路径为 4。
从这一点我们可以看出红黑树是大致平衡的。 (比平衡二叉树要差一些，AVL 的平衡因子最多为 1)
注：若以下有说到性质 1-5，分别表示上述性质，如性质 2 表示“根节点是黑色”。
2-3-4 树和红黑树的等价关系
红黑树起源于 2-3-4 树，一颗红黑树对应一颗确定的 2-3-4 树，一颗 2-3-4 树对应多个红黑树。
上面的 2-3-4 树和红黑树看上去完全不同，但实际上是等价的，通过一些规则可以让 2-3-4 树变为红黑树，如：
上图中 3 节点存在 2 种情况：
右倾：红色在右边
左倾：红色在左边
因此，这就决定了一颗红黑树对应一颗确定的 2-3-4 树，一颗 2-3-4 树对应多个红黑树。
然后我们把最开始的那棵 2-3-4 树按照上面的规则转化为红黑树，如下：
节点之间的转化对应如下：
由规则生成的红黑树：
那么到底 2-3-4 树和红黑树是怎么对应的？就是上面简单的替换吗？那我插入或删除的时候怎么调整，通过什么规则去调整，我们继续往下分析。
左倾红黑树
在上面等价替换中，3 节点可以转化为 2 中不同类型的红黑树，即左倾红黑树和右倾红黑树，下面的内容主要通过左倾红黑树来讲解。
那什么是左倾红黑树呢？
一个节点要么有一个子节点，要么有两个子节点，如果有一个红色子节点，那么这个子节点只能在左边，如果有 2 个红色子节点，那就是两边都是红色。右倾红黑树同理：
了解了左倾红黑树，我们再看看红黑树的调整和它以及 2-3-4 树有什么关系，继续往下看。
红黑树的调整
插入操作
根据上面的性质，如果我们在插入一个元素的时候违反了，此时我们需要调整才能使其遵守上述性质。而调整方式只有以下 2 种可能：
改变节点的颜色
对节点进行旋转
旋转和变色
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变
这里的插入操作主要通过从插入节点的过程和左倾红黑树以及右倾红黑树的规则来分析插入过程中存在的情况。
基本定义：
叔父节点：指新节点的父节点的兄弟节点（若不存在叔父节点，则用 null 表示）
祖父节点：指新节点的父节点的父节点
插入原则：插入的新节点默认为红色节点
下面的 1-5 序号表示从根节点（包括根节点）开始插入的第几个节点。
创建一棵红黑树（
13为根节点，这里不展示 null 节点），根据红黑树的性质：根节点是黑色
插入第二个节点，此时会存在两种情况
若插入的节点小于 13，则该节点为 13 的左子节点，若插入节点
8，此时它就是一棵红黑树，也符合左倾红黑树的规则。
若插入的节点大于 13，则该节点为 13 的右子节点，若插入节点
17。
此时，节点 17 为右子节点，不符合左倾红黑树的规则，那么怎么调整使其平衡？我们上图还原为一棵 2-3-4 树：
这个 2-3-4 树其实就是一个 3 节点，按照左倾的规则（父节点黑色，子节点红色）把它变为一棵左倾红黑树：
我们把对比一下 2-3-4 树和红黑树的插入：
通过上图可以看出，对 2-3-4 树来说就是一个 3 节点，对红黑树来说就是插入一个右子节点，做一次左旋转变色。如果说不左倾的话，那就是第一种情况，既不用旋转也不用变色
通过 1，2 两步操作我们可以得出第一种情形：
情形一：插入的新节点位于树的根上或插入的新节点的父节点是黑色，无需做任何操作即可使其平衡
插入第三个节点，以节点 13 和 17 为例，此时存在 3 种情况
若插入的节点小于 13，则该节点为 13 的左子节点，若插入节点 8
根据红黑树的性质不能有连续的红色节点，所以需要对它做调整使其平衡，那么怎么调整使其平衡？我们还是还原为一棵 2-3-4 树：
再对比一下 2-3-4 树和红黑树的插入：
通过上图可以看出，对 2-3-4 树来说就是一个 4 节点，2-3-4 树要变成一棵左倾红黑树就就是父黑子红。对红黑树来说就是插入一个左子节点，做一次右旋转然后变色。这里的变色怎么理解？就理解为 2-3-4 树变红黑树，父黑子红。
由于左倾的原因，新节点为其父节点的左子节点，父节点也是其父节点的左子节点，可以得出第二种情形：
情形二：插入的新节点的父节点是红色，叔父节点为黑色（若没有则是 null 节点，null 节点为黑色节点），且新节点为其父节点的左子节点，父节点也是其父节点的左子节点。这种情形只需要一次右旋变色即可。
这里其实可以联想一下，上面的节点 13 和 17 通过左倾使得 13 为 17 的左子节点，如果不左倾，按照插入的顺序来，应该是这样的：
所以，若此时我插入节点大于 17，那么刚好和情形二相反，若插入节点 25：
这里就可以非常简单的推出第三种情形：
情形三：插入的新节点的父节点是红色，叔父节点为黑色（若没有则是 null 节点，null 节点为黑色节点），且新节点为其父节点的右子节点，父节点也是其父节点的右子节点。这种情形需要一次左旋变色即可。
若插入的节点比 13 大，比 17 小，则该节点为 13 的右子节点，若插入节点 15
肯定也是不符合红黑树的性质的，这里直接查看对比图：
这种情况可以看到，插入节点还是形成了一棵 2-3-4 树，在按照左倾的规则，先左旋，这时就和上面的情况相同，然后再右旋，在变色，也就形成了最终的红黑树。
情形四：插入的新节点的父节点是红色，叔父节点为黑色（若没有则是 null 节点，null 节点为黑色节点），且新节点为其父节点的右子节点，父节点是其父节点的左子节点。这种情形需要先进行一次左旋，然后右旋，最后变色即可。
同样，若不左倾，当插入节点 15：
情形五：插入的新节点的父节点是红色，叔父节点为黑色（若没有则是 null 节点，null 节点为黑色节点），且新节点为其父节点的左子节点，父节点是其父节点的右子节点。这种情形需要先进行一次右旋，然后左旋，最后变色即可。
若插入的节点比 17 大，则该节点为 17 的右子节点，若插入节点 25
此时，它就是一棵满足条件的红黑树，这种情形就是情形一，无需做任何操作。
所以，连续插入 3 个节点，对于 2-3-4 树形成一个 4 节点，对于红黑树，形成都是这样：
插入第四个节点，以节点 13，17，25 为例，此时可能存在 4 种情况，即第四个节点可能为 13 的左子节点，右子节点，25 的左子节点，右子节点。
若为 13 的左子节点 ，插入节点 11，即插入节点在根节点的左边
上图中的变色实际就对应 2-3-4 树的 3 节点，3 节点左倾变为父黑子红的左倾红黑树，2 节点对应黑色节点。
若为 13 的右子节点，插入节点 15，即插入节点在根节点的左边
上图中是按照左倾的方式来处理的，如果不左倾则简单很多，因为不需要左旋，直接变色即可，如下：
若为 25 的左子节点 ，插入节点 22，即插入节点在根节点的右边
若为 25 的右子节点 ，插入节点 27，即插入节点在根节点的右边
如果不左倾直接变色即可：
上面通过插入第四个节点的分析，可以看到新节点插入时，其父节点和叔父节点都是红色，若不考虑左倾，它们都是只做了变色操作，所以得出情形六：
情形六：若插入节点的父节点和叔父节点都是红色，则做变色操作即可使其平衡。
至此，红黑树插入节点的情形都分析完成，如果理解了 2-3-4 树到红黑树的转变，就不用去死记插入节点时会碰到那些情况。
小结
通过上面插入操作的分析，插入的情形可以总结出以下几点：
若插入新节点为根节点或者父节点为黑色，则无需做任何操作（黑父）
若插入新节点的父节点和叔父节点都是红色，则做变色操作即可（红父红叔）
若插入新节点的父节点为红色，叔父节点为黑色（红父黑叔）
若新节点及左子节点，父节点为左子节点，先右旋再变色（子左父左）
若新节点为右子节点，父节点为左子节点，先左旋再右旋再变色（子右父左）
若新节点为左子节点，父节点为右子节点，先右旋再右旋再变色（子左父右）
若新节点为右子节点，父节点为右子节点，先左旋再变色（子右父右）
删除操作
红黑树的删除如果还原为 2-3-4 树分析个人感觉复杂很多，所以这里还是按照二叉排序树的删除方式来分析。红黑树的删除和二叉排序树类似，也分为 3 种情况，即删除节点无子节点，有 1 个子节点和有 2 个子节点三中情况，也就是说红黑树的删除要先考虑是否有子节点再考虑删除节点的颜色。所以在红黑树的删除中，存在 6 种情形（3*2）。
无子节点
情形一：删除节点无子节点 ，且删除节点为红色
由红黑树的性质 4 和 5 可知，若删除节点为红色，则其父节点必为黑色，所以这种情况不会破坏红黑树的性质，直接删除即可。如下图删除节点27
情形二：删除节点无子节点，且删除节点为黑色
这种情况是比较复杂的，建议先看完其他几种在回头来看。
情形二的删除情形又分为以下几种：
① 删除节点的兄弟节点为黑色，且兄儿子与兄同边（左或右）红色
上图中，删除节点 D，则经过 D 路径的黑色节点减少 1 个，以 P 为支点旋转，将 B 节点旋转（左旋）到 P 的位置，并把与 B 同边的 BS 节点变为黑色，P 节点变为黑色，并将替代节点 null 删除，达到局部平衡。
同理，若节点 D 在右边，节点 B，BS 在左边，那就是右旋+变色即可达到平衡。
② 删除节点的兄弟节点为黑色，且兄儿子与兄不同边（左或右）红色
将 BS 和 B 旋转（右旋），变色，变成①。
同理，节点 D 在右边，节点 B，BS 在左边，左旋+变色，变成①。
③ 删除节点的兄弟节点为黑色，且兄弟节点的子节点为黑色
若删除节点的父节点 P 为红色
删除 D，经过 D 节点的路径上黑色就少了一个，这个时候可以把 P 变成黑色，这样删除 D 后经过 D 节点路径上的黑色节点就和原来一样了。但是这样会导致经过 B 节点的路径上的黑色节点数增加一个，所以这个时候可以再将 B 节点变成红色，这样路径上的黑色节点数就和原来保持一致。
若删除节点的父节点 P 也为黑色
D 节点删除之后，不管怎么变色都无法使左右平衡，因为左边少了一个黑色节点，若将 D 的兄弟节点 B 变为红色，P 节点的左右子树的黑色节点相同，但是经过 PB 路径的黑色节点会减少 1，所以此时需要对 P 节点（把 P 当做要删除的节点分析，但不是真的删除）进行平衡操作。
④ 删除节点的兄弟节点为红色
若删除节点的兄弟节点为红色，则其父节点必为黑色，且 B 的子节点也为黑色节点
这里我们把节点 B 进行左旋和变色操作：
从上图可以看出旋转之后删除节点 D 的兄弟节点变为了黑色节点 BSL，这就是前面分析的情形①或②。
这里就可以解释为什么红黑树的删除最多需要三次旋转：
若 BSL 的右子节点为红色，则符合情形①，经过一次旋转变色，共 2 次旋转。
若 BSL 的左子节点为红色，则符合情形②，经过一次旋转变色符合情形①，共 3 次旋转。
所以整个过程只需要旋转三次即可达到平衡，这也是为什么删除要优于 AVL 的原因。
有一个子节点
情形三：删除节点有一个子节点，且删除节点为红色
这种情况如下：
由红黑树的性质 4 和 5 可知，在构建一棵红黑树的时候，任意节点的路径都具有相同的黑色节点，且红色节点和红色
节点不连续，所以若删除节点为红色其子节点必为黑色，这样就破坏了性质 5，所以这种情况在构建红黑树的时候
就不会存在，所以删除的情况也不会存在。
情形四：删除节点有一个子节点，且删除节点为黑色
若删除节点为黑色，则其子节点必为红色（为黑色则不满足性质 5），所以删除节点后只需要用子节点替换然后变
色即可（因为黑色节点被删除，由于性质 5，所以需要把子节点在变为黑色）。如删除节点8：
有两个子节点
节点的删除可以通过前驱节点（删除节点左子树中的最大值）或后继节点（删除节点右子树中的最小值）替换掉要删除的节点，若通过后继节点删除，存在 2 种情况：
所以，用后继节点代替要删除节点，转化为删除后继节点，通过判断后继节点的删除来调整。
若后继节点是①的情况：
情形五：删除节点有 2 个子节点
若后继节点 successor 为红色
没有右子节点，对应情形一
若存在右子节点，只能为黑色，不满足性质 5，对应情形三
若后继节点 successor 为黑色
没有右子节点，对应情形二
若存在右子节点，不能为黑色，只能为红色，对应情形四
若后继节点是②的情况：
情形六：删除节点有 2 个子节点
若后继节点 successor 为红色
没有子节点，对应情形一
若存在子节点，只能为黑色，不满足性质 5，对应情形三
若后继节点 successor 为黑色
没有子节点，对应情形二
若存在子节点，只能为红色，对应情形四
有 2 个节点的删除通过后继节点的方式，如果是前驱节点的方式，可能又是不一样的，但分析过程却是差不多的。
小结
这里的红黑树的删除是根据删除节点是否存在子节点来分析的，但总结一下上面的六种情形，情形五和情形六同时被转化为上面的一，二，四，所以我们只需要掌握这三种即可。
判断属于那种情形的时候，通过下面的顺序：
先看删除节点的颜色
再看兄弟节点的颜色
再看兄弟子节点的颜色（兄弟子节点先看兄弟右子节点右再看兄弟左子节点）
最后看父节点的颜色
红黑树和 AVL 的区别
所以，在实际应用中，若搜索的次数远远大于插入和删除，那么选择 AVL，如果搜索，插入删除次数几乎差不多，应该选择 RB。
总结
在学习红黑树的时候查阅了很多资料，同时也让我很头疼，比如它和 AVL 的增删效率到底怎么去计算，明明在新增的时候旋转的次数都是两次，有的博文却说 AVL 要高于 2 次，10 篇文章就有 10 种说法，但是我还是坚持自己在实际操作中所记录下的。
本来准备把代码贴上来，但是我觉得没必要，因为在面试中也不会有面试官叫你手写红黑树，如果有，请把键盘给他，他行他上。而且对于我们实际开发也没有太大用处，也可能一辈子都不会去手写一个红黑树，比如你不会去自己实现 HashMap，所以没有必要动不动就什么死磕红黑树的，我们只需要知道他的基本逻辑就行了，如新增的时候怎么旋转保持平衡，删除的时候怎么旋转保持平衡的逻辑就够了。而在你有一定代码能力之后，很可能你就自己能写一个简单的 demo 了，写代码的前提就是要清晰的知道逻辑。
这里还是把代码提供出来，需要的可自行去下载：
之前有人问上面的动图是怎么做的，数据结构可视化：
参考
版权声明: 本文为 InfoQ 作者【阿粤Ayue】的原创文章。
原文链接:【http://xie.infoq.cn/article/28d477cfd51aa404df2bfedaa】。文章转载请联系作者。
微信搜：Javatv 2019.10.16 加入
秘密基地：javatv.net
评论