分类:
Java集合
一、在如下图所示的红黑树的基础上再添加节点15、14
二、添加节点15后会破坏红黑规则，原因：不能出现两个红色节点相连，效果如下图
解决过程如下
解决依据
其父节点为红色，叔叔节点也是红色
1．将“父节点”设为黑色，将“叔叔节点”设为黑色
2．将“祖父节点”设为“红色”。
3．如果祖父节点为根节点，则将根节点再次变成黑色。
结果如下图
四、添加节点14后会破坏红黑规则，原因：不能出现两个红色节点相连，效果如下图
解决过程如下
解决依据
其父节点为红色，叔叔节点是黑色
1．将“父节点15”设为“黑色”
2. 将“祖父节点16”设为“红色”
3．以祖父节点为支点进行旋转（是左旋还是右旋要看左右俩边的大小，即左右俩边层数的比较）
因为14的祖父节点为16，可以看出左边大于右边所以应该右旋，在旋转的时候我们假设看不见该区域的叶子节点，效果如下图
旋转后且补上叶子节点的结果如下图
红黑树小结
红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的规则如下:
每一个节点或是红色的，或者是黑色的。
根节点必须是黑色
3．如果一个节点没有子节点或者父节点，则该节点相应的指t属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的;
4.不能出现两个红色节点相连的情况
5．对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点;
添加节点时
评价
排名
4
文章
473
粉丝
3
评论
2
ICP备案 ：渝ICP备18016597号-1
网站信息：2018-2025TNBLOG.NET
技术交流：群号656732739
联系我们：contact@tnblog.net
公网安备：
50010702506256
50010702506256
欢迎加群交流技术