Binary tree To Red-Black tree

Question

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

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!

Answer 1

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!