algorithm - 高度为 h 的节点数是多少？

Question

谁能解释一下方程 n/(2^(h+1)) 用来计算高度为 h 的节点数？

有 3 个节点的树:

 4    h=1
2 3   h=0

对于 h=0，即 2 个节点，等式给出 3/(2^(0+1))=3/2^1=1.5

这是什么意思？这是怎么正确的，方程式不应该给出高度为 0 的最大节点数，即 2，而不是 1.5？

这个等式来自Introduction to algorithms http://mitpress.mit.edu/books/introduction-algorithms

以下是有关方程式的更多信息以及我在何处找到它: https://cs.stackexchange.com/questions/6405/maximum-number-of-nodes-with-height-h https://engineering.purdue.edu/~ee608/handouts/hw4s.pdf #5

Answer 1

你误读了公式。这不仅仅是 n/2^h+1，而是⌈n/2^{h +1}⌉(没有“脚”的方括号是上限函数的表示法，它返回大于其参数的最小整数)。

ceil(3/2^(0+1)) = ceil(3/2) 
                = ceil(1.5)
                = 2