algorithm - 红黑树问题

Question

红黑树中的一个节点可以有一个红色和一个黑色的孩子吗？

我有以下树，我在这里只指定了颜色。叶节点被忽略。

                   B
           R               B
       B       B       R       R 
     R   R       R

score 1 · Accepted Answer

是的，一个节点可以有不同颜色的子节点。例如，参见MathWorld关于 RB 树的文章顶部的图表；您可以验证它是否满足 RB 树的所有要求，并且其中一个节点具有不同颜色的子节点。就此而言，您给出的示例是否如此。

score 1 · Accepted Answer

这是一篇关于在 Haskell 中学习数据结构的背景下阅读黑树的好文章。

它给出的 RB 树标准非常清楚。红色节点的子节点必须为黑色，但未指定黑色节点的子节点。重要的一点是，从给定节点到其下方叶子的所有路径必须具有相同数量的黑色节点。查看您的树，从根开始的每条路径都有 1 个黑色节点（如果算上根，则为 2 个），所以没关系。

2 回答 2