问题描述
我已阅读到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的红黑树中最小节点数的公式是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！