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$
1
  • $\begingroup$ The way to write italics is to use stars. Dollars are for math. $\endgroup$ – Yuval Filmus May 17 at 7:13
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 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 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 at 19:28
  • $\begingroup$ I think you got it ;-) $\endgroup$ – Nathaniel May 11 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 at 19:32

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.