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.

Improve this question
$\endgroup$
1
  • $\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$ Commented Apr 3, 2013 at 13:07

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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$ Commented Apr 4, 2013 at 5:04
  • $\begingroup$ @Aryabhata, i added a proof. Sorry I took so long. $\endgroup$ Commented Apr 7, 2013 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$ Commented Apr 20, 2013 at 5:53
  • $\begingroup$ There's a question about this answer. $\endgroup$ Commented Nov 7, 2016 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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.