0. 前言
由于需要处理的情形较多，直接背红黑树的算法会比较难。
所以本文尝试用推导思路的方式去聊一聊红黑树，希望能在需要的时候，即使忘记也能将算法完整推导出来。
推导出来的代码和情况划分可能会有一些差异，但只要大思路一致，代码看着不同，执行效率上差异通常不大，这也是没必要强记各种情况的原因之一。
其实个人认为红黑树包含不少有趣的思维模式如递推、奇偶性、对称等等，知道其思想以后有可能也有助于其他问题的理解。
1.为什么要用红黑树
红黑树是二叉搜索树的一种。而二叉搜索树用于解决快速搜索的同时保持较高的改动效率（相对于有序数组）。
二叉搜索树也有很多种，相对来说最直观容易理解的是平衡二叉树，其整棵树或任意子树的左右子树深度差异不超过一。但为了这样的平衡，需要一点点代价：每次增删可能会要求更多的调整次数（具体为旋转）。并且为了提升增删的效率，往往需要为每个节点多记录一个深度值（通常这是小事）。
而红黑树则以牺牲绝对的平衡为代价，只要求其中的黑色节点完全平衡即可，以此换取了一些调整的便捷性空间，以此达到更高效的增删效率。
2.红黑树的要求
红黑树有几条要求（或者叫性质）。第一次看见往往都会一脸懵逼。但我们一条一条分析，就能知道每一条的意义。
（注：个人不把空的叶子结点视作叶子结点，能省一条对叶子结点的要求）
要求1 每个节点要不红黑要不黑色
先为每个节点加上红或黑的颜色性质，平衡中和操作中的实际作用中略类似于奇偶性。
要求2 从任意结点向下至其不同的叶子结点会经过相同数量的黑色结点
用于保证红黑树内黑色结点的完美平衡。
要求3 两个红色结点不能为父子结点
用于保证在黑色结点完美平衡的同时，红色结点在任意树枝不会多于黑色结点的数量加一，限制了树的不平衡度深度至多差一倍。
要求4 根结点一定为黑色结点
这条对红黑树性质没有本质的影响。其实没有也可以。只是在具体推到算法时，有这一条的限制可以为我们省去不少判断的功夫，能有效减少理解和写算法的难度。
3. 递推结构
有了红黑树的几条限制后，可以尝试构建几棵树，找找感觉。
运气好的话的话，应该很快能发现红黑树的一个局部性特征：对任意已经达到条件的子树或叶子结点，我们可以用：
- 其根节点的颜色
- 其根到叶子结点经过的黑节点数量
两个特征进行描述足以，子树以外不再关心其他特征，由此我们可以隐藏内部结构。
由这个特征出发，我们可以考虑将问题归约为有限高度的子树的平衡，以减少需要考虑的情景数量。
当子树平衡后检查其根至叶子结点经过的黑节点数量和根节点颜色是否变化，如果有变化，则将子树考虑为一个结点向上用相同方式调整平衡，最终使整棵树平衡（和平衡二叉树的算法说起来也类似）。
为了进一步简化问题并利用上述发现的局部性特征，我们可以在推导具体算法时尽可能满足以下几个条件：
- 调整平衡的起点是一棵平衡的子树，而非一个中间节点（中间节点需要同时照顾父节点和孩子，无法合并与递推）。
- 子树的根到叶子结点经过的黑节点数量相比于修改前的最多只增减1。
- 每次修改前，红黑树一定已满足红黑树的必要条件（可以为推导过程提供大量外部信息，减少需要考虑的情况）。
之后我们会发现，在红黑树的增删中，这些条件都是比较容易达到的。
4. 增加节点
首先，我们需要找到节点在树中的插入位置，方式非常简单，二叉查询至合适的空叶子节点即可。
找到了位置，我们便可以考虑插入节点。那我们令这个新节点的颜色是红还是黑呢？
其实都可以。
但是，如果我们插入的是黑节点，这意味着其父节点（如果存在）为根的子树一定不再黑平衡（可以简单思考为什么），于是一定需要调整。
而如果我们选用红色，则仅当父节点为红时（不满足要求2.3），我们才需要进行调整。
因此为简化问题，也为了效率，我们选择将目标节点染成红色并插入，并以其为目标节点进行后续调整。
此时观察这个新节点，如果我们把它当成是一棵子树，显然是黑平衡的（两个边子树都是空）。
所以主要考察外部结构。
如果父节点为空，意味着它是根节点，根据要求2.4，我们把它染黑即可结束（之后我们会发现这样做的好处），不需要额外的平衡。
如果父节点为黑，考虑以父节点为根的子树，明显黑平衡没有变化，之前平衡现在也应平衡，由此也可以直接结束无需平衡。
（以下其他情况需要开始考虑平衡）
为了调平衡递推函数的可控性，我们首先仅以新增节点为平衡目标的特征进行考虑，其特征为
- 红色
- 其根到叶子结点经过的黑节点数量没有变化
之后递推时可以尽可能保持这两个特征，减少情况数量。
现在来考虑目标节点可能的各种情况：
如果父节点为红，局部调整最简单的方式是把父节点染黑，再把目标节点染红，再以父节点为平衡目标去调整的平衡性（特征为1.黑色，2.其根到叶子结点经过的黑节点数量增加1）。
可以发现这样的特征信息和之前我门以新增节点为平衡目标时的特征信息并不相同，意味着平衡函数内需要考虑更多的情况，虽然也可以做到，但为了减少复杂性，个人倾向于先调整出具有相同的特征信息的子树后，再递推调整。
但是，如何找到这样一个特征相同的情景呢？仅调整目标节点和其父节点似乎并不可行。
这时候要求2.4便发挥了出了一些价值：如果父节点是红色，意味着父节点以上一定有一个黑色的祖父节点。
我们可以把这三代合在一起进行考察，且确定目标为
- 目标1:调整达到子树黑平衡，且不改变子树根节点颜色。（如果达到则完成调整）
- 目标2:调整达到子树黑平衡，但子树根节点由黑变红。（于是基于相同特征继续调整子树根节点）
接下来便需要考虑可能的解决方案与对应的限制情形。并考虑是否覆盖了所有情形。
4.1 方案1
父代与祖父交换颜色。
将父节点修改为黑色，将祖父节点修改为红色，以此在不改变目标节点所在分支的黑深度情况下，解决了两个红节点为父子的问题。
但这样做明显有限制：如果存在叔叔节点，由于祖父节点由黑变红，则叔叔分支的黑深度将变小，而不在平衡。为解决这样的问题，如果叔叔节点是红色，我们可以轻易的将其改为黑色，达到调平深度的目的。
整理一下：如果叔叔节点不存在或颜色为红，则交换父辈节点和祖父节点颜色。此时达到了目标2，于是以祖父为目标继续向上递推调整即可。
4.2 方案2
旋转调平。
这里再介绍二叉查找树中比较常用的一种调整方式：旋转
旋转是一种调平衡的手段，具有一些很好的性质：
- 旋转后，树的中序不变（查找树的要求）
- 旋转不对旋转节点和其父节点以外各个节点产生要求（D、E、C无论是空还是一棵大树都不重要非常灵活）
从根节点两个子分支的角度来看，旋转其实在转移了一层节点深度的同时，还转移了旋转节点的旋转方向孩子。
所以实际运用中，通常哪边“重”，就往另一边转就行。但旋转节点的旋转方向孩子会成为其兄弟的孩子，可能会造成新的不平衡等问题，需要提前关注。
所以回到我们当前的问题本身，由于目标节点的存在，我们可以尝试向其叔叔侧旋转其父节点。
如果目标节点和其父节点是同侧的子节点，则旋转并不会转移调平横的目标节点（可以模拟一下非同侧的情况下旋转的结果）。
旋转之后左右高度会有1的差异，这时交换一下颜色便可以达到高度修正的目标。
此情况可以左右镜像，所以不对镜像进行赘述。
总结一下，当调平衡的目标节点与其父节点同属一侧时，可以向另一侧转动父节点，并交换父与祖父的颜色。这样可以直接达到平衡无需进一步调整。
4.3 方案3
调整至方案2。
如果目标节点和父节点不是同一侧的孩子，直接旋转会产生新的问题，但我们可以先向目标节点的孩子侧的另外一边旋转目标节点，使情况变为方案2的条件，再重新将其父节点作为目标去调整（和目标节点拥有相同的黑节点深度，所以特征不变）。
还可以综合以上考虑一下是否有遗漏的情形（应该能发现没有了）。
5. 删除节点
删除节点的情景会稍多一些，但如果能稍熟练递推的模式，并运用好旋转则也容易穷举出各种情况和相应的解决方案。
5.1 找替代节点
由于删除节点时会同时影响其子节点（失去了根需要调整结构，并调平），并会影响父节点（很可能不平衡，需要调平），情形较多，但此时我们可以通过“替代节点”的方式减少影响。
具体方式为，找目标节点在其子树中的前继或者后继作为替代节点（如果没有孩子，那更好，直接不用找替代）。
找到替代节点后，可以将替代节点的值赋予删除的节点，接着替代节点便可以视为新的删除节点（可以试试看）。
理论上我们可以一直重复找替代节点和替代节点的替代节点，直到叶子节点，没有孩子情况最简洁。这确实是一种处理方式，但并不必要。由于其后继或者前继必定没有左孩子或者右孩子，删除之后直接将存在的孩子（如果存在）提上来占删除节点的位置即可，如下图。
在删除后，再去针对此位置的新节点考虑平衡调整，但注意，此时此位置有可能不存在节点，所以在编程中为了方便，可以在为空时补一个黑色节点（黑色和空一样，不惹事，好处理），并在调平后删掉它。
5.2 考虑平衡影响
删了一个节点，会有什么影响呢？如果删除的是一个红色节点，容易发现没有任何影响。
但如果是黑色的，则明显有影响了，并且影响是所在分支的黑深度少了1。
这使得我们从删除任务转移至了调平任务。和插入节点时挺像的，只是这次是少了1。
接着我们可以思考一下调整的方式，由于是一整棵树的平衡，很可能需要调整很多层，这样穷举就过于复杂了。所以
我们可以继续借鉴插入节点时采用的递推思想，把问题化简（虽然也有代价，采用递推后不能再随意调整前面的节点）
下面再进行调平的递推方式进行思考。先从能想到的最简单的方案入手。
5.3 自己调平
由于需要增加1的黑深度，如果需调平的目标节点颜色是红，那最好办，直接变黑便解决了问题。并且由于黑色不对相连其他节点产生威胁，可以放心变色。
这样做已经包含了自己是根节点的情况，条件和处理都是几乎一样的
5.4 协助调平
在开始穷举前可以先整理一下自己穷举的思路，以做到不漏（可以重，毕竟是编程可以有先后依次判断）。讲道理，穷举方式非常多，每一种情形在推导正确的情况下，理应都能找到解决方案，并且方案大同小异殊途同归。
这里列举一下我的分类方式
（注：H0表示调整后需要达到的黑深度）
情况1:我首先想到利用父节点和兄弟节点调平衡，感觉靠变色就能处理一部分。但为了让变色更自由，需要侄子节点非黑即空，由此得到了这么一个分类。
情况2:非情况1时，意味着侄子节点至少有一个是红色节点，于是先列出右侄子这种。
情况3:剩余的情况。
5.4.1 情况1
（注：放一张图更好掌握感觉，可以放大查看）
分别说明一下这三种子情形：
- 都黑：非常简单，将兄弟节点变红即可调平
- 父红兄黑：用我们在插入时也利用过的手段，父与兄交换颜色来平衡
- 兄红父黑：这种情况下会稍微麻烦一点，可以尝试后发现变色已经无法解决平衡问题。需要旋转和变色，并且发现依旧无法完全平衡。但我们可以将除了目标以外的节点全部调平（通过变色），此时由于兄和父已经变化为侄子与父，且侄子一定有限，所以可以继续以其为目标节点进行平衡调整（原地递推）。
5.4.2 情况2
首先让兄弟节点向自己旋转。
接着根据父节点的颜色是红还是黑分别讨论。
- 如果父红：为了避免考虑另外一个侄子的颜色（图中的F），于是把上两层颜色进行交换，并且发现根节点和初试父节点一致为红，所以没有额外影响。结束调整。
- 如果父黑：修改颜色后可以调平，但计算根节点的黑深度时，会发现少了1，于是需要针对根节点进行进一步调平。
5.4.3 情况3
借鉴平衡二叉树的旋转方式，经过如图两次旋转，即可达到视觉平衡的情况。但由于目标节点的父节点不确定，于是还需要进一步讨论。
5.5 总结
推导完成后，可以回顾一下整体思路。其实也可总结为一个准则：
- 能自己处理的自己处理（自己变色）
- 不能自己处理的，找父节点帮忙
- 父节点也不能直接处理的，找叔叔节点一起帮忙调整
- 父辈整体都搞不定了，那再诉诸爷爷辈
这样感觉就不那么抽象了。
6. C语言实现
由于依旧左右对称，就不在赘述镜像的情况，代码中也可以继续利用一个左右标志节省接近一半的代码。
7. 参考资料
https://rbtree.phpisfuture.com/
https://www.phpisfuture.com/article/1