算法--我的红黑树学习过程

学习资料：
清晰理解红黑树的演变---红黑的含义
 一篇文章搞懂红黑树的原理及实现
 红黑树详细分析，看了都说好
 红黑树删除操作
 码图并茂红黑树
 红黑树从头至尾插入和删除结点的全程演示图

阅读前提

在研究集合类源码的时候，发现Map，Set里面不少用到红黑树，为了能够更顺利的学习源码。我决定把红黑树知识恶补一下。如果不了解树、二叉树、平衡二叉树定义的同学先了解一下这些前提知识。 由于能力时间有限，我就不复述学习资料里大神写的内容了。关于一些基础知识和概念请大家先读一遍学习资料里的文章。我接下来的讲解都将基于这三篇的基础之上，进行更细致的讲解，把我在学习过程中遇到的一些比较难理解的点尝试用文字或图例变得更容易理解。

我强烈建议大家的阅读顺序为：先读红黑树详细分析，看了都说好。这篇文章讲的比较全，但是删除部分对我来说，文字上有点难理解。接着阅读红黑树删除操作。这篇文章把删除讲解的比较细致。最后再阅读红黑树从头至尾插入和删除结点的全程演示图或码图并茂红黑树。前者格式不好，后者漏了一步，可以主要以后者为主。两篇文章就是来学以致用的，文章以图来全程演示此红黑树的所有插入，和删除情况。但是缺点是没有任何讲解，所以正适合检验一下前两篇的学习和理解，建议大家可以先自己推理一步，然后再看与文章中的下一步的结果图是否一致。

（2020.06更新）最后一定要看清晰理解红黑树的演变---红黑的含义、一篇文章搞懂红黑树的原理及实现这两篇，这两篇是讲红黑树的演变，意义。比如为什么要红色和黑色，为什么要两个父节点不能同时为红色。

OK，现在就当大家已经按上面步骤阅读完了。如果此时还有疑问或不懂的地方，可以继续往下阅读，也可以在评论中询问我，我会尽力回答。由于个人只是对红黑树的删除部分觉得有难点，所以下面主要讲的是红黑树删除部分。

红黑树删除

前提知识

1. 红黑树的定义

任何一个节点非红即黑；
树的根为黑色；
叶子节点为黑色(注意：红黑树的所有叶子节点都指的是Nil节点)；
任何两个父子节点不可能同时为红色；
任何节点到其所有分枝叶子的简单路径上的黑节点个数相同；

2. 节点命名约定

D表示要被删除的节点。即：取 Delete 的首字母；
P 表示父节点。即：取 Parent 的首字母；
S表示兄弟姐妹节点。即：取 Sibling的首字母；
U表示叔伯节点。即：取Uncle的首字母；
G表示祖父节点。即：取 Grandfather的首字母；
L表示左树。即：取Left的首字母；
R表示右树。即：取Right的首字母；
Nil表示叶子节点。即所谓的空节点；注意：红黑树中的叶子节点与其他树中所述说的叶子节点不是同一概念。而且红黑树中的叶子节点(即：Nil节点)永远是被定义为黑色的。

下文的节点命名表示将会使用以上这些命名约定或它们的组合表示。因此，请先牢记这些命名约定。举例：
DR表示要被删除的节点的右子树，即：右子节点； SL表示兄弟节点的左子树，即：左子节点；

3. 删除操作宏观分析

在红黑树中，删除一个节点往大的说，只有以下四种情况。
情况一：删除的节点的左、右子树都非空；
情况二：删除的节点的左子树为空树，右子树非空；
情况三：删除的节点的右子树为空树，左子树非空；
情况四：删除的节点的左、右子树都为空树；

其中情况一，可以按与其他二叉搜索树的删除方式一样处理，最终可以转换到后面的三种情况。具体为：找到(Old)D节点的直接后继节点(暂且称为X节点)，然后将X的值转移到D节点，最后将X节点作为真正要被删除掉的节点(即：(Real)D节点)。 这样删除操作后，可以保证该树仍然为一棵二叉搜索树。但由于红黑树的定义(即：红黑树的性质)约定。这样删除(Real)D节点后，可能会破坏红黑树的性质。所以需要额外做一些调整处理，这便是下面将要详细讨论的内容。 说明：下文中所提到的D，除非有特别说明，否则都将指的是(Real)D。

删除情况分类

通过阅读红黑树详细分析，看了都说好、红黑树删除操作两篇文章，可以发现虽然说法不同，但是绝大多数应对的情形是一样，我整理为下列表格：

《红黑树删除操作》	《红黑树详细分析》	备注
被删除D为红		只需要直接将D节点删除，并将DR作为P的左子节点即可。
D为黑，DR不为Nil、DR必为红		由于红黑树定义5，（P-D-Nil）和（P-D-DR-Nil）的黑点数一样，所以DR必为红
D黑、DR为Nil、S红	情况二	仍需继续平衡
D黑、S黑、SL红	情况五（后续为情况六）	这里两篇文章有些不同，《删除操作》中单独处理，《详细分析》将与情况六搭配起来处理平衡，但是结果是一样的。个人喜欢使用情况五六搭配起来使用方式
D黑、S黑、SR红	情况六
D黑、S黑、P红、SL黑、SR黑	情况四
D黑、S黑、P黑、SL黑、SR黑	情况三	可能仍需继续平衡，此时经过P的路径的黑节点个数将会比不经过它的路径少一个。因此，我们将P作为待平衡的节点(即：此时的P相当于DR的角色)往上继续上溯，直到P为根节点为止。

D黑、DR为Nil、S红（情况二）详解

在红黑树删除操作中D黑、DR为Nil、S红这个分支个人认为讲的有点太绕了。图画的容易让人混淆。我重新画个图方便大家理解。其实作者省略了SL和SR的叶子节点，准确的红黑树图应该如下：

当删除结点D后通过旋转变色，得到的结果如下：

可以发现，此时乍看一下好像是平衡了，但是把叶子结点加上后，就会发现（S-P-DR）这条线比其他线少一个黑结点。此时需要继续平衡，这个时候我们的DR结点的兄弟结点是SL，所以匹配D黑、S黑、P红、SL黑、SR黑的情况。

所以最终平衡结果如下：

在删除结点演示图中的删除结点16，就是这个情况。

红黑树删除结点演示图部分详解

这里我们根据红黑树从头至尾插入和删除结点的全程演示图的删除演示图，详解其中的几步。

删除结点12

先寻找到结点12的后继结点13，然后将13的值复制到结点12处，将结点13删除，此时可以发现匹配D黑、S黑、SR红的情况（因为是镜像的原因，所以是SR红不是SL红），根据匹配的结果旋转变色，最后得到结果红黑树：

删除结点13

此时红黑树为，我们将删除结点13

把注意力集中在13-16-17这棵红黑树上，发现匹配D黑、S黑、P黑、SL黑、SR黑情形，根据匹配结果着色为下图（右）：

此时以结点16为根的红黑树平衡了，但是我们把目光放在整棵红黑树上，会发现所有经过结点16的黑节点数会比不经过结点16的少1，所以根据D黑、S黑、P黑、SL黑、SR黑的备注，我们将原P（结点16）作为待平衡的节点(DR)往上继续上溯，直到P为根节点为止。如下图所示（结点16连线断开仅是为了防止匹配时被红结点17干扰）：

最后

最后，如果你也在学习红黑树，希望这篇文章能够帮助到你。另外，由于红黑树本身比较复杂，加之本人水平有限，难免会出一些错误。如果有错或者有疑问，还望大家指出来，我们共同讨论。