《数据结构与算法》总结(二)红黑树
目录
- 序言
- 红黑树必须满足以下5条性质
- 添加
- 删除
一 序言
红黑树也是一种自平衡的二叉搜索树,以前也叫做平衡二叉B树(Symmetric Binary B-tree)
二 红黑树必须满足以下5条性质
1.节点是RED
或者是BLACK
- 根节点是
BLACK
-
叶子节点
(外部节点,空节点)都是BLACK
-
RED
节点的子节点都是BLACK
4.1RED
节点的parent
都是BLACK
4.2 从根节点到叶子节点
的所有路径上不能有2个连续的RED
节点 - 从任一节点到
叶子节点
的所有路径都包含相同数目的BLACK
节点
2.1 请问下面这棵是红黑树吗?
作为一个开发者,有一个学习的氛围跟一个交流圈子特别重要,这是一个我的iOS交流群:413038000,不管你是大牛还是小白都欢迎入驻 ,分享BAT,阿里面试题、面试经验,讨论技术, 大家一起交流学习成长!
以下资料在群文件可自行下载!
红黑树必须满足以下5条性质
- 节点是
RED
或者BLACK
- 根节点是
BLACK
-
叶子节点(外部节点,空节点)
都是BLACK
-
RED
节点的子节点都是BLACK
4.1RED
节点的子节点都是BLACK
4.2 从根节点到叶子节点
的所有路径上不能有2个连续的RED
节点 - 从任一节点到
叶子节点
的所有路径都包含相同数目的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 )
- 其中前 4 种属于B树节点上溢的情况
3.2 修复 - 修复性质4 - LL\RR
判定条件:uncle
不是RED
-
parent
染成BLACK
,grand
染成RED
-
grand
进行单旋操作
2.1 LL:右旋转
2.2 RR:左旋转
3.3 添加 - 修复性质4 - LR\RL
判定条件:uncle
不是RED
- 自己染成
BLACK
,grand
染成RED
- 进行双旋操作
2.1 LR:parent
左旋转,grand
右旋转
2.2 RL:parent
右旋转,grand
左旋转
3.4 添加-修复性质4-上溢-LL
判定条件:uncle
是RED
-
parent
、uncle
染成BLACK
-
grand
向上合并
2.1 染成RED
,当做是新添加的节点进行处理
2.2grand
向上合并时,可能继续发生上溢
2.3 若上溢持续到根节点,只需将根节点染成BLACK
3.5 添加-修复性质4-上溢-RR
判定条件:uncle
是RED
-
parent
、uncle
染成BLACK
-
grand
向上合并
2.1 染成RED
,当做是新添加的节点进行处理
3.6 添加-修复性质4-上溢-LR
判定条件:uncle
是RED
-
parent
、uncle
染成BLACK
-
grand
向上合并
2.1 染成RED
,当做是新添加的节点进行处理
3.7 添加-修复性质4-上溢-RL
判定条件:uncle
是RED
-
parent
、uncle
染成BLACK
-
grand
向上合并
2.1 染成RED
,当做是新添加的节点进行处理
四 删除
B树中,最后真正被删除的元素都在叶子节点中
4.1 删除 – RED节点
- 直接删除,不用作任何调整
4.2 删除-BLACK节点
有 3 种情况
-
拥有
2
个RED
子节点的BLACK
节点
1.1 不可能被直接删除,因为会找它的子节点替代删除
1.2 因此不用考虑这种情况 -
拥有 1 个
RED
子节点的BLACK
节点 -
BLACK 叶子节点
4.3 删除 – 拥有1个RED子节点的BLACK节点
判定条件:用以替代的子节点是 RED
将替代的子节点染成BLACK
即可保持红黑树性质
4.4 删除 – BLACK叶子节点 – sibling为BLACK
-
BLACK 叶子节点被删除后,会导致B树节点下溢(比如删除88)
-
如果
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
- 会导致parent 也下溢
- 这时只需要把 parent 当做被删除的节点处理即可
作为一个开发者,有一个学习的氛围跟一个交流圈子特别重要,这是一个我的iOS交流群:413038000,不管你是大牛还是小白都欢迎入驻 ,分享BAT,阿里面试题、面试经验,讨论技术, 大家一起交流学习成长!
推荐阅读
iOS开发——最新 BAT面试题合集(持续更新中)
作者:路飞_Luck
链接:https://www.jianshu.com/p/fe2d66274496
来源:简书