Pergunta

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof.

Induction for height.
Let's assume that it is truth for each AVL tree of height at most $h$.
Let's consider AVL tree $T$ of height $h+1$. Now, let's consider two subtree of $T$ - $L$ and $R$. We know that $height(R)\le h$ and $height(L)\le h$. Hence using induction hypothesis we conclude that $L$ and $R$ may be colored such that $L$ and $R$ will be red black tree. Then we may paint root - of course black color. Now $T$ is AVL and black tree.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top