1
$\begingroup$

Why the number of (NIL) leaf nodes in n-element red-black trees is n+1?

$\endgroup$
  • $\begingroup$ This is tree for every full binary tree. $\endgroup$ – Yuval Filmus May 12 '18 at 8:56
2
$\begingroup$

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 ?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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