红黑树详解三:红黑树的删除"/>
红黑树详解三:红黑树的删除
系列文章目录
文章目录
- 系列文章目录
- 1、删除
- 2、红黑树的平衡
- 2.1、N为根节点
- 2.2、兄弟为黑色节点
- 2.2.1、兄弟子节点全黑
- 2.2.1.1、父亲为红色节点
- 2.2.1.2、父亲为黑色节点
- 2.2.2、兄弟子节点全为黑(全红,一红一黑)
- 2.2.2.1、兄节点与为红色的兄子节点同边
- 2.2.2.1.1、兄在左,兄左子为红
- 2.2.2.1.2、兄在右,兄右子为红
- 2.2.2.2、兄节点与红色的兄子节点异边
- 2.2.2.2.1、兄在左,兄右子为红
- 2.2.2.2.2、兄在右,兄左子为红
- 2.3、兄弟为红色节点
- 2.3.1、兄在左边
- 2.3.2、兄在右边
- 3、总结
- 4、示例
- 4.1、删除50
- 4.2、删除70
- 4.3、删除60
- 4.4、删除10
- 4.5、删除20
1、删除
红黑树的删除和二叉搜索树类似,只不过需要加上颜色,经过变色和旋转满足红黑树的性质。
大致情况为如下几种,候面我们在细分讲解每一种情况。
1、无子节点时,删除节点可能为红色或者黑色。
1.1、如果为红色,直接进行删除即可。
1.2、如果为黑色,直接删除之后需要进行红黑树的平衡操作。
2、有一个子节点时
2.1、删除的节点一定为黑色,子节点一定是红色(联系红黑树性质推测一下),只需要将子节点替换删除节点的位置,变黑即可。
3、有两个子节点时
3.1、与二叉搜索树一样,找到其后继节点放到要删除的节点的位置,然后将后继节点作为删除节点处理。
2、红黑树的平衡
首先看一下概览,如下图所示:
2.1、N为根节点
无需任何操作,直接删除。
2.2、兄弟为黑色节点
2.2.1、兄弟子节点全黑
2.2.1.1、父亲为红色节点
交换P(红色)与S(黑色)的颜色,平衡结束。
2.2.1.2、父亲为黑色节点
将S节点变红,把P当作新的N节点,递归处理,因为此时无论怎么旋转在P的子树都无法达到平衡,所以考虑往上层结构遍历。
2.2.2、兄弟子节点全为黑(全红,一红一黑)
2.2.2.1、兄节点与为红色的兄子节点同边
2.2.2.1.1、兄在左,兄左子为红
对P节点进行右旋操作,P与S换色,SL变黑,平衡结束。
2.2.2.1.2、兄在右,兄右子为红
对P几点进行左旋操作,P与S换色,SR变黑,平衡结束。
2.2.2.2、兄节点与红色的兄子节点异边
2.2.2.2.1、兄在左,兄右子为红
以S进行左旋,交换S和SR的颜色,转换到同左处理。
2.2.2.2.2、兄在右,兄左子为红
以S进行右旋,交换S和SL的颜色,转换到同右处理。
2.3、兄弟为红色节点
2.3.1、兄在左边
对P进行右旋操作,P(黑色)和S(红色)交换颜色,这时N的兄弟节点为黑色(兄在左),转换为兄弟节点为黑色的情况处理。
2.3.2、兄在右边
对P进行左旋操作,P(黑色)和S(红色)交换颜色,这是N的兄弟节点为黑色(兄在右),转换为兄弟节点为黑色的情况处理。
3、总结
删除动作(移除节点)之后,看看这个节点是不是黑色的叶子节点,如果不是,简单处理就可以达到平衡了;
先看N是不是根节点,是的话啥都不用管;不是的话看兄弟什么颜色:
2.1 兄弟是红色:进行旋转涂色,去到兄弟为黑色那里处理
2.2 兄弟是黑色,看看兄弟子节点是不是全部都是黑。
(1)全黑的话,看父什么颜色进行对应处理;
(2)不全黑,看兄在的位置,兄在左的话,看兄的左子是不是红色,进行对应处理;兄在右的话,看兄的右子是不是红色,进行对应处理。
4、示例
现在我们有一颗红黑树:
4.1、删除50
4.2、删除70
4.3、删除60
4.4、删除10
4.5、删除20
更多推荐
红黑树详解三:红黑树的删除
发布评论