共计 2653 个字符，预计需要花费 7 分钟才能阅读完成。
说到 HashMap，就一定要说到红黑树，红黑树作为一种自平衡二叉查找树，是一种用途较广的数据结构，在 jdk1.8 中使用红黑树提升 HashMap 的性能，今天就来说一说红黑树，上一讲已经给出插入平衡的调整操作，这一讲就说说更为复杂的删除平衡操作。
前言
限于篇幅，本文只对红黑树的基础进行说明，暂不涉及源码部分，大部分摘抄自维基百科，这里也贴出对应链接：
维基百科 (中文)：https://zh.wikipedia.org/wiki…
维基百科：https://en.wikipedia.org/wiki…
笔者这里会根据维基百科的讲解做些说明，方便初学者理解。
删除平衡
在正式进入红黑树的删除说明之前，想下二叉搜索树中的删除是如何做的？
参照二叉搜索树的删除调整原理：
如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题（为了表述方便，这里所指的儿子，为非叶子节点的儿子）。对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们要么找到它左子树中的最大元素、要么找到它右子树中的最小元素，并把它的值转移到要删除的节点中（如在这里所展示的那样）。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值（没有复制颜色），不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。
那么红黑树中会出现哪些情况呢？
删除节点的左右子树都非空
删除节点的左子树为空，右子树非空
删除节点的右子树为空，左子树非空
删除节点的左右子树都为空
对于第一种情况，我们可以找到删除节点的后继节点，将值替换，然后删除后继节点，这样保证了该树仍然是一棵二叉树，但是在删除后继节点时可能破坏了红黑树的特性，故需要进行调整。强调一下，红黑树中的叶子节点指的都是 NIL 节点。
这样来看，被删除的节点一定有一个右子树，可能为 NIL 也可能为非空子树，接下来就具体看看情况。
1. 如果删除节点 E 为红色，则 E 子节点 F 则必为黑色（红黑树特性），这种情况只有在 E 的两个节点都为叶子节点时才会发生。故删除之后红黑树平衡不用调整。可以自行画图验证：
删除节点 E 有两个非叶子节点，这不可能，因为 E 已经是后继节点。
E 有一个非叶子节点（右子节点），则这个非叶子节点 F 为黑色，通过 E 的两条黑色路径不同，不满足特性 5
2. 如果删除节点 E 为黑色，F 为红色，这种情况下，F 节点有两个叶子节点（需保证红黑树特性，黑色路径需保持一致）则 F 放置到 E 处时只需要变色就可以使得红黑树平衡
3. 如果删除节点 E 为黑色，F 也为黑色，这种情况只有在 E 的两个节点都为叶子节点时才会发生。参考上边情况 1 的验证。这里删除了一个黑色节点，红黑树平衡被破坏（黑色路径不同了），需要进行调整
针对 3 这里就又会有以下几种情况：
N 为删除的位置节点，现在被删除的节点的子节点取代 (这里子节点对应上边的 F，即删除后，N 的位置为叶子节点)，N 为黑色，P 为 N 的父母，S 为 P 的右子，SL 代表 S 的左子，SR 代表 S 的右子。
S 必不为叶子节点，反推下，如果为叶子节点，在未删除之前 P 的两边黑色路径就不一致了（未删除之前是 P ->E->F 这种，自行画图理解）。注意，下面列举的情况都是在删除 E 节点后，子节点取代 E 形成的情况，在此基础上进行红黑树的调整。按照顺序每种情况进行判断处理。注意每种情况处理之后会重新标记，以适应下次情况的对比调整，并且下列过程只以第一次调用时说明，递归调用下列顺序过程时将叶子节点当成一个已经平衡的局部红黑树即可。和之前的插入平衡调整类似，每次都是局部化调整。
第一种情况：如果 N 为根节点，不需要调整平衡了，原有树只有一个非叶子节点，两个叶子节点，删除了根节点，相当于删除了红黑树。继续第二种情况判断。
第二种情况：如果 N(这里是叶子节点 NIL) 是其父 P 的左子节点，S 为红色，P 必为黑色，参照下图，反转 P 和 S 的颜色，然后在 P 处向左旋转，将 S 转换为 N 的祖父母。这里 N 处的黑色路径少一个，还未平衡。N 是其父 P 的右子节点参照相似处理。SL 标记为新的 S 继续以 N,P,S 这块局部树进行处理。继续第三种情况处理。
第三种情况：如果 P，S 和 S 的孩子都是黑色，左图显示了出现的情况，在 N 替换掉之前的父节点后形成的状态，这里重新绘制 S 为红色，变为右图，在这个局部中满足平衡红黑树的特性 4 和 5，但是通过 P 节点的黑色路径相比原有结构减少了 1，还需要进行调整，需重新进行平衡。这里重新平衡即从第一种情况再次顺序执行，以 P 节点进行重新平衡，相当于以 P 为新的 N，黑色路径少 1，再次进行平衡调整。不满足当前情况，再继续执行第 4 种情况处理。
第四种情况：如果 S 和 S 的孩子是黑色，但 P 是红色的。在这种情况下，我们只需交换 S 和 P 的颜色。这不会影响通过 S 的路径上的黑色节点数量，但它确实会在通过 N 的路径上添加一个黑色节点数，从而弥补这些路径上已删除的黑色节点。将达到红黑树平衡。不满足当前情况，则继续第五种情况的处理。
第五种情况：如果 S 是黑色，S 的左孩子是红色，S 的右孩子是黑色，N 是其父母的左孩子。在这种情况下，我们在 S 处右转，这样 S 的左边孩子就成了 S 的父母和 N 的新兄弟。然后我们交换 S 及其新父母的颜色。所有路径仍然有相同数量的黑色结点，但是 P 的左子树因为删除一个节点导致黑色路径少 1，还未完全平衡。这里进行调整主要是为了满足第六种情况，继续第六种情况的处理。
第六种情况：如果 S 是黑色，S 的右子是红色，N 是其父 P 的左子。在这种情况下，我们向左旋转 P，这样 S 成为 P 和 S 的右子的父亲。然后，我们交换 P 和 S 的颜色，并使 S 的右子节点变黑。比较删除前与 N 替换调整后的属性，满足 4 和 5，与删除前是一致的。
总结
删除操作相对插入操作之后的平衡要复杂的多，不过按照情况一步步处理也是比较明了的，同样为了方便初学者理解，从上边的过程我们也可以发现，在一次局部平衡调整中，最多进行 3 次旋转操作，我这里再进行一个流程梳理，帮助各位更好的理解红黑树的删除操作。
到此关于红黑树的基础已经介绍完毕，下一章我将就 JDK 源码中的 TreeNode 进行讲解说明，看一看红黑树是如何在源码中实现的。
参考资料：
https://zh.wikipedia.org/wiki…
https://en.wikipedia.org/wiki…
https://my.oschina.net/hosee/…
https://www.cnblogs.com/tongy…
