红黑树,为什么4和5那两个叶子节点没有黑点

C语言 码拜 9年前 (2015-10-19) 670次浏览
红黑树,为什么4和5那两个叶子节点没有黑点
上图所示,为什么4和5那两个叶子节点没有黑点呢?4和5节点与1,2,3叶子节点有什么不一样?红黑树不是要求所有的叶子节点都得是黑色吗,为什么4,5这两个叶子节点“不是黑色”?如果4,5这两个节点是黑色,那么又会违背“从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点”这一性质,纠结中。
解决方案:10分
你这图少了, 两个红结点在一起,显然是演示insert后的fixup, 1,2,3,4,5都应该代表子树, 黑色代表子树的根是黑色,也就是无法知道黑高是多少
解决方案:10分
红黑树,为什么4和5那两个叶子节点没有黑点就这张图来说,如果这是一棵红黑树,那么P的左右子树(分别以1和2为根)一定不会为空,并且1,2节点还必须是黑色,这样才能保证以P为根结点子树到叶节点黑色节点等于以U为根节点到叶节点黑色节点数。如果1,2为空,就已经违反了红黑树性质,后面再做插入也就没有意义了。

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明红黑树,为什么4和5那两个叶子节点没有黑点
喜欢 (0)
[1034331897@qq.com]
分享 (0)