紅黑樹證明

Question

我在我最後的評論表上有一個問題說。證明n> 1，紅黑樹必須至少有1個紅色節點。這對我很有意義，因爲如果n是偶數，則根中的2個子樹的節點數不同，因此必須至少有一個紅色才能保持所有路徑具有相同的黑色高度。那麼還有另外一個問題，就是說黑色高度爲k的樹的最小內部節點是2^k-1。證明這一點的是，如果每個節點都是黑色的，那麼完整的二叉樹（假設虛擬外部葉子被計數）將具有高度k，並且將其插入公式2^h-1給出我們的答案。

我的問題是第一次證明如何與第二次證明一致。具有多於1個節點的樹如何能夠具有至少1個紅色節點，但是最小的內部節點樹只具有黑色節點。任何人都可以啓發我嗎？

Answer 1

第一個證明基於它的插入算法，這就是爲什麼總是有一個紅色節點的原因。但是在第二個證明中，你實際上可以建立一個僅由黑色構成的紅黑樹。使用常用的插入算法，插入時總是會顯示紅色。

我插入此作爲一個答案，以防某人有相同的問題或知道更準確的單詞用作aswer。

閱讀材料：http://www.geeksforgeeks.org/red-black-tree-set-2-insert/