1
$\begingroup$

I have the following claim:

Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.


My attempt:

Disproof.

We will exhibit a counterexample:

enter image description here

This tree satisfies the conditions of being a red-black tree, since:

  1. The root is black.
  2. All leaves are black.
  3. There isn't any red key.
  4. In each path there is the same amount of black keys, in particular, we have three black keys in such paths.

However, we have two keys in level 1, which have one child and it is black.

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \blacksquare$


Is this counterexample correct?

$\endgroup$
2

1 Answer 1

2
$\begingroup$

The disproof is wrong because in your Red-Black tree, all possible leaves need to be represented (see exemples on wikipedia). That means that the real tree represented should be:

this one

It is easy to see that it does not respect the fourth condition of the definition.

In the claim, when it is said that:

a key […] has exactly one child (which isn't null)

it actually means that it has two children, and exactly one of them is null. It is due to the fact that in the representation of a red-black tree, you can either represent ALL null leaves or represent none.

I will let you try to prove or disprove the claim knowing that and edit this answer if necessary.

$\endgroup$
5
  • $\begingroup$ So if I omit the null leaves then it is a disproof, doesn't it? $\endgroup$
    – Chopin
    May 11, 2021 at 19:08
  • $\begingroup$ Still no, because omitting the null leaves is only for the representation. Those leaves are still there when trying to verify the fourth condition. $\endgroup$
    – Nathaniel
    May 11, 2021 at 19:25
  • $\begingroup$ So this is the reason why we cannot pick a key which has exactly one black child, right? $\endgroup$
    – Chopin
    May 11, 2021 at 19:28
  • $\begingroup$ I think you got it ;-) $\endgroup$
    – Nathaniel
    May 11, 2021 at 19:30
  • $\begingroup$ thank you!!! If I will have more questions I will ask you. I will give you the V :) $\endgroup$
    – Chopin
    May 11, 2021 at 19:32

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.