[Solved]: Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

Problem Detail: 

My best attempt at a specific case of the problem where $n =$ 256:

For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq 2*lg(n+1)$ then $h\leq 16$ for $n =$ 256.

But this doesn't exactly help me deduce whether the last row is all black nodes (thereby implication the parent of these black nodes are red)

Can someone hep me carry this further?

Asked By : Beached Whale

Answered By : 3yakuya

Five rules for RB-Trees:

1. Every node is black or red,
2. Root is black,
3. Every leaf is black,
4. If a node is red then both its sons are black,
5. All paths from a single node to any leaf must contain an equal amount of black nodes.

A common implementation has a NIL leaf set as a parent of root and son (left and right at the same time) of all leaves - in this case the NIL is black, and so it's parents can be black or red (as NIL is the only leaf.) This is the reason for a common misconception that leaves can be any color.

I am almost sure that any RB-Tree containing at least 2 elements (except NIL) will have at least one red node. This is due to an observation of the Insert algorithm. The inserted node is always coloured red at first, but any later modifiaction (if the colouring needs to be repaired) either does not change the colour of the newly added node (so it remains red) or makes at least one other node red.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35393

 Ask a Question

 Download Related Notes/Documents