红黑树
- 红黑树也是一种自平衡的二叉搜索树；
- 红黑树以前也叫做平衡二叉B树；
如下图所示：
Snip20210511_15.png
红黑树的5条性质：
- 节点是RED或者BLACK；
- 根节点是BLACK；
- 叶子节点(空节点)都是BLACK；
- RED节点的子节点都是BLACK；
4.1 RED节点的parent都是BLACK；
4.2 从根节点到叶子节点的所有路径上不能有2个连续的RED节点； - 从任意节点到叶子节点的所有路径都包含相同数目的BLACK节点；
B树
- B树是一种平衡的多路搜索树，多用于文件系统，数据库的实现；
- 一个节点可以存储超过2个元素，可以拥有超过2个字节点；
- 拥有二叉搜索树的性质；
- 平衡，每个节点的所有子树高度一致；
- 比较矮；
m阶B树的性质(m>=2)
- m阶B树是指一个节点最多拥有m个子节点；
Snip20210511_16.png
Snip20210511_17.png
- 假设一个节点存储的元素个数为x
- 根节点： 1 <= x <= m - 1
- 非根节点： ceil(m/2) - 1 <= x <= m -1
- 如果有子节点，子节点的个数 y = x + 1；
- 根节点的子节点：2 <= y <= m
- 非根节点的子节点： ceil(m/2) <= y <= m
以m=3，即3阶B树为例：
根节点的元素个数 1<= x <= 2，即1或者2，不会有3个元素；
非根节点的元素个数 1<= x <= 2，即1或者2，不会有3个元素；
根节点的子节点个数 2 <= y <= 3
非根节点的子节点个数 2 <= y <= 3
B树与二叉搜索树，在逻辑上等价的；
多代节点合并，可以获得一个超级节点；
2代合并的超级节点，最多拥有4个子节点，至少是4阶B树；
3代合并的超级节点，最多拥有8个子节点，至少是8阶B树；
n代合并的超级节点，最多拥有 2^n 个子节点，至少是 2^n 阶B树；
m阶B树，最多需要log2 m带合并；
搜索指定节点
- 从根节点开始；
- 先在节点内部从小到大开始搜索元素；
- 如果命中，搜索结束；
- 如果未命中，再去对应的子节点中搜索元素，重复步骤1；
添加
- 新添加的元素必定是添加到叶子节点；
添加导致上溢
- 上溢节点的元素个数必然等于m；
- 假设上溢节点最中间的元素的位置为k；
- 将k位置的元素向上与父节点合并；
- 将[0，k-1]和[k+1，m-1]位置的元素分裂成2个子节点，这两个子节点的元素个数，必然都不会低于最低限制ceil(m/2)-1；
- 一次分裂完成后，有可能导致父节点上溢，依然按照上述的方法解决；
- 最极端的情况，有可能一直分裂到根节点；
如下所示：4阶B树，添加元素98
Snip20210511_18.png
Snip20210511_19.png
- 添加元素98，由于是4阶B树，节点元素个数最大为3，则导致上溢；需进行一次分裂结果如下：
Snip20210511_20.png
删除叶子节点
- 需要删除的元素在叶子节点中，那么直接删除即可；
如下所示：删除元素55
Snip20210511_18.png
- 删除元素55之后：
Snip20210511_21.png
删除非叶子节点
- 先找到其前驱或者后继元素，覆盖所需删除元素的值；
- 再把前驱或后继元素删除；
如下所示：删除元素60
Snip20210511_22.png
Snip20210511_23.png
- 真正被删除的元素是前继元素55，
- 真正被删除的元素都是在叶子节点中。
删除导致下溢
原理如下所示：
Snip20210517_2.png
看一个例子：5阶B树删除元素22
Snip20210511_24.png
- 删除元素22，由上面的结论我们知道非根节点的元素数量 ceil(5/2)-1<= x <= 4，即至少有两个元素，现在删除22，导致当前节点的元素为1，即导致下溢；
- 下溢节点的元素数量必然等于ceil(m/2) - 2
- 如果下溢节点临近的兄弟节点至少有ceil(m/2)个元素，可以向其借一个元素；
- 将父节点的元素b插入到下溢节点的最小位置；
- 用兄弟节点的元素a(最大元素)替代父节点的元素b；
- 上述操作的本质就是：旋转，操作结果如下所示：
Snip20210517_1.png
- 如果下溢节点的临近兄弟节点，只有ceil(m/2)-1个元素；
- 将父节点的元素b挪下来与左右子节点进行合并；
- 合并之后的节点元素个数为ceil(m/2)+ceil(m/2)-2，不会超过m-1；原理如下图所示：
Snip20210517_3.png
- 此操作可能会导致父节点下溢，依然按照上述的方法解决，下溢现象可能会一直向上传播；
红黑树的等价变换
- 红黑树与4阶B树具有等价性；
- BLACK节点与它的RED子节点融合在一起，形成一个B树节点；
- 红黑树的BLACK节点个数与4阶B树的节点总个数相等；
Snip20210519_17.png
红黑树的添加
- 新元素的必定是添加到叶子节点中；
- 4阶B树所有节点的元素个数x都满足 【1，3】；
- 建议新添加的节点默认为红色RED；
- 如果添加的是根节点，染成黑色BLACK即可；
以上面的红黑树为例子，进行阐述添加的所有情况：
- 当添加的节点的父节点parent为黑色BLACK，如下图所示：
Snip20210519_18.png
- 具体有4种情况，见图中被添加的粉色节点；
- 能同时满足红黑树的五条性质，因此不用做任何额外的处理；
- 当添加的节点的父节点parent为红色RED，如下图所示：
Snip20210519_19.png
- 具体有8种情况，见图中被添加的粉色节点；
- 不满足红黑树的第4条性质：RED节点的子节点都是BLACK；
