高度爲h的紅黑樹中最小節點數的公式是多少？

Question

我已經讀過它是log（n + 1）< = h < = 2 * log（n + 1）其中log是以2爲底的。但是，當在幾個已知的最小高度上試用這個時，總是鍛鍊。

到目前爲止我知道：

爲H = 1，節點的最小＃= 2

用於h = 2，最小的節點= 4

用於h = 3，最小節點數= 10。

但是，這些純粹是通過使用紅黑樹的規則進行追蹤來完成的。

當我試圖找到這個或者我的方法/計算完全錯誤時，我應該記下黑色高度嗎？

Answer 1

我們可以遞歸地找到最小節點數。
count_minimum_node將返回達到高度h的節點數量。

int count_node(int h) 
{ 
    int sum = h; 
    for(int i=1; i<=h-2; i++) sum += count_node(i); 
    return sum; 
} 

int count_minimum_node(int h) { return count_node(h+1); }