algorithm - 高度为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); }