高度为h的红黑树的最小节点数计算公式是什么？

Question

我读到它是 log(n+1) <= h <= 2*log(n+1) ，其中 log 以 2 为底。但是，在一些已知的最小高度上进行尝试时，它并不总是奏效。

到目前为止我知道：

对于 h = 1，最小节点数 = 2。

对于 h = 2，最小节点数 = 4。

对于 h = 3，最小节点数 = 10。

然而，这些完全是通过使用红黑树的规则进行追踪来完成的。

我在寻找这个时应该注意黑色高度还是我的 approach/calculations 完全错误？

Answer 1

我们可以递归地找到最小节点数。
count_minimum_node将return的节点数达到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); }