Is a tree with all black nodes a red black tree?

Question

It seems the definition on wiki is not precise:

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

Is a tree with all black nodes a red black tree?

UPDATE

With the definition of rbtree not so strict,how do we decide whether to print the children of a black node as red or black?

Answer 1

Yes, a tree with all nodes black can be a red-black tree. The tree has to be a perfect binary tree (all leaves are at the same depth or same level, and in which every parent has two children) and so, it is the only tree whose Black height equals to its tree height.

Answer 2

A red-black tree is simply a binary-tree representation of a 2-3-4 tree. Any red node in a red-black tree corresponds to a piece of its parent node in the analagous 2-3-4 tree. For example:

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

is a representation of the 2-3-4 tree

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

If a red-black tree has only black nodes, that means it represents a 2-3-4 tree with only 2-nodes (single entries), not 3-nodes (such as [3 | 5] in the example) or 4-nodes. Notice this is basically just a plain binary search tree.