如何判斷一棵紅黑樹是否可以有X個黑色節點和Y個紅色節點

Question

我下週在算法中進行了一次考試，並給出了準備考試的問題。其中一個問題讓我陷入困境。

「我們可以繪製一個有7個黑色節點和10個紅色節點的紅黑樹嗎？爲什麼？」

聽起來好像它可以很快回答，但我無法理解它。

CRLS給我們帶有n個內部節點的RB樹的最大高度：2 * lg（n + 1）。

我認爲這個問題可以單獨使用這個引理來解決，但我不確定。

任何提示？

Answer 1

既然是考試，我不想給你一個直接的答案，但我認爲你需要考慮的是，支配你如何建立一個紅黑樹的性質：

1. 節點是紅色或黑色。
2. 根部是黑色的。 （此規則在其他定義中有時會被省略，因爲根總是可以從紅色變爲黑色，但不一定反之亦然，因此該規則對分析影響不大）。
3. 所有葉子都是黑色的。
4. 每個紅色節點的兩個孩子都是黑色的。
5. 從給定節點到其任何後代樹葉的每條簡單路徑都包含相同數量的黑色節點。

（偷這些從維基百科頁面：http://en.wikipedia.org/wiki/Red-black_tree）

給你列出的節點的數量，你能滿足所有這些屬性？

Answer 2

答案很簡單。

正如我們所知，紅色節點只能有黑色父母。的節點將是當每個黑節點的兩個孩子都是紅色的，因此，每個黑節點都有紅色父節點。因此，對於'n'黑節點'2n'紅節點是可能的。

想想這樣說：

1. 把第一個節點（這是根）&使黑色
2. 使雙方及其子女紅色
3. 化妝左，右兩個孩子這些紅色節點黑並且對於所有這些黑節點，
4. 遵循與根節點跟隨的相同過程，直到黑節點計數達到給定值（在本例中爲7）

希望這可以幫助您形象化解決方案。

Answer 3

答案關鍵取決於您的RB樹是否在樹葉上使用了黑色虛擬節點，如果是這樣，它們包含在七個黑色節點的計數中。如果沒有，請考慮一個包含七個黑色節點的完整樹

 * 
    /\ 
     * * 
    /\ /\ 
    * * * * 

添加十個紅色節點不會有太多麻煩。