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?

  • $\begingroup$ What do you mean by the "last row"? If you mean leafs then you can be sure they are all black (if it is a RB-tree this comes from the definition). $\endgroup$
    – 3yakuya
    Dec 16, 2014 at 19:35
  • $\begingroup$ @Byakuya Are you sure about that? I thought that leaves in RB trees can be any color, not just black. $\endgroup$ Dec 16, 2014 at 20:27
  • $\begingroup$ @templatetypedef You are not wrong. The colour of leaves depends on what you call leaves. If these are actually nodes holding a key, then they can be either red or black. Sometimes the nil-pointers at the bottom are considered leaves (I believe wikipedia does that) that obviously do not hold keys. Those leaves are considered black. $\endgroup$ Dec 16, 2014 at 23:42
  • $\begingroup$ If all nodes are black, then the tree is a perfectly balanced tree, which means it has $2^h-1$ keys for some $h$. The reverse is not true. When the tree has a power-of-two-minus-one nodes, it does not imply all these are black. $\endgroup$ Dec 16, 2014 at 23:46

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.