红黑树问题

Question

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

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

                   B
           R               B
       B       B       R       R 
     R   R       R

Answer 1

是的，一个节点可以有不同颜色的子节点。例如，查看R-B树上the MathWorld article的最顶部的图；您可以验证它满足R-B树的所有要求，并且它的一个节点具有不同颜色的子节点。就这一点而言，您给出的例子也是如此。

Answer 2

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

http://scientopia.org/blogs/goodmath/2009/11/30/advanced-haskell-data-structures-red-black-trees/

它给出的R-B树标准非常清楚。红色节点的子节点必须是黑色的，但没有指定黑色节点的子节点。重要的一点是，从给定节点到到它下面的叶子的所有路径必须具有相同数量的黑色节点。看看你的树，从根部往下的每条路径都有一个黑色节点(如果算上根部就是2个)，所以没问题。