Search code examples
data-structuresred-black-tree

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

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?

Solution

  • 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.