16
$\begingroup$

A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition).

I was wondering if we can do something similar with Red-Black trees.

Given an arbitrary uncoloured binary tree (with NULL nodes), is there a "fast" algorithm which can determine if we can colour (and find a colouring) the nodes Red/Black so that they satisfy all the properties of a Red-Black tree (definition as in this question)?

An initial thought was that we can just remove the NULL nodes and try to recursively verify if the resulting tree can be a red-black tree, but that didn't seem to go anywhere.

I did (a brief) web search for papers, but could not seem to find any which seem to deal with this problem.

It is possible that I am missing something simple.

$\endgroup$
  • $\begingroup$ I'm pretty sure a tree can be red-black colored iff for each node, the longest path from it to a NULL node is no more than twice longer than the shortest one. Is that fast enough? $\endgroup$ – Karolis Juodelė Apr 3 '13 at 13:07
12
$\begingroup$

If for each node of a tree, the longest path from it to a leaf node is no more than twice longer than the shortest one, the tree has a red-black coloring.

Here's an algorithm to figure out the color of any node n

if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

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

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

Here n.black-quota is the number of black nodes you expect to see going to a leaf, from node n and n.min-height is the distance to the nearest leaf.

For brevity of notation, let $b(n) = $ n.black-quota, $h(n) = $ n.height and $m(n) = $ n.min-height.

Theorem: Fix a binary tree $T$. If for every node $n \in T$, $h(n) \leq 2m(n)$ and for node $r = \text{root}(T)$, $b(r) \in [\frac{1}{2}h(r), m(r)]$ then $T$ has a red-black coloring with exactly $b(r)$ black nodes on every path from root to leaf.

Proof: Induction over $b(n)$.

Verify that all four trees of height one or two satisfy the theorem with $b(n) = 1$.

By definition of red-black tree, root is black. Let $n$ be a node with a black parent $p$ such that $b(p) \in [\frac{1}{2}h(p), m(p)]$. Then $b(n) = b(p) -1$, $h(n) = h(p)-1$ and $h(n) \geq m(n) \geq m(p)-1$.

Assume the theorem holds for all trees with root $r$, $b(r) < b(q)$.

If $b(n) = m(n)$, then $n$ can be red-black colored by the inductive assumption.

If $b(p) = \frac{1}{2}h(p)$ then $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$. $n$ does not satisfy the inductive assumption and thus must be red. Let $c$ be a child of $n$. $h(c) = h(p)-2$ and $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$. Then $c$ can be red-black colored by the inductive assumption.

Note that, by the same reasoning, if $b(n) \in (\frac{1}{2}h(r), m(r))$, then both $n$ and a child of $n$ satisfy the inductive assumption. Therefore $n$ could have any color.

$\endgroup$
  • $\begingroup$ @Aryabhata, any traversal is fine, as long as the parent is seen before its children. I don't have a formal proof written, but I have an idea of how it would look. I'll try writing something up when I can. $\endgroup$ – Karolis Juodelė Apr 4 '13 at 5:04
  • $\begingroup$ @Aryabhata, i added a proof. Sorry I took so long. $\endgroup$ – Karolis Juodelė Apr 7 '13 at 11:15
  • $\begingroup$ @Aryabhata, the idea is that if $b(p)$ of some node $p$ is withing certain bounds, a child or grandchild $c$ of $p$ can have $b(c)$ within those same bounds. Having $b(n)$ in those bounds may correspond to $n$ being black. Most of the proof is about bounding $h$ and $m$ of a child or grandchild, given $h$ and $m$ of the parent or grandparent. Your tree is certainly colorable. $b(root) = 8$, left child is black and right child is red, the path of length 16 is $brbrbr\dots$, the path of length 8 is $bbbbbbbb$, paths of 9 and 12 can have multiple valid colorings. $\endgroup$ – Karolis Juodelė Apr 20 '13 at 5:53
  • $\begingroup$ There's a question about this answer. $\endgroup$ – David Richerby Nov 7 '16 at 20:30
2
$\begingroup$

I believe Karolis' answer is correct (and a pretty nice characterization of red-black trees, giving an $O(n)$ time algorithm), just wanted to add another possible answer.

One approach is to use dynamic programming.

Given a tree, for each node $n$, you construct two sets: $S_R(n)$ and $S_B(n)$ which contains the possible black-heights for the subtree rooted at $n$. $S_R(n)$ contains the black-heights assuming $n$ is coloured Red, and $S_B(n)$ assuming $n$ is coloured black.

Now given the sets for $n.Left$ and $n.Right$ (i.e direct children of $n$), we can compute the corresponding sets for $n$, by taking appropriate intersections and unions (and incrementing as needed).

I believe this comes out be an $O(n \log n)$ time algorithm.

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