algorithm - 是二叉树的高度 log2(n)

Question

假设我们有一个长度为 n=7 的数组，树的高度应该是2 .我不会用行数来计算高度，而是用它们之间的连接来计算高度。
(我认为，因为在堆排序算法中，Siftdown 方法说最后一行的高度为 0 它可以行进，而前一行可以行进的高度为 1，所以树中的 2 行将允许高度1 去旅行。)

所以要得到高度我会计算log2(allNodesInTheBottomRow)这是(n+1)/2 .

是 log2((n+1)/2)正确的？。

在这里，一个例子:

Answer 1

一般来说，二叉树的高度是 O(log n) 是不正确的。 .请注意，在下图中，这两个树都是有效的二叉树:



请注意，右边的树满足右 child 大于根的属性，并且它本身就是二叉树的根。

我认为您的意思是平衡二叉树的高度为 O(log n) .请注意，平衡二叉树的规范定义是高度最小的给定元素集上的二叉树(或者在许多情况下，接近最小 - 一个常数因子)。直观地观察到当每一行完全饱和(即树是完整的或几乎完整的)时会发生这种情况是很简单的。

请注意，当树完全饱和时，第一行有 1元素，第二行有 2元素和 ith行有 2^(i-1)元素。结果，如果有 n元素，即 n = 2^(log n) .这意味着有 O(log n)根据需要行。

如果您正在寻找一个精确的函数来计算高度，而不仅仅是 O(log n)绑定(bind)，你只需四舍五入n最接近 2 的幂然后计算它的日志。例如，如果 n=7 ，2 的最接近幂是 8和 log(8) = 3如所须。您可以减去 1最后取决于您对高度的定义。