Why the number of (NIL) leaf nodes in n-element red-black trees is n+1?
By definition, a red-black tree is a full binary tree in which each node is assigned either red or black and the leaves are labeled as NIL-node while internal nodes are labeled as non-NIL node. In a full binary tree all of the nodes have either 0 or 2 children. Thus, assuming that a full binary tree has
n internal nodes, the number of leaf nodes will be
n + 1. So what you are asking is: if red-black tree has
n non-NIL nodes why does it have
n+1 NIL-nodes ?