《数据结构与算法》总结（二）红黑树

目录

• 序言
• 红黑树必须满足以下5条性质
• 添加
• 删除

一 序言

红黑树也是一种自平衡的二叉搜索树，以前也叫做平衡二叉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节点

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

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

以下资料在群文件可自行下载！

红黑树必须满足以下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 节点

红黑树

等价交换后的4阶B树

2.3 几个英文单词

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

三 添加

已知

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

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

3.1 添加的所有情况

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

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

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

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

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

判定条件:uncle 不是RED

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

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

判定条件:uncle 不是RED

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

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

判定条件:uncle 是RED

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

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

判定条件:uncle 是RED

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

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

判定条件:uncle 是RED

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

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

判定条件:uncle 是RED

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

四 删除

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

4.1 删除 – RED节点

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

4.2 删除-BLACK节点

有 3 种情况

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

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

3. BLACK 叶子节点

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

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

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

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

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

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

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

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

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

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

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

如果 parent 是 BLACK

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

---

项目连接地址 - 12_RedBlackTree

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

推荐阅读

iOS开发——最新 BAT面试题合集（持续更新中）

作者：路飞_Luck
链接：https://www.jianshu.com/p/fe2d66274496
来源：简书