Is a tree with all black nodes a red ebony?

Question

The wiki definition seems to be inaccurate:

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

Is a tree with all black nodes a red ebony?

UPDATE

With the rbtree definition, it’s not as strict as we decide whether to print black black nodes as red or black?

Answer 1

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

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

is a representation of a tree 2-3-4

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

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

Answer 2

Yes , a tree with all the nodes of black can be a red-black tree. The tree should be an ideal binary tree (all leaves are at the same depth or the same level, and each parent has two children), and therefore this is the only tree whose height is equal to the height of its tree.

Answer 3

It is possible to have the right red-black tree with all black nodes. Trivially, RBTree with only one node or with single leaf nodes being direct children of the root will all return nodes.

Answer 4

To answer the second part of the question about whether to print a node as red or black, this information is stored in each node.

In a typical binary search tree, each node contains a value, a left pointer and a right pointer (and possibly a parent pointer). In a red-black tree, each node contains all these things, plus an additional field indicating whether this node is red or black. Various tree operations, such as insertion or deletion, are responsible for permanently storing this color information.

You will never be given an unpainted tree and it will offer colors for nodes (with the possible exception of a homework assignment or exam).

Answer 5

Yes, but the same does not apply to the red-black tree with all the red nodes. Such a tree is invalid. There are restrictions by which nodes must be black. For example, leaf nodes should be black, and children of red node should be black.

Answer 6

Yes, a tree with all black nodes can be a red ebony. It can be proved that such a tree must be completely filled with a tree in order to maintain equal black depth.

You yourself can prove that a tree with all black nodes can be a red ebony, creating a small tree of this kind. For example:

  2,black 1,black 3,black 

This tree has all black knots and satisfies all conditions. Suppose the root has nil as its parent, and both leaf nodes have both their children and nil.Hope this helps.