红黑树
https://www.jianshu.com/p/4cd37000f4e3
https://www.bilibili.com/video/BV1Ce4y1Q76H
引入
有了二叉搜索树，为什么需要平衡二叉树？
- 二叉搜索树容易变成链表，查找的时间复杂度就会从O(log2N)变为O(N)。
- 引入平衡二叉树，防止树退化。
有了平衡二叉树，为什么还需要红黑树
- 平衡二叉树插入删除操作影响效率
- 红黑树减少插入/删除操作，整体性能优于AVL，也能保证时间复杂度为O(log2N)。
- 红黑树插入时的不平衡，不超过两次旋转可以解决
- 删除时的不平衡，不超过三次旋转可以解决。
介绍
红黑树是一种接近平衡的二叉树。
特性/要求
- 节点是红色或者黑色；
- 根是黑色；
- 叶子结点（外部节点，空节点）都是黑色，并且为空节点（概念上有空节点，实际无）；
- 红色节点的子节点和父节点都是黑色（即，不存在两个连续的红色节点）；
- 从任意节点到叶子结点的所有路径都包含相同数目的黑色节点
红黑树与二三四树
红黑树与二三四树等价；
红黑树的黑色节点数 = 234树的节点数
在234树中的红黑树，黑色节点必为父节点，红色节点必为子节点；
（黑色中间，红色两边）
每一棵红黑树都有对应的唯一一棵二三四树；
但一个二三四树可能有多个红黑树与之对应。
高度
路径长度不会超过2log(n+1)，即
$$
红黑树高度 \leq 2log(n+1)
$$
效率
红黑树的查找、插入和删除操作，时间复杂度都是O(logN)。
红黑树与AVL树比较
- AVL树时间复杂度优于红黑树；
- 红黑树整体性能略优于AVL树。
hole…
插入操作情况
插入结点的颜色
若插入的是根节点，则为黑色；
其他节点都为红色。
- 如果插入红色节点，出现两个连续的红色节点，只需要旋转和变色进行调整。
为什么？
如果插入的颜色为黑色，则接下来的调整会非常麻烦；
如果插入的颜色为红色，则只有一种冲突的情况，只需要旋转和变色进行调整就可。
黑父
无需做任何操作；
红父
又分为两种情况：红叔、黑叔
红叔
若新节点的父节点和叔节点都是红色节点，将父节点和叔节点改为黑色，把祖节点改为红色，然后递归检查祖节点即可。
黑叔
黑叔分为4种情况处理；
- 父节点是是祖节点的左儿子，新节点是父节点的左儿子
- 父节点是是祖节点的左儿子，新节点是父节点的右儿子
- 父节点是是祖节点的右儿子，新节点是父节点的左儿子
- 父节点是是祖节点的右儿子，新节点是父节点的右儿子
父左新左
右旋，然后变色，叶子节点为黑色，其他向上交错；然后向上递归变色；
父右新右
左旋，然后变色，叶子节点为黑色，其他向上交错；然后向上递归变色；
父左新右
在父节点左旋，然后在祖节点右旋，最后变色，以叶子节点为黑色为基准，向上递归变色；
父右新左
在父节点右旋，然后在祖节点左旋，最后变色，以叶节点为黑色为基准，向上递归变色；
删除操作
分为两种情况：红色节点删除，黑色节点删除；
思想
B树中的删除操作，对于非叶子节点的删除，都要转换为其前驱/后继节点的删除。
- 这里要删除节点8，现将前驱节点与要删除的节点值进行交换（这里是和6交换）；
- 然后删除前驱节点即可。
红色节点删除
可以直接删除，不做任何调整；
黑色节点删除
麻烦。必须进行调整才能满足红黑树的性质；即：从任意节点到叶子节点的所有路径都包含相同的黑色节点。
黑色节点的三种形式
- 有2个红色子节点的黑色节点；（即：234树的4节点）
- 不做考虑，对这个节点的删除会转换为对其子节点的删除。
- 有1个红色子节点的黑色节点；（即：234树的3节点）
- 黑色叶子节点。（即：234树的2节点）
有1个红色子节点的黑色节点
用唯一的红色子节点来替代被删除的节点，然后将替代的节点染为黑色。
==步骤：替代，删除，将替代节点染黑==
删除没有子节点的黑色叶子节点
删除黑色叶子节点，会造成下溢的情况；
这里再分为三种情况：
- 删除节点为根节点；
- 此时整个红黑树只有这一个节点，可以直接删除。
- 删除节点的兄弟节点为黑色；
- 删除节点的兄弟节点为红色，这里要转变兄弟节点为黑色进行处理
删除节点的兄弟节点为黑色几种情况
分为以下几种情况：
- 兄弟节点带有红色子节点（借用兄弟子节点修复）
- 兄弟节点带有左红色子节点
- 兄弟节点带有右红色子节点
- 兄弟节点带有两个红色子节点
- 兄弟节点没有红色子节点（父节点向下合并）
兄弟节点带有左红色子节点
兄弟节点带有右红色子节点
兄弟节点有两个红色子节点
兄弟节点没有红色子节点
这里分两种情况：
- 父节点为红色节点
- 父节点为黑色节点
父节点为红色节点
作为B树，没有任何变化；
作为红黑树，需要进行一次变色；
父节点为黑色节点
兄弟节点染为红色，父节点染为黑色；
如果父节点本就是黑色，就把父节点当做已被删除的节点处理，向上递归处理；
例子，==这里没能成功理解，后续回来==
兄弟节点为红色
这里要转变为黑色处理。
处理：父节点右旋，兄弟节点染为黑色，父节点染为红色，然后以兄弟节点为黑色进行修复；
