Wikipedia's Red-black tree states the last property of a Red-black tree:
Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: the number of black nodes from the root to a node is the node's black depth; the uniform number of black nodes in all paths from root to the leaves is called the black-height of the red–black tree
I'm not understanding this property. So, looking at this tree from the above Wikipedia article:
What is this field's value for the 8 tree, i.e. Root (13) -> 8?
How about for 15, i.e. Root (13) -> 7 -> 15?
When providing an answer, please also explain the why of that number.
Best Answer
From the definitions:
Let's use $d(n)$ for the black depth of a node $n$. So $d(8) = 1$, for example, because one node is black along the path $13 \to 8$ (namely node $13$). Similarly $d(15)=2$ because along the path $13 \to 17 \to 15$, two nodes ($13$ and $15$) are black.
The black-height of the tree here is $3$ because $d(n)=3$ whenever $n$ is NIL.