
上图所示,为什么4和5那两个叶子节点没有黑点呢?4和5节点与1,2,3叶子节点有什么不一样?红黑树不是要求所有的叶子节点都得是黑色吗,为什么4,5这两个叶子节点“不是黑色”?如果4,5这两个节点是黑色,那么又会违背“从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点”这一性质,纠结中。
解决方案:10分
你这图少了, 两个红结点在一起,显然是演示insert后的fixup, 1,2,3,4,5都应该代表子树, 黑色代表子树的根是黑色,也就是无法知道黑高是多少
解决方案:10分
