所有黑色节点的树是红黑树吗？

Question

看来维基上的定义并不准确:

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

所有黑色节点的树是红黑树吗？

UPDATE

由于rbtree的定义不那么严格,我们如何决定是将黑色节点的子节点打印为红色还是黑色？

Answer 1

是的,所有节点都是黑色的树可以是红黑树.树必须是完美的二叉树(所有叶子都在相同的深度或相同的水平,并且每个父亲都有两个孩子),因此,它是唯一一棵黑色高度 等于树高的树.

Answer 2

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

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

是2-3-4树的代表

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

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