二叉树的高度是否为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). 请注意，在下图中，这两棵树都是有效的二元树。

请注意右边的树满足了右边的子树大于根树的特性 而且它本身也是二元树的根树。

我想你的意思是说，a 均衡 二叉树有高度 O(log n). 请注意，平衡二叉树的规范定义是给定元素集上的二叉树，其中高度是最小的（或在许多情况下，接近最小--一个常数因子）。可以直接做出直观的观察，当每一行完全饱和时，就会发生这种情况（即树是 完整 或 殆尽).

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

如果你正在寻找一个精确的函数来计算高度，而不仅仅是一个简单的 O(log n) 缚，你只需绕 n 满打满算 2 然后计算其对数。例如，如果 n=7，最接近的一次 2 是 8 和 log(8) = 3 根据需要。您可以通过 1 根据你对身高的定义，在最后。