Adding empty leaf vertices to AVL tree?

Question

I was wondering if it is always possible to add empty leaf vertices to a balanced AVL tree and then colour all the vertices so that there is a correctly structured Red-Black tree?

Answer 1

Very good question. I think the answer is yes. The following is not a complete proof, but I think they indicate that the answer might be true. The worst balanced AVL tree is the Fibonacci tree defined by the following:

fib(0) = EmptyLeaf()
fib(1) = Node(fib(0), fib(0))
fib(n) = Node(Fib(n-1), Fib(n-2))

This is, upto permutation of left and right child, the unique tree of depth n with the smallest number of node. See for example

In such a tree you decide to color the node recursively by the following rules

1 - Root is black
2 - for each node n if parent_color is black and n is left child 
    then color = red
    else color = black

Then this is a red-black tree. See for example (thanks to this applet):

Also there is a note as the bottom of this page indicating the same.