我們可以繪製一個帶8個黑色節點和12個紅色節點的RB樹嗎？

Question

我在stackoverflow上看到類似的問題here，但沒有回答（清楚地）。

我可以嘗試構建這樣的樹（8個黑色節點和12個紅色節點）沒有任何排尿5 RB-樹（到目前爲止我還沒有能夠做到這一點，雖然）;

1. 一個節點是紅色或黑色
2. 根是黑色
3. 所有的葉子都是黑色
4. 每個紅色節點的兩個孩子都是黑色
5. 每一個簡單路徑從給定節點到任何它的後裔葉子包含相同數量的黑色節點。

但我真的對更優雅的答案感興趣（除了試試看看它是否有效）。

編輯：在葉子被計爲黑色的情況下，顯然這樣的樹不可能被構建。但是如果樹葉不算作黑色節點（8個非葉節點），那麼怎麼辦？

Answer 1

從規則3和4出發，紅色節點不能比黑色節點更多，因爲向樹添加紅色節點必然會增加黑色節點。這是如果你計算一個rb樹的樹葉作爲節點（你的定義）。