Problem Detail: 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.
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.
Asked By : user40545
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/51357 Ask a Question Download Related Notes/Documents
