0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The definition you quote concerns "Every path from a given node to any of its descendant NIL nodes", but you ask about "this field's value" for paths 13 -> 8 and 13 -> 7 -> 15 that are not of such a form. I'm not sure what you are asking. Probably you meant 17 in place of 7. $\endgroup$ – hardmath Mar 6 '16 at 16:51
1
$\begingroup$

From the definitions:

The number of black nodes from the root to a node is the node's black depth.

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 uniform number of black nodes in all paths from root to the leaves is called the black-height of the red–black tree.

The black-height of the tree here is $3$ because $d(n)=3$ whenever $n$ is NIL.

$\endgroup$
0
$\begingroup$

In red-black tree you know: that black-depth is permanent for every two child in the tree. For example:

8:

We have two children's $1$ and $11$ and for them we know that black-depth($1$) = black-depth($11$)=$2$.

$\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.