2
$\begingroup$

Let's define thin AVL tree as AVL tree $t'$ such that contains minimal possible number of nodes among all AVL tree $t$ such that $height(t)=height(t')$.

I am trying to prove that every thin AVL tree may be colored to be red-black tree. I would like to use induction. I tried to do induction by height - but as you could see Every AVL tree may be red black tree I didn't managed to (I have very similar problem).

Could you give me a hint ?

I can see following thing:
thin avl tree of height $h$ has exactly one vertex on height $h$ - contrary avl tree wouldn't be thin. Moreover this node must be red (property of black height).
Example:
enter image description here

$\endgroup$
  • 1
    $\begingroup$ I suggest you spend more time on it. Draw some thin AVL trees and see how to color them. Try to spot a pattern. Then try a proof by induction; you might have to strengthen the induction hypothesis. $\endgroup$ – Yuval Filmus Jan 3 '16 at 0:22
  • $\begingroup$ strenghen ? hmm, it is not truth for arbitrary tree $\endgroup$ – user40545 Jan 3 '16 at 13:22
  • 1
    $\begingroup$ Well, that's not the correct way to strengthen the induction hypothesis, then. $\endgroup$ – Yuval Filmus Jan 3 '16 at 13:35
4
$\begingroup$

Just a remark.

Your "thin" trees are sometimes know as Fibonacci trees. A Fibonacci tree $T_h$ of height $h$ is recursively defined as root with two subtrees $T_{h-1}$ and $T_{h-2}$. Hence the name.

As the number of black nodes along each path from root to leaf must be equal, this means that the subtrees $T_{h-1}$ and $T_{h-2}$ must have the same black height in $T_h$, although they differ in height.

$\endgroup$

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.