3
$\begingroup$

I have a question regarding the solution provided by Karolis Juodelė. Given in this question; Colour a binary tree to be a red-black tree

Tree Example

Black = black nodes, white = red nodes

So for this tree when I try to manually work out the code, it seems to fail on the node 17. E.G. I have a black quota of 3 so I color the root black. Afterwards I go to the left child (17) and that has the same min height (namely 17 - 21 - 23) -> so I color this black. After this black colour I cannot see how I will end up with a valid tree with 1 black node left.

So if you could provide how to solve it for this example that would be great!

$\endgroup$
1
$\begingroup$

Well, apparently my answer was wrong. The algorithm, at least. The theorem seems to be okay, if a little unreadable.

More in line with that proof, the algorithm should be

if n is root,   # as before
    n.color = black
    n.black-quota = n.height / 2, rounded up.
    # black-quota could start at any value between n.height/2 and n.min-height

else if n.parent is red,   # as before
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    n.black-quota = n.parent.black-quota - 1

    # check that the subtree isn't totally uncolorable
    if n.min-height < n.black-quota then
        error "shortest path was too short"

    # use red only if the subtree is not colorable (as a tree), with given quota
    if n.height <= n.black-quota*2  then
        n.color = black

    else
        n.color = red

What I meant by the last condition is that 17 is red for the sole reason that you can't color it black i.e. $b(17) \notin [\frac{1}{2}h(17), m(17)]$.

Hopefully that works. Thanks for pointing out the error!

$\endgroup$
  • $\begingroup$ Please edit your answer over there so it's correct, too! $\endgroup$ – Raphael Aug 7 '17 at 5:47

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.