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