红黑树（Red Black Tree)
红黑树也是一种自平衡的二叉搜索树，红黑树必须满足一下5条性质：
1.节点是RED或者BLCAK
2.根节点是BLACK
3.叶子节点（外部节点，空节点）都是BLACK
4.RED节点的子节点都是BLACK，RED节点的父节都是BLACK，从根节点到叶子节点的所有路径上不能有2个连续的RED节点
5.从任意一个节点到叶子节点的所有路径都包含相同数目的BLACK节点
请问下面这棵是红黑树么？
答案是不是的，因为不满足上面所说的性质5:从任意节点到叶子节点的所有路径都包含相同的BLACK节点，路径55->53-null,这条路径如果不包含null这个叶子节点的话，那么就只有两个BLACK节点，而其他的是有3个的BLACK节点
红黑树的等价变换
红黑树和4阶B树（2-3-4树）具有等价性，BLACK节点与它的RED子节点融合在一起，形成一个B树节点，红黑树的BLACK节点个数与4阶B树的节点总个数相等
几个相关的专业名字
parent：父节点
sibling：兄弟节点
uncle：叔父节点（parent的兄弟节点）
grand：祖父节点（parent的父节点）
红黑树的添加
从B树中我们可以知道，新元素必定是添加到叶子节点中，4阶B树的多有节点的元素个数都符合，建议新添加的节点默认为RED，这样能够让红黑树的性质星空满足（性质1，2，3，5都满足，就只有性质4不一定满足），另外如果添加的是根节点，直接染成BLACK即可
添加的所有情况（12种）
为什么是12种情况呢？因为添加元素都是添加到叶子节点，你可以想一下，叶子节点和父节点的分布情况有哪几种，分别有红黑红，黑红，红黑，黑如下图：
可以从图中看到最后两层的分布形式，基于这种情况下，我们可以有12种添加元素的方式，如下图所展示
前面已经说过了，如果添加的节点是红色就满足了4条性质，接下来我们就是要满足性质4，从上述12种情形中，我们可以看到4种情形是满足性质4的(parent为BLACK)，情形分别是情形5，情形10，情形11，情形12；那么如果是这4种情况我们就是不用左任何额外处理的，如果是剩下的那8种(parent为RED)，我们就需要额外处理了
先处理情形7和情形8，这两种情况分别符合RR和LL的情况，处理的步骤是判断uncle 如果不是RED，就执行下面步骤：1.parent染成BLACK，grand染成RED；2.grand进行单旋转操作，如果是LL，就右旋转，如果是RR，就左旋转；
图形展示如下：（情形7是RR，情形8是LL）
再处理情形6和情形9，分别符合RL和LR情况，处理方式：判定条件是uncle 不是RED，处理步骤1.自己染成BLACK，grand染成RED，2.进行双旋操作，LR：parent左旋转，grand右旋转，RL：parent右旋转，grand左旋转
上图：
目前为止，现在只剩下4种情况，是情形1，情形2，情形3，情形4
情形1:修复性质4-上溢(LL)
判定条件：uncle是RED，parent，uncle染成BLACK，grand向上合并，然后grand染成RED，当作是新添加的节点进行处理，如果grand向上合并时候，继续发生了上溢，那么继续按照上溢的方式处理，若上溢持续到根节点，只需将根节点染成BLACK；
此时38是parent，55是grand，80是uncle，根据前面说的，parent,uncle染成black，grand向上合并，染成RED
剩余3种情形上溢RR，上溢LR，上溢RL，都是和上溢LL一样的处理方式，这里不在展示了，接下来描述一下删除
红黑树的删除
删除也是分为好几种情况的，下面一一说明：
删除-RED节点
直接删除，不用做任何调整，因为删除RED不会红黑树的性质，前面已经说过，删除的节点都是在叶子节点；
删除-BLACK节点
有3种情形，拥有2个RED子节点的BLACK节点，这种可以忽略，因为不可能直接被删除，因为前面说过删除的都是子节点，既然在有子节点，肯定是在子节点中删除，然后子节点是红色的话，那就不用处理，所以这里需要处理的只有拥有一个RED子节点的BLACK节点，和BLACK叶子节点，如下图所示：
上面说过删除拥有两个RED子节点的BLACK不需要理会，也就是说上面的情形1，不用我们去管理，这里我们看一下情形2的情况先，因为情形2可以拆分出多种情况
情形2的第一种情况：sibling为BLAKCK并且有RED子节点
这种方式的处理可以理解成为：判定条件：用以替代的子节点是RED，将替代的子节点染成BLACK，即可以保持红黑树的性质，具体步骤可以立即成为，BLAKCK叶子节点被删除后，会导致B树节点下溢，比如上面删除的88，如果sibling至少有一个RED子节点，首先根据相关旋转条件进行相应旋转操作，旋转之后的中心节点继承parent的颜色，旋转之后的左右节点染为BLACK
情形2的第二种情况：sibling为BLAKCK没有RED子节点
这种情况的判定条件是：sibling没有一个RED子节点，处理步骤是sibling，染成RED，parent染成BLACK就可以了，如果parent是BLACK，下溢之后导致parent也下溢，这个时候只需要把parent当作被删除的节点处理就可以了（上图下面一种情况）
情形2的第三种情况：sibling为RED
如果sibling是RED，sibling染成BLACK，parent染成RED，进行旋转，于是情况就又回到sibling是BLACK的情况了，下面就按照前面的情况进行处理就可以了
红黑树暂时先到这里吧，后续有学到新的我会再补充上来的
