tnblog
首页
视频
资源
登录

红黑树-添加节点后如何保证红黑规则 08

3675人阅读 2022/6/16 18:12 总访问:1432584 评论:0 收藏:0 手机
分类: Java集合

一、在如下图所示的红黑树的基础上再添加节点15、14

二、添加节点15后会破坏红黑规则,原因:不能出现两个红色节点相连,效果如下图

解决过程如下

解决依据

其父节点为红色,叔叔节点也是红色

1.将“父节点”设为黑色,将“叔叔节点”设为黑色
2.将“祖父节点”设为“红色”。

3.如果祖父节点为根节点,则将根节点再次变成黑色。

结果如下图

四、添加节点14后会破坏红黑规则,原因:不能出现两个红色节点相连,效果如下图

解决过程如下

解决依据

其父节点为红色,叔叔节点是黑色

1.将“父节点15”设为“黑色”
2.  将“祖父节点16”设为“红色”
3.以祖父节点为支点进行旋转(是左旋还是右旋要看左右俩边的大小,即左右俩边层数的比较)

因为14的祖父节点为16,可以看出左边大于右边所以应该右旋,在旋转的时候我们假设看不见该区域的叶子节点,效果如下图


旋转后且补上叶子节点的结果如下图

红黑树小结

红黑树不是高度平衡的,它的平衡是通过"红黑规则"进行实现的规则如下:

  1. 每一个节点或是红色的,或者是黑色的。

  2. 根节点必须是黑色

  3.如果一个节点没有子节点或者父节点,则该节点相应的指t属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的;
  4.不能出现两个红色节点相连的情况

  5.对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点;


添加节点时

评价
没有个性,不需要签名
排名
6
文章
6
粉丝
16
评论
8
{{item.articleTitle}}
{{item.blogName}} : {{item.content}}
ICP备案 :渝ICP备18016597号-1
网站信息:2018-2024TNBLOG.NET
技术交流:群号656732739
联系我们:contact@tnblog.net
公网安备:50010702506256
欢迎加群交流技术