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.

  • 1
    $\begingroup$ Do you have a specific question? We don't like "look at my proof!" questions. $\endgroup$ – Raphael Jan 2 '16 at 10:17

Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule:

Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

Not every AVL tree satisfies this condition, for example the Wikipedia example doesn't.

  • $\begingroup$ Look, at wikipedia example once again. What about following coluouring i.imgur.com/7gWbjl1.png ? $\endgroup$ – user40545 Jan 2 '16 at 11:55
  • 1
    $\begingroup$ @user40545 That's not the coloring that your proof produces. $\endgroup$ – Yuval Filmus Jan 2 '16 at 11:57
  • $\begingroup$ Ah, ok I thought that You claied that there is no possiblity to color this graph. $\endgroup$ – user40545 Jan 2 '16 at 16:30

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.