# Every AVL tree can be colored to be a red-black tree

I want to prove any AVL tree can be turnt into a red-black tree by coloring nodes appropriately. Let $$h$$ be the height of a subtree of an AVL tree. It is given that such a coloring is constrained by these cases:

1. $$h$$ even $$\implies$$ black height $$=$$ $$\frac{h}{2} + 1$$, root node black
2. $$h$$ odd $$\implies$$ black height $$=$$ $$\frac{h+1}{2}$$, root node red

After that the root node is colored black.

I'm trying to prove this inductively. Let's start with the base case $$h=1$$. Then there is only one node (the root node) and it gets colored black (using case 2) which yields a valid red-black tree.

Now suppose the statement is true for some $$h \geq 1$$. Then for any node $$u$$ in the AVL tree, the height difference between their children is less than $$1$$. That is, for an AVL tree of height $$h+1$$ either both subtrees of the root node have height $$h$$ or one has height $$h-1$$.

By the induction hypothesis we know how to color the subtree of height $$h$$, depending on the parity of $$h$$. I'm unsure if I should use strong induction instead because it is not given in the hypothesis how to color a subtree of height $$h-1$$.

If we would know how to color both subtrees, then consider the following cases:

1. $$h+1$$ is even
• one subtree has height $$h$$, the other height $$h-1$$
• both subtrees have height $$h$$
2. $$h+1$$ is odd
• one subtree has height $$h$$, the other height $$h-1$$
• both subtrees have height $$h$$

For case 1.1 we would get \begin{align*} \quad & h+1 &\text{even} \\ \implies \quad & h &\text{odd} \\ \implies \quad & \text{black height} = \frac{h+1}{2} \\ \implies \quad & h-1 &\text{even} \\ \implies \quad & \text{black height} = \frac{(h-1)}{2} + 1 = \frac{h+1}{2} \end{align*}

So their black heights differ by $$1$$. How would I take that into consideration?

• I do not understand your initial assumption. If $h$ is even then the black height equals $\frac {h+1}2$. But that's not an integer? – Hendrik Jan Jan 14 at 17:11
• I'm sorry, I've interchanged them. Should be fixed now. – millionmilesaway Jan 14 at 17:12
• Same problem in your last paragraph? – Hendrik Jan Jan 14 at 17:30
• So, now after correction in the last paragraph both cases we have the same outcome. Do you still have a problem? Or does it move to the other case? – Hendrik Jan Jan 14 at 22:11

Here is a computer verification of your method.

The height discrepancies occur when we are making a red root, in which case the shorter child with the reduced black height would also have a red root. Since there can't be two consecutive red nodes, we need to turn the shorter child black, which increases its black height to match the taller child.