1. 红黑树简介
红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于 1978 年发明，在当时被称为平衡二叉 B 树( symmetric binary B-trees )。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。
2. 红黑树的特性
节点：
- parent：父节点
- sibling：兄弟节点
- uncle：叔父节点（ parent 的兄弟节点）
- grand：祖父节点（ parent 的父亲节点）
特性：
- 节点是红色或黑色
- 根节点是黑色
- 叶子节点都是黑色（ NULL 空节点才是叶子节点）
- 红色节点的子节点都是黑色
- 红色节点的父节点都是黑色
- 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
- 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
分类：
红黑树与四阶 B 树具有等价特性，我们将红黑树转化为四阶 B 树后进行分类。
- 红黑红
- 黑红
- 红黑
- 黑
3. 红黑树的操作
3.1 旋转操作
- 左旋
- 右旋
左旋是将某个节点 A 旋转为其右孩子节点 B 的左孩子节点 C，如果节点 C 存在，则节点 C 作为节点 A 的左孩子；
右旋是将某个节点 A 旋转为其左孩子节点 B 的右孩子节点 C，如果节点 C 存在，则节点 C 作为节点 A 的有孩子。
3.2 插入操作
根据红黑树的分类，插入（从叶子节点插入）分为 12 种情况，这12种均满足 1，2，3，5 特性。其中有 4 种满足特性 4，这 4 种情况插入操作不需要做任何处理，对其余 8 种需要做特殊处理。
3.2.1 RR 和 LL 情况
- RR情况：父节点为祖父节点的右节点，插入节点为父节点的右节点
- LL情况：父节点为祖父节点的左节点，插入节点为父节点的左节点
判定条件： uncle 不是红色节点。
这里的两种情况，他们的插入节点都是没有叔父节点的，所以叔父节点也不可能是红色。
处理方法：
- parent 染成黑色，grand 染成红色。
- grand 进行单旋操作。
- LL：右旋转。
- RR：左旋转。
3.2.2 LR 和 RL 情况
- RL情况：父节点为祖父节点的右节点，插入节点为父节点的左节点
- LR情况：父节点为祖父节点的左节点，插入节点为父节点的右节点
判定条件： uncle 不是红色节点。
这两种情况的插入节点也是没有叔父节点的。
处理方法：
- 插入节点染成黑色，grand 染成红色。
- 进行双旋操作。
- LR：parent 左旋转， grand 右旋转。
- RL：parent 右旋转， grand 左旋转。
3.2.3 上溢的 LL 情况
- 上溢LL情况：父节点为祖父节点的左节点，插入节点为父节点的左节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。
判定条件： uncle 是红色节点。
满足这个条件的就都是上溢的情况，上溢的修复只需要染色，不需要旋转。
处理方法：
- parent、uncle 染成黑色。
- grand 向上合并。
- 将向上合并的grand染成红色，相对上一层，就当做是新添加的节点，再次来一遍插入情况的判断，进行处理。
3.2.4 上溢的 RR 情况
- 上溢RR情况：父节点为祖父节点的右节点，插入节点为父节点的右节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。
判定条件： uncle 是红色节点。
满足这个条件的就都是上溢的情况，上溢的修复只需要染色，不需要旋转。
处理方法：
- parent、uncle 染成黑色。
- grand 向上合并。
- 染成红色（其实染成红色就已经是完成了向上合并，因为祖父节点和祖父节点的父节点的连接指向并没有变），当做是新添加的节点进行处理。
3.2.5 上溢的 LR 情况
- 上溢LR情况：父节点为祖父节点的左节点，插入节点为父节点的右节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。
判定条件： uncle 是红色节点。
满足这个条件的就都是上溢的情况，上溢的修复只需要染色，不需要旋转。
处理方法：
- parent、uncle 染成黑色。
- grand 向上合并。
- 染成红色，当做是新添加的节点进行处理。
3.2.6 上溢的 RL 情况
- 上溢RL情况：父节点为祖父节点的右节点，插入节点为父节点的左节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。
判定条件： uncle 是红色节点。
满足这个条件的就都是上溢的情况，上溢的修复只需要染色，不需要旋转。
处理方法：
- parent、uncle 染成黑色。
- grand 向上合并。
- 染成黑色，当做是新添加的节点进行处理。
3.2.7 插入情况总结
插入一共有12种情况：
插入节点的父节点是黑色的情况有4种。
这种情况仍然会维持红黑树的性质，则不需要进行额外处理。插入节点的父节点是红色的情况有8种。
这种情况不满足红黑树的性质4，需要进行额外的修复处理，这8种情况中：- 叔父节点不是红色的情况有4种。
这些情况都是非上溢，需要通过重新染色和旋转来进行修复 - 叔父节点是红色的情况有4种。
这些情况都是上溢的，只需要通过祖父节点上溢合并和染色即可完成修复
- 叔父节点不是红色的情况有4种。
3.3 删除操作
B 树中，最后真正被删除的元素都在叶子节点中。所以在红黑树中，被删除的节点一定也在最后一层。
最后一层有红色节点和黑色节点，我们就以删除节点的颜色来区分删除操作的所有情况。
如果删除的节点是红色直接删除，不用作任何调整。因为删除最后一层的红色节点，并没有影响红黑树的任何性质。
3.3.1 删除黑色节点
有3种情况：
- 拥有 2 个红色子节点的黑色节点。
- 不可能被直接删除，因为会找它的子节点替代删除，因此不用考虑这种情况。
- 拥有 1 个红色子节点的黑色节点。
- 黑色叶子节点。
3.3.2 删除拥有1个红色子节点的黑色节点
判定条件： 用以替代的子节点是红色节点
处理方法：
- 用删除节点的唯一子节点对其进行替代。
- 将替代节点染成黑色。
3.3.3 删除黑色叶子节点——删除节点为根节点
一棵红黑树只有一个黑色根节点（也就是唯一的一个叶子节点，整个红黑树只有这一个黑色节点），可直接删除该节点，无需做其他操作。
3.3.4 删除黑色叶子节点——删除节点的兄弟节点为黑色
这种情况会产生下溢（特性5）。
3.3.4.1 兄弟节点至少有1个红色子节点
判定条件： 兄弟节点至少有 1 个红色子节点
处理方法：
- 进行旋转操作。
- 旋转之后的中心节点继承父节点（删除节点的父节点）的颜色。
- 旋转之后的左右节点染为黑色。
3.3.4.2 兄弟节点没有红色子节点
判定条件： 兄弟节点没有红色子节点
处理方法：
- 父节点向下与兄弟节点进行合并。
- 将兄弟染成红色、父节点染成黑色即可修复红黑树性质。
- 如果父节点是黑色，直接将父节点当成被删除的节点处理，来修复父节点的下溢情况。
3.3.5 删除黑色叶子节点——删除节点的兄弟节点为红色
判定条件： 兄弟节点是红色
处理方法：
- 兄弟节点染成 BLACK，父节点染成染成 RED，对父节点进行右旋。
- 于是又回到兄弟节点是黑色的情况（侄子节点变为兄弟节点），继续使用兄弟节点为黑色的方法进行修复。
4. AVL树 vs 红黑树
4.1 AVL树
- 平衡标准比较严格：每个左右子树的高度差不超过 1。
- 最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W 个节点，AVL 树最大树高 28）。
- 搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整。
4.2 红黑树
- 平衡标准比较宽松：没有一条路径会大于其他路径的2倍。
- 最大高度是 2 ∗ log2(n + 1)（100W 个节点，红黑树最大树高 40）。
- 搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整。
4.3 如何选择
- 搜索的次数远远大于插入和删除，选择 AVL 树；搜索、插入、删除次数几乎差不多，选择红黑树。
- 相对于 AVL 树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于 AVL 树。
- 红黑树的平均统计性能优于 AVL 树，实际应用中更多选择使用红黑树。
原文链接： https://blog.csdn.net/cy973071263/article/details/122543826
