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

Question

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?

Answer 1

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.