tnblog
首页
视频
资源
登录

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

2850人阅读 2022/6/16 17:24 总访问:1054495 评论:0 收藏:0 手机
分类: Java集合

以如下图几个节点为例,演示保证红黑规则

红黑规则

每一个节点是红色或者黑色,根节点必须是黑色
每个叶节点(Nil)是黑色的;

不能出现两个红色节点相连

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


一、先把这些节点全部变成红色


二、添加第一个节点20,因为20是第一个节点,所以是根节点,因此要把它变成黑色,结果如下图

三、把节点18、23添加进去时因为它们的父级节点是黑色所以不用改变颜色,结果如下图

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

解决依据

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

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

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

结果如下图

五、依次添加剩下的节点16、24、19它们都因为其父节点为黑色,则不需要做任何操作。结果如下图

六、小结


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