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

码拜

9年 ago

上图所示，为什么4和5那两个叶子节点没有黑点呢？4和5节点与1，2，3叶子节点有什么不一样？红黑树不是要求所有的叶子节点都得是黑色吗，为什么4,5这两个叶子节点“不是黑色”？如果4,5这两个节点是黑色，那么又会违背“从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点”这一性质，纠结中。

你这图少了, 两个红结点在一起,显然是演示insert后的fixup, 1,2,3,4,5都应该代表子树, 黑色代表子树的根是黑色,也就是无法知道黑高是多少

就这张图来说，如果这是一棵红黑树，那么P的左右子树(分别以1和2为根)一定不会为空，并且1,2节点还必须是黑色，这样才能保证以P为根结点子树到叶节点黑色节点等于以U为根节点到叶节点黑色节点数。如果1,2为空，就已经违反了红黑树性质，后面再做插入也就没有意义了。