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?

  • $\begingroup$ 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? $\endgroup$ Jan 14 '21 at 17:11
  • $\begingroup$ I'm sorry, I've interchanged them. Should be fixed now. $\endgroup$ Jan 14 '21 at 17:12
  • $\begingroup$ Same problem in your last paragraph? $\endgroup$ Jan 14 '21 at 17:30
  • $\begingroup$ 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? $\endgroup$ Jan 14 '21 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.


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.