分类:
Java集合
以如下图几个节点为例，演示保证红黑规则
红黑规则
每一个节点是红色或者黑色，根节点必须是黑色
每个叶节点(Nil)是黑色的;
不能出现两个红色节点相连
对每一个节点，到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点;
一、先把这些节点全部变成红色
二、添加第一个节点20，因为20是第一个节点，所以是根节点，因此要把它变成黑色，结果如下图
三、把节点18、23添加进去时因为它们的父级节点是黑色所以不用改变颜色，结果如下图
四、添加节点22后会破坏红黑规则，原因：不能出现两个红色节点相连，效果如下图
解决依据
其父节点为红色，叔叔节点也是红色
1．将“父节点23”设为黑色，将“叔叔节点18”设为黑色
2．将“祖父节点20”设为“红色”。
3．如果祖父节点为根节点，则将根节点再次变成黑色。
结果如下图
五、依次添加剩下的节点16、24、19它们都因为其父节点为黑色，则不需要做任何操作。结果如下图
六、小结
评价
排名
4
文章
473
粉丝
3
评论
2
ICP备案 ：渝ICP备18016597号-1
网站信息：2018-2025TNBLOG.NET
技术交流：群号656732739
联系我们：contact@tnblog.net
公网安备：
50010702506256
50010702506256
欢迎加群交流技术