data-structures - 全黑节点的树是红黑树吗？

Question

维基上的定义似乎并不准确:

http://en.wikipedia.org/wiki/Red-black_tree#Properties

全黑节点的树是红黑树吗？

更新

在 rbtree 的定义不那么严格的情况下，我们如何决定将黑色节点的子节点打印为红色还是黑色？

Answer 1

红黑树只是 2-3-4 tree 的二叉树表示.红黑树中的任何红色节点都对应于类似 2-3-4 树中其父节点的一部分。例如:

           [black 5]
          /         \
      [red 3]     [black 6]
     /       \
[black 2] [black 4]

是 2-3-4 树的表示

    [3 | 5]
   /   |   \
 [2]  [4]  [6]

如果红黑树有 只有黑色节点 ，这意味着它表示只有 2 个节点(单个条目)，而不是 3 个节点(例如 [3 | 5] 在示例中)或 4 个节点的 2-3-4 树。请注意，这基本上只是一个普通的二叉搜索树。