平衡二叉搜索树
AVL树
AVL树的特点
每个节点的平衡因子只可能是 1、0、-1（绝对值 ≤ 1，如果超过 1，称之为“失衡”）
每个节点的左右子树高度差不超过 1
搜索、添加、删除的时间复杂度是 O(logn)
平均时间复杂度
- 搜索：O(logn)
- 添加：O(logn)，仅需 O(1) 次的旋转操作
- 删除：O(logn)，最多需要 O(logn) 次的旋转操作
添加导致的失衡
可能会导致所有祖先节点都失衡 只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡【仅需 O(1) 次调整】
父节点、非祖先节点，都不可能失衡
失衡情况：
- LL：left-left，指的是，失衡结点左子树的左子树上添加结点导致的失衡；恢复平衡需要右旋转
- RR: right- right。恢复平衡需要左旋转
- LR: 左旋 --> 右旋
- RL: 右旋 --> 左旋
删除导致的失衡
可能会导致父节点或祖先节点失衡（只有1个节点会失衡）
恢复平衡后，可能会导致更高层的祖先节点失衡【最多需要 O(logn) 次调整】
B树
B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现
B树特点
- 1 个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点
- 拥有二叉搜索树的一些性质
- 平衡，每个节点的所有子树高度一致
- 比较矮
m阶B树的性质（m≥2）
一个节点存储的元素个数 x
- 根节点：1 ≤ x ≤ m − 1
- 非根节点：┌ m/2 ┐ − 1 ≤ x ≤ m − 1
如果有子节点，子节点个数 y = x + 1
- 根节点：2 ≤ y ≤ m
- 非根节点：┌ m/2 ┐ ≤ y ≤ m
m=2时，B树就是AVL树
B树 VS 二叉搜索树
B树 和 二叉搜索树，在逻辑上是等价的
多代节点合并，可以获得一个超级节点
- 2代合并的超级节点，最多拥有 4 个子节点（至少是 4阶B树）
- 3代合并的超级节点，最多拥有 8 个子节点（至少是 8阶B树）
- n代合并的超级节点，最多拥有 2 n 个子节点（ 至少是 2 n 阶B树）
m阶B树，最多需要 lo g 2 m 代合并
B树添加节点
新添加的元素必定是添加到叶子节点
上溢（overflow）：叶子节点的元素个数将超过限制 的现象
添加 – 上溢的解决
上溢节点的元素个数必然等于 m
- 假设上溢节点最中间元素的位置为 k，将 k 位置的元素向上与父节点合并
- 将 [0, k-1] 和 [k + 1, m - 1] 位置的元素分裂成 2 个子节点 这 2 个子节点的元素个数，必然都不会低于最低限制（┌ m/2 ┐ − 1）
- 一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决 最极端的情况，有可能一直分裂到根节点
B树删除节点
假如需要删除的元素在叶子节点中，那么直接删除即可
假如需要删除的元素在非叶子节点中
- 先找到前驱或后继元素，覆盖所需删除元素的值
- 再把前驱或后继元素删除
非叶子节点的前驱或后继元素，必定在叶子节点中 所以这里的删除前驱或后继元素 ，就是最开始提到的情况：删除的元素在叶子节点中 真正的删除元素都是发生在叶子节点中
下溢（underflow）：叶子节点被删掉一个元素后，元素个数可能会低于最低限制（ ≥ ┌ m/2 ┐ − 1 ）
删除 – 下溢的解决
下溢节点的元素数量必然等于 ┌ m/2 ┐ − 2
（1）如果下溢节点临近的兄弟节点，有至少 ┌ m/2 ┐ 个元素，可以向其借一个元素
将父节点的元素 b 插入到下溢节点的 0 位置（最小位置）
用兄弟节点的元素 a（最大的元素）替代父节点的元素 b 这种操作其实就是：旋转
（2）如果下溢节点临近的兄弟节点，只有 ┌ m/2 ┐ − 1 个元素
将父节点的元素 b 挪下来跟左右子节点进行合并
合并后的节点元素个数等于┌ m/2 ┐ + ┌ m/2 ┐ − 2，不超过 m − 1
这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播
4阶B树
4阶B树的性质 所有节点能存储的元素个数 x ：1 ≤ x ≤ 3
所有非叶子节点的子节点个数 y ：2 ≤ y ≤ 4
红黑树
红黑树也是一种自平衡的二叉搜索树
以前也叫做平衡二叉B树（Symmetric Binary B-tree）
parent：父节点
sibling：兄弟节点
uncle：叔父节点（ parent 的兄弟节点）
grand：祖父节点（ parent 的父节点）
平均时间复杂度
搜索：O(logn)
添加：O(logn)，O(1) 次的旋转操作
删除：O(logn)，O(1) 次的旋转操作
红黑树必须满足以下 5 条性质
-
节点是 RED 或者 BLACK
-
根节点是 BLACK
-
叶子节点（外部节点，空节点）都是 BLACK
-
RED 节点的子节点都是 BLACK ， RED 节点的 parent 都是 BLACK ， 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点
-
从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点
红黑树与四阶B树
红黑树 和 4阶B树（2-3-4树）具有等价性
BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点
红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等
红黑树添加
B树中，新元素必定是添加到叶子节点中 ，4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3 ，建议新添加的节点默认为 RED，这样能够让红黑树的性质尽快满足（性质 1、2、3、5 都满足，性质 4 不一定）
1、如果添加的是根节点，染成 BLACK 即可
2、有 4 种情况满足红黑树的性质 4 ：parent 为 BLACK
3、有 8 种情况不满足红黑树的性质 4 ：parent 为 RED（ Double Red ） 。这种情况又分为叔父结点是否为red的情况
添加 - LL\RR
uncle 不是 RED
- parent 染成 BLACK，grand 染成 RED
- grand 进行单旋操作 。 LL：右旋转 RR：左旋转
uncle 是 RED
- parent、uncle 染成 BLACK
- grand 向上合并（染成 RED，当做是新添加的节点进行处理）
- grand 向上合并时，可能继续发生上溢 若上溢持续到根节点，只需将根节点染成 BLACK
添加 – LR\RL
uncle 不是 RED
- 自己染成 BLACK，grand 染成 RED
- 进行双旋操作 。 LR：parent 左旋转， grand 右旋转 ； RL：parent 右旋转， grand 左旋转
uncle 是 RED
- parent、uncle 染成 BLACK
- grand 向上合并 。染成 RED，当做是新添加的节点进行处理
红黑树删除
B树中，最后真正被删除的元素都在叶子节点中
删除 – RED节点
直接删除，不用作任何调整
删除 – BLACK节点
拥有 2 个 RED 子节点的 BLACK 节点 不可能被直接删除，因为会找它的子节点替代删除 因此不用考虑这种情况
2、拥有 1 个 RED 子节点的 BLACK 节点
用以替代的子节点是 RED。将替代的子节点染成 BLACK 即可保持红黑树性质
3、BLACK 叶子节点，区分兄弟结点
sibling为BLACK：BLACK 叶子节点被删除后，会导致B树节点下溢（比如删除88） 。
- 如果 sibling 至少有 1 个 RED 子节点 进行旋转操作 旋转之后的中心节点继承 parent 的颜色 旋转之后的左右节点染为 BLACK
- sibling 没有 1 个 RED 子节点 将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质。如果 parent 是 BLACK 会导致 parent 也下溢 这时只需要把 parent 当做被删除的节点处理即可
sibling 是 RED：sibling 染成 BLACK，parent 染成 RED，进行旋转 于是又回到 sibling 是 BLACK 的情况
AVL树 vs 红黑树
AVL树
平衡标准比较严格：每个左右子树的高度差不超过1
最大高度是 1.44 ∗ lo g 2 n + 2 − 1.328（100W个节点，AVL树最大树高28）
搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整
红黑树
平衡标准比较宽松：没有一条路径会大于其他路径的2倍
最大高度是 2 ∗ lo g 2 n + 1 （ 100W个节点，红黑树最大树高40）
搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整
选择
搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树
红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树
