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

user_775627 0
Viewed 15728

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?

red-black-tree data-structures
7 Answers

Here is an example to show that all nodes of a red-black tree are black:

First, insert {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} in increasing order into red-black tree. Then, delete {10, 9, 8} in decreasing order from the red-black tree.

Finally all nodes of this red-black tree are black.

A red-black tree whose nodes are all black is the same as the B- tree (m=4) whose nodes all have only one key.

user_73529460

Yes a tree with all black nodes can be a red black tree. It can be proved that such tree has to be a completely filled tree in order to preserve the equal black depth property.

You can yourself prove that a tree with all black nodes can be a red black tree by buildind a small tree of that kind. For example:

                            2,black
                      1,black      3,black

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

user_8246150
Related