高度为h的红黑树中最小节点数的公式是什么? [英] What is the formula for the minimum number of nodes in a red-black tree of height h?

问题描述

我已阅读到log是(n + 1)< = h< = 2 * log(n + 1)，其中log在基数2中.但是，在一些已知的最小高度上进行尝试时，它并不总是能解决.

I have read that it is log(n+1) <= h <= 2*log(n+1) where log is in base 2. However, when trying this out on a few known minimum heights, it does not always work out.

到目前为止，我知道:

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

For for h = 1, minimum # of nodes = 2.

对于h = 2，最小节点=4.

For h = 2, minimum nodes = 4.

对于h = 3，最小节点=10.

For h = 3, minimum nodes = 10.

但是，这些完全是通过使用红黑树的规则对其进行追踪来完成的.

However these were done purely by tracing it out using the rules for red-black trees.

当我尝试查找黑高时应该记下它吗?还是我的方法/计算完全错误?

Should I be taking note of the black-height when trying to find this or is my approach/calculations just completely wrong?

推荐答案

我们可以递归地找到最小节点数.
count_minimum_node将返回达到高度h的节点数.

We can find the minimal node count recursively.
count_minimum_node will return the number of nodes to achieve height 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); }

这篇关于高度为h的红黑树中最小节点数的公式是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！