Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?
Five rules for RB-Trees:


  
  Every node is black or red,
  Root is black,
  Every leaf is black,
  If a node is red then both its sons are black,
  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.