將空葉頂點添加到AVL樹？

Question

我想知道是否總是可以將空葉子頂點添加到平衡AVL樹上，然後對所有頂點着色，以便有正確構造的紅黑樹？

Answer 1

非常好的問題。我認爲答案是肯定的。以下是不完全的證據，但我認爲他們表明答案可能是真實的。最壞的平衡AVL樹是由以下定義的斐波那契樹：

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

這是，左，右的孩子高達排列，深度n與節點的最小數量的獨特的樹。例如見

在這樣的樹你決定通過以下規則

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 

遞歸着色節點那麼這是一個紅黑樹。參見例如（感謝this applet）：

也有一個音符作爲this page指示相同的底部。