《恋上数据结构与算法一》笔记（十一）红黑树

一 序言

红黑树也是一种自平衡的二叉搜索树，以前也叫做平衡二叉B树(Symmetric Binary B-tree)

二 红黑树必须满足以下5条性质

1.节点是RED或者是BLACK

2. 根节点是BLACK
3. 叶子节点(外部节点，空节点)都是BLACK
4. RED节点的子节点都是BLACK
   4.1 RED节点的parent都是BLACK
   4.2 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

image.png

2.1 请问下面这棵是红黑树吗？

image.png

红黑树必须满足以下5条性质

1. 节点是RED或者BLACK
2. 根节点是BLACK
3. 叶子节点（外部节点，空节点）都是BLACK
4. RED节点的子节点都是BLACK
   4.1 RED节点的子节点都是BLACK
   4.2 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

2.2 红黑树的等价交换

• 红黑树和4阶B树（2-3-4树）具有等价性
• BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点
• 红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等
• 网上有些教程:用 2-3树 与 红黑树 进行类比，这是极其不严谨的，2-3树 并不能完美匹配 红黑树 的所有情况
• 注意:因为PPT界面空间有限，后面展示的红黑树都会省略NULL 节点

红黑树

image.png

等价交换后的4阶B树

image.png

2.3 几个英文单词

• parent:父节点
• sibling:兄弟节点
• uncle:叔父节点( parent 的兄弟节点)
• grand:祖父节点( parent 的父节点)

三 添加

已知

• B树中，新元素必定是添加到叶子节点中
• 4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3
• 如果添加的是根节点，染成BLACK 即可

备注：建议新添加的节点默认为 RED，这样能够让红黑树的性质尽快满足(性质 1、2、3、5 都满足，性质 4 不一定)

image.png

3.1 添加的所有情况

• 有 4 种情况满足红黑树的性质 4 :parent 为 BLACK

1.同样也满足 4阶B树 的性质
2.因此不用做任何额外处理

image.png

• 有 8 种情况不满足红黑树的性质 4 :parent 为 RED( Double Red )

1. 其中前 4 种属于B树节点上溢的情况

image.png

3.2 修复 - 修复性质4 - LL\RR

判定条件:uncle 不是RED

1. parent 染成 BLACK，grand 染成 RED
2. grand 进行单旋操作
   2.1 LL:右旋转
   2.2 RR:左旋转

image.png

3.3 添加 - 修复性质4 - LR\RL

判定条件:uncle 不是RED

1. 自己染成BLACK，grand染成RED
2. 进行双旋操作
   2.1 LR:parent 左旋转， grand 右旋转
   2.2 RL:parent 右旋转， grand 左旋转

image.png

3.4 添加-修复性质4-上溢-LL

判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，当做是新添加的节点进行处理
   2.2 grand 向上合并时，可能继续发生上溢
   2.3 若上溢持续到根节点，只需将根节点染成 BLACK

上溢-LL.png

3.5 添加-修复性质4-上溢-RR

判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，当做是新添加的节点进行处理

上溢-RR.png

3.6 添加-修复性质4-上溢-LR

判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，当做是新添加的节点进行处理

上溢-LR.png

3.7 添加-修复性质4-上溢-RL

判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，当做是新添加的节点进行处理

上溢-RL.png

四 删除

B树中，最后真正被删除的元素都在叶子节点中

删除.png

4.1 删除 – RED节点

• 直接删除，不用作任何调整

删除-RED节点.png

4.2 删除-BLACK节点

有 3 种情况

1. 拥有 2 个 RED 子节点的 BLACK 节点
   1.1 不可能被直接删除，因为会找它的子节点替代删除
   1.2 因此不用考虑这种情况

2. 拥有 1 个 RED 子节点的 BLACK 节点

3. BLACK 叶子节点

image.png

4.3 删除 – 拥有1个RED子节点的BLACK节点

判定条件:用以替代的子节点是 RED

将替代的子节点染成BLACK 即可保持红黑树性质

image.png image.png

4.4 删除 – BLACK叶子节点 – sibling为BLACK

1. BLACK 叶子节点被删除后，会导致B树节点下溢(比如删除88)

2. 如果 sibling 至少有 1 个 RED 子节点
   2.1 进行旋转操作
   2.2 旋转之后的中心节点继承 parent 的颜色
   2.3 旋转之后的左右节点染为 BLACK

• 下图是3种需要删除的情况

image.png

• 下图对应着删除节点88后，旋转之后的样子

image.png

4.5 删除 – BLACK叶子节点 – sibling为BLACK

判定条件:sibling 没有 1 个 RED 子节点

• 将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质

如果 parent 是 BLACK

1. 会导致parent 也下溢
2. 这时只需要把 parent 当做被删除的节点处理即可

image.png

---

项目连接地址 - 12_RedBlackTree

---

本文参考 MJ老师的 恋上数据结构与算法

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励。

---