高さhの赤黒のツリーにあるノードの最小数の式は何ですか？

Question

私はlog（n + 1）< = h < = 2 * log（n + 1）であることを読んだ。ここでlogは底2である。しかし、これをいくつかの既知の最小高さで試してみると、常にうまくいく。

これまで私が知っている：H = 1の場合

H = 3の場合、ノードの最小＃= 2

時間= 2、最小ノード= 4

、最小ノード= 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); }