CODEWITHSUNDEEP
data-structuresred-black-tree
cpuer
cpuer

Reputation: 7793

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?

Upvotes: 16

Views: 18298

Answers (7)

shudeng wu
shudeng wu

Reputation: 141

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.

Upvotes: 3

Suriya Chaudary
Suriya Chaudary

Reputation: 136

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.

Upvotes: 10

Rampal Chaudhary
Rampal Chaudhary

Reputation: 707

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.

Upvotes: 1

Chris Okasaki
Chris Okasaki

Reputation: 4955

To answer the second part of the question, about deciding whether to print a node as red or black, that 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 maybe a parent pointer). In a red-black tree, each node contains all those things plus an extra field indicating whether this node is red or black. The various operations on the tree, such as insert or delete, are then responsible for maintaining this color information in a consistent fashion.

You would never be given an uncolored tree and told to choose colors for the nodes (except perhaps as a homework or exam question).

Upvotes: 2

jtbandes
jtbandes

Reputation: 118741

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.

Upvotes: 10

Alan Turing
Alan Turing

Reputation: 12581

Yes, but the same is not true for a red-black tree with all red nodes. Such a tree is invalid. There are restrictions on which nodes have to be black. For example, leaf nodes have to be black, and the children of a red node both have to be black.

Upvotes: 0

jwismar
jwismar

Reputation: 12268

It is possible to have a proper red-black tree that has all black nodes. Trivially, a RBTree with only one node, or with the only leaf nodes being direct children of the root, will be all back nodes.

Upvotes: 3

Related Questions