红黑树中的一个节点可以有一个红色和一个黑色的孩子吗?
我有以下树,我在这里只指定了颜色。叶节点被忽略。
B
R B
B B R R
R R R
红黑树中的一个节点可以有一个红色和一个黑色的孩子吗?
我有以下树,我在这里只指定了颜色。叶节点被忽略。
B
R B
B B R R
R R R
是的,一个节点可以有不同颜色的子节点。例如,参见MathWorld关于 RB 树的文章顶部的图表;您可以验证它是否满足 RB 树的所有要求,并且其中一个节点具有不同颜色的子节点。就此而言,您给出的示例是否如此。
这是一篇关于在 Haskell 中学习数据结构的背景下阅读黑树的好文章。
http://scientopia.org/blogs/goodmath/2009/11/30/advanced-haskell-data-structures-red-black-trees/
它给出的 RB 树标准非常清楚。红色节点的子节点必须为黑色,但未指定黑色节点的子节点。重要的一点是,从给定节点到其下方叶子的所有路径必须具有相同数量的黑色节点。查看您的树,从根开始的每条路径都有 1 个黑色节点(如果算上根,则为 2 个),所以没关系。