一、初识红黑树
1、红黑树的英文是什么？红黑树和二叉搜索树有什么关系？
- 红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树
- 以前也叫做平衡二叉 B 树（Symmetric Binary B-Tree）
image.png
2、红黑树必须满足以下 5 条性质？
- ①节点都是 Red 或者 Black
- ②根节点是 Black
- ③叶子节点（外部节点、空节点）都是 Black
- ④Red 节点的子节点都是 Black（推导一：Red 节点的 parent 都是 Black；推导二：从根节点到叶子节点的所有路径不能有 2 个连续的 Red 节点）
- ⑤从任一节点到叶子节点的所有路径都包含相同数目的 Black 节点
image.png
3、红黑树与哪阶 B 树等价？
- 红黑树 和 4阶(2-3-4)B树具有等价性
image.png
image.png
二、红黑图添加
1、红黑树添加的所有情况（总共有 12 种情况）？
- 往红黑树添加新节点，都是往叶子节点上添加，并成为新的叶子节点。
image.png
2、将添加节点的 12 种情况归类之一：parent 为 Black（有四种情况）
- 直接也满足 4阶B树 的性质
- 因此不用做任何处理
3、将添加节点的 12 种情况归类之二：parent 为 Red && uncle 不是 Red && LL/RR（有两种情况）
- parent 染成 Black，grand 染成 Red
- grand 进行单旋操作
image.png
4、将添加节点的 12 种情况归类之三：parent 为 Red && uncle 不是 Red && LR/RL (有两种情况)
- 把自己染成 Black，grand 染成 Red
- 进行下面之一的双旋操作
- LR：parent 左旋转，grand 右旋转
- RL：parent 右旋转，grand 左旋转
image.png
5、将添加节点的 12 种情况归类之四：parent 为 Red && uncle 是 Red (有四种情况)
- parent、uncle 染成 Black
- grand 向上合并（染成 Red，当做是新添加的节点进行处理）
- grand 向上合并时，可能继续发生上溢（若上溢持续到根节点，只需将根节点染成 Black）
image.png
image.png
image.png
二、红黑树的补充
1、为什么红黑树的 5 条性质就能让红黑树也称为平衡二叉搜索树？
- 首先不要拿 AVL 树的平衡去衡量红黑树的平衡
- 红黑树的平衡其实就是 B 树的平衡
- 相比 AVL 树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的 2 倍
2、AVL树 和 红黑树之间如何选择？（最重要，一定要切记）
image.png
image.png
三、红黑树删除节点
1、红黑树删除的奥义是什么？
- 在 B 树中，最后真正被删除的元素都在叶子节点中
- 红黑树等价于四阶(2-3-4)B树，并且红黑树是二叉搜索树的子集
2、红黑树删除太复杂，后面再看吧。
image.png
image.png
image.png
image.png
image.png
