一.红黑树特性
红黑树是一种自平衡的二叉搜索树，也曾叫做平衡二叉B树。
红黑树性质：
1.节点是RED或者BLACK
2.根节点是BLACK
3.叶子节点（外部节点，空节点）都是BLACK
4.RED节点的子节点都是BLACK
5.从任意节点到叶子节点的所有路径都包含相同数目的BLACK节点
红黑树的等价交换
红黑树可以与4阶B树(2-3-4树)进行等价交换
图1为红黑树，图二为4阶B树，由图可以看出，将红黑树中BLACK节点与RED子节点融合在一起，就可以形成一个B数节点，红黑树的BLACK节点数与4阶B树的节点总个数相等。
图1:
图2：
红黑树与4阶B树的全部类型转换
红黑树与4阶B树一共有四中不同情况，分别为红黑红，红黑，黑红，黑（空节点表示null leaf）。
二. 红黑树添加
简要分析：
当新增一个节点时候，红黑树依然需要满足红黑树的五条性质。
:one:性质一：节点为RED或者BLACK。节点永远只有这两种颜色，依旧满足
:two:性质二：根节点是BLACK。当正好插入一个RED节点时，该性质不满足，当正好插入一个BLACK节点时，该性质满足
:three:性质三：叶子节点（外部节点，空节点）都是BLACK。依旧满足
:four:性质四：RED节点的子节点都是BLACK。当父节点为RED时候，插入的节点不能是RED,当父节点是BLACK时候，插入节点不区分RED还是BLACK
:five:性质五：从任意节点到叶子节点的所有路径都包含相同数目的BLACK节点，如果插入节点为黑色，必定无法满足性质五，如果插入节点为红色时，依然满足性质五
若假设新插入节点默认为黑色，将必不满足性质五。若重新对该树进行梳理，以致满足红黑树的五大性质，这方面的性能损耗将会很大，每当一个插入一个黑色节点时，就需要重新梳理一遍。
若假设新插入节点默认为红色，将不满足性质二与性质四，相对于性质五而已，新插入的红色节点代替了原来NULL LEAF的位置，且新插入的红节点自带两个黑色的NULL LEAF子节点，所以当插入一个红色节点时，路径上黑色节点的数目将不会发生变化，估满足了性质五的要求。
新增节点情况分析与处理：
接下来以下图为红黑树模板逐一分析添加新节点的全部可能性，以及相应的处理方法
现在讲全部的空节点画出来，每一个空节点都将是红黑树新增节点的一种方式，一共12种添加方式，另外加上一种，新增节点为根节点的情况，一共13种添加方式。下面将依次分析：
1 新节点为根节点
- 默认新添加的节点为红色，当添加的节点为根节点的时候，直接讲红色转变为黑色即可，即满足性质二，同事也满足性质四。
2 父节点为黑色节点
-
当插入节点为叶子节点，且父节点为黑色节点时，将同时直接满足性质二与性质四。
image
父节点为黑色节点时候，一共有4种情况，直接插入新红色节点就满足了红黑树的全部性质。
3. 父节点为红色节点
剩下的八种情况将无法满足性质四，需要进行额外处理，让该树满足红黑树特性
3.1 当叔父节点为黑色节点，将出现LL\RR\RL\LR四种情况
3.1.1 出现LL\RR情况
46 -> 50 -> 新节点 right -> right方向，归类于RR情况
76 -> 72 -> 新节点 left -> left方向，归类于LL情况
将两种情况的红黑树转换为4阶B树
由B树结构可以看出，若想实现B树平衡，形成新的B树节点，由于B树节点是有一个黑色节点，与其相应的红色子节点形成的，所以当出现LL/RR情况时需进行变色，使46-50-52/76-72-60改变成新的B树节点，如下图所示。
LL情况下，72变黑色，76变红色
RR情况下，50变黑色，46变红色
（步骤1：父节点变黑色，祖父节点变红色）
现在会发现在LL情况下38->46两个节点（在RR情况下80->76两个节点）出现了连续双红色节点，不满足性质四。根据4阶B树的性质，一个树节点是有一个黑色节点以及相应的红色子节点（或者无子节点）组成。顾只需要将已经变完色的树节点进行旋转，让黑色节点变为父节点，红色节点变为子节点即满足了B树的要求。
LL情况向右旋转，RR情况向左旋转
（步骤2：LL情况向右旋转，RR情况向左旋转）
旋转完成后，黑色节点变为父节点，红色新增节点以及红色祖父节点变为子节点，如图
开始旋转：
旋转完成：
由旋转完成后的图可以看出，该树结构完全满足了4阶B树的全部性质，也就意味这该树满足了红黑树的全部性质，最后得到的红黑树结构如下：
总结：当叔父节点为黑色节点，且出现LL\RR情况时候，先将父节点变为黑色，祖父节点变为红色，若是LL则右旋，若是RR则左旋
3.1.2 出现LR\RL情况
46 -> 50 -> 新节点 right -> left方向，归类于RL情况
76 -> 72 -> 新节点 left -> right方向，归类于LR情况
将两种情况的红黑树转换为4阶B树
由B树结构可以看出，若想实现B树平衡，形成新的B树节点，由于B树节点是有一个黑色节点，与其相应的红色子节点形成的，所以当出现LR/RL情况时需进行变色，使46-48-50/76-74-72改变成新的B树节点，如下图所示。
LR情况下，74变黑色，76变红色
RL情况下，48变黑色，46变红色
（步骤1：自己变黑色，祖父节点变红色）
现在会发现在RL情况下46->50两个节点（在LR情况下72->76两个节点）同时出现红色，不满4阶B树的性质，开始通过双旋转来调整。
RL情况下，父节点向右旋转，祖父节点向左旋转，新节点向上移动
LR情况下，父节点向左旋转，祖父节点向右旋转，新节点向上移动
（步骤2：双旋，父节点与祖父节向外两边反向旋转，自己上移）
旋#转完成后，新节点变为父节点，父节点以及祖父节点均变为子节点，如图
开始旋转：
旋转完成：
由旋转完成后的图可以看出，该树结构完全满足了4阶B树的全部性质，也就意味这该树满足了红黑树的全部性质，最后得到的红黑树结构如下：
总结：当叔父节点为黑色节点，且出现RL\LR情况时候，先将自己变为黑色，祖父节点变为红色，进行双旋变为子节点，自己上移为父节点
3.2 当叔父节点为红色节点，将出现上溢LL\RR\RL\LR四种情况
3.2.1 上溢 LL情况
对LL进行处理：
根据4阶B树的特效，树是有1至3个节点组成，当前LL情况，会出现4个节点，顾出现树分裂（节点上溢）的情况，以保证满足4阶B数的特性，由图可以发现，最好的上溢的节点为中间的两个节点，一个是红色节点17，一个是黑色节点25，由于黑色节点25本省就是节点38的子节点，所以黑色节点25上溢将更加容易。
（步骤1：父节点与叔父节点变为黑色节点）
当祖父节点25上溢时，先保证17->25树的特性，将父节点17转变为黑色节点，将叔父节点33变为黑色节点
（步骤2：将黑色节点25看做是在38->55->80树新添加的节点，先变色为红色节点）
从前面可知，在红黑树（4阶B树）中插入一个新节点比较好的方式为，插入一个默认为红色的节点，现将黑色节点25看做新插入的一个节点，顾先变色为红
（步骤3：不难看出，当前新插入的红色25节点的叔父节点80为红色，且满足LL的情况，顾重复步骤1）
前面归纳红色新节点的添加一共有12种方式，当发生上溢时，可以看做上溢的节点新添加到上一个树中，判断此处新增节点属于什么类型的新增方式，直接按照相应的方式进行新增，依次轮询类推
（步骤4：重复步骤2）
将该上溢节点看做新增节点，顾将待上溢的节点变为红色节点
（步骤5：判断该节点为根节点，直接变为黑色即可，平衡完成）
最后得到的红黑树结构：
3.2.2 上溢 RR情况
（步骤1：父节点与叔父节点变为黑色节点）
（步骤2：上溢节点看做新增节点，先变色为红色节点）
（步骤3：继续形成上溢LL情况，重复进行开始插入步骤，直到平衡）
最后得到的红黑树结构：
总结：当叔父节点为红色节点，且出现LL\RR情况时候，先将父节点与叔父节点变为黑色，将祖父节点变为上溢，最后将祖父节点变为红色看做一个新增节点处理即可
3.2.3 上溢 LR 情况
（步骤1：父节点与叔父节点变为黑色节点）
（步骤2：祖父节点上溢变为红色）
（步骤3：上溢节点看做新增节点，形成LL情况，重复上溢LL情况的新增操作）
当祖父节点25上溢时候，将25节点看做树38->66->80的新增节点，顾先变色为红，然后会发现继续形成了上溢LL情况，顾将25的父节点38与叔父节点88变为红色，将黑色节点55上溢且变为黑色
（步骤4：上溢红色节点55将变为该树的根节点，顾直接变色为黑即可）
最后得到的4阶B树结构：
最后得到的红黑树结构：
3.2.4 上溢 RL 情况
（步骤1：父节点与叔父节点变为黑色节点）
（步骤2：祖父节点上溢变为红色）
（步骤3：上溢节点看做新增节点，形成LL情况，重复上溢LL情况的新增操作）
（步骤4：上溢红色节点55将变为该树的根节点，顾直接变色为黑即可）
最后得到的4阶B树结构：
最后得到的红黑树结构：
总结：当叔父节点为红色节点，且出现RR\LLRL\LR情况时候，先将父节点与叔父节点变为黑色，将祖父节点上溢（根据4阶B树的特效，一棵树的节点数在1-3个，新增节点加入后变为4个节点，则需要有一个节点向上一层转移），且作为上一层树结构的新增节点看待，先变色为红，查看后续该节点作为新增节点时，属于红黑树新增12中情况的的哪一种，继续进行处理，直到满足红黑树的五条性质即可
到此为止，红黑树节点添加的全部情况已经梳理完成，统计如下:
| 新增类型 | 处理方式 | 类型数量 |
|---|---|---|
| 新增节点为根节点 | 直接添加，仅变色 | 1 |
| 父节点为黑色节点 | 直接添加，仅变色 | 4 |
| 父节点为红色，叔父节点为黑色 | 变色，旋转 | 4 |
| 父节点为红色，叔父节点为红色 | 变色，上溢 | 4 |
二. 红黑树删除
真后继节点定义：
1.树中在节点“右边”的第一个节点
2.真后继节点还同时满足是该节点的子孙
(以下步骤将null节点排除，不作为子节点看待，以下D节点看做待删除节点)
1.不存在子节点
1.1 如果为红色，直接删除即可，不会影响黑色节点的数量；
1.2 如果为黑色，则需要进行删除平衡的操作了；
删除平衡操作，当删除节点为黑色且没有子节点时，该节点的兄弟节点必为黑色，且该兄弟节点的子节点要么为红色要么为空节点，且该兄弟节点没有孙子节点。
处理方式：该节点直接删除，父节点与兄弟节点旋转变换位置，兄弟节点的子节点位移为父节点的子节点
若待删除节点为左子节点，原父节点变为兄弟节点的左子节点，原兄弟节点的左子节点变为原父节点的右子节点，最后统一进行变色处理（这里的变色，直接依照旋转前原位置颜色变化即可保证红黑树性质）
总结：当删除节点为黑且没有子节点时候:
（步骤1：去除待删节点）
（步骤2：先进行旋转，原兄弟节点上移为父节点，原父节点下移为兄弟节点的一个子节点，原兄弟的一个节点变为原父的一个节点）
2.1若待删除节点为右子节点，原父节点变为兄弟节点的右子，原兄弟节点的右子变为父节点的左子。
2.2若待删除节点为左子节点，原父节点变为兄弟节点的左子，原兄弟节点的左子变为父节点的右子
（步骤3：依照旋转前的位置颜色，修改旋转后位置的颜色，一一对应变色即可
2.存在一个子节点
2.1只有右子节点
该节点为红色，右子不能为红，所以右子为黑色，但该节点没有左子，这里与红黑树的黑色叶子节点数目一致的性质想违背，必不可能存在该情况。
该节点为黑色，右子可能为红可能为黑，但该节点没有左子，为了不违背红黑树的黑色叶子节点数目一致的性质，顾右子必定为红色，且该右子节点没有子节点（ps:没有子节点的原因在于红黑树性质4判断子节点只能为黑色，而当为黑色时无法满足性质5，所以不存在子节点）
真后继节点为该节点的右子节点。
2.2只有左子节点
当没有右子存在左子时候，只存在一个子节点的情况，与上面情况类似，分析参考上面情况，所以确定该节点的为黑色，右子为红色，右子将不存在子节点。
真后继节点为该节点的左子节点。
总结：当只有一个子节点时候，该节点必为黑色，且子节点必为红色，找到真后继节点，替换掉待删除节点，原待删除节点的子节点变色为黑（当删除一个黑色节点时，该树将不能满足红黑树性质五，顾需变色），即可。
（步骤1：后继节点与待删除节点进行值替换，去除待删除节点）
3.存在两个子节点
当该节点的左右子均存在时，真后继节点为右子树中序遍历的第一个节点。
将等待删除的节点替换成真后继节点
判断真的后继节点是否存在右子节点
进行递归操作，直到不存在右子节点
情形一：
情形二：
情形三：
情况四：
总结：当存在两个子节点时候，需要先找到该节点的真后继节点，进行值替换，变换为删除该真后继节点，然后判断删除该真后继节点属于删除类型中的哪一种，进行相应的操作，直到树平衡为止。
到此为止，红黑树节点删除的全部情况已经梳理完成，统计如下:
| 新增类型 | 处理方式 |
|---|---|
| 没有子节点 | 判断颜色，若为红直接删除，若为黑进行平衡处理 |
| 存在一个子节点 | 寻找真后继节点，进行值替换 |
| 存在两个子节点 | 寻找真后继节点，进行值替换，继续删除真后继节点，判断删除情况类型，继续执行删除节点操作 |
（ps：删除操作中，无论是寻找真后继节点，或是寻找真前继节点均可正常执行红黑树删除节点操作）
关于红黑树的学习梳理基本完成，主要包括红黑树的性质，红黑树与4阶B树的等价交换，红黑树新增节点情况分析，红黑删除节点情况分析。
学习路径：
1.https://www.bilibili.com/video/BV1HJ411z7ZU?p=107
2.https://juejin.im/post/6844904036747968525
3.https://www.cnblogs.com/tongy0/p/5460623.html
推荐相关的在线工具：
1.数据结构可视化(Data Structure Visualizations)：http://www.rmboot.com/Algorithms.html
2.数据结构可视化(可以查看各种遍历方式)：http://520it.com/binarytrees/
3.数据结构和算法动态可视化 (Chinese)：https://visualgo.net/
