紅 - 紅 - 黑樹中具有特定黑高度的節點數

Question

我在家庭作業中被要求回答有關「紅 - 紅 - 黑」樹的問題。紅 - 紅 - 黑樹（從某處在互聯網上覆制）的描述是：

「紅 - 紅 - 黑樹是二叉搜索樹滿足以下條件：

1. 每節點是紅色或黑色
2. 每一片葉子（NIL）是黑
3. 如果一個節點是紅色的，它的母公司是紅色的，那麼它的兩個孩子都是黑色
4. 從一個節點到後代葉每一個簡單路徑包含相同數量的黑色節點（樹的黑色高度）「

我被問到，給定一個有n個節點的紅黑樹，黑高k的內節點的最大數目是多少？最小的數字是多少？

我一直試圖考慮它現在兩個多小時，但除了頭痛，我無法得到任何地方。

謝謝！

Answer 1

兩個紅色節點永遠不會連續出現。 穿過任何路徑時，黑色節點的數量應該相等。