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:
- $h$ odd $implies$ black height $=$ $frac{h}{2} + 1$, root node black
- $h$ even $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:
- $h+1$ is even
- one subtree has height $h$, the other height $h-1$
- both subtrees have height $h$
- $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}{2} + 1 \
implies quad & h-1 &text{even} \
implies quad & text{black height} = frac{(h-1)+1}{2} = frac{h}{2}
end{align*}
$$
So their black heights differ by $1$. How would I take that into consideration?
