也许是个愚蠢的问题。在 n 是节点总数的平衡二叉树中，我理解为什么高度等于 log(n)。我不明白的是人们将高度称为 O(log(n)) 时的意思。我只看到 Big O 在算法的上下文中使用，如果算法在 O(n) 中运行并且如果输入加倍，则运行时间加倍。但高度不是算法。这如何适用于树的高度？高度为 O(log(n)) 是什么意思？
最佳答案
这是因为 n 个节点的完整二叉树不具有 log(n) 的高度。
考虑一棵高度为 k 的完全二叉树。这样的树有 2k 个叶节点。它总共有多少个节点？如果你查看每一层，你会发现它有 1 + 2 + 4 + 8 + ... + 2k 个节点，或者 20 + 21 + 22 + 23 + ... 2k.
经过一些数学运算后，您会发现这个级数等于2k+1 - 1。
那么，如果你的树有 n 个节点，它的高度是多少？如果你求解关于 k 的方程 n = 2k+1 - 1，你将得到 k = log 2(n+1) - 1。
这个表达式比log2(n)稍微差一点，肯定不是同一个数。然而，根据大 O 符号的特性， log2(n+1) - 1 = O(log(n))。
在您正在阅读的源代码中，强调高度增长的速度与log(n) 一样快。它们属于同一个复杂度类别。此信息在设计算法时非常有用，因为您知道将输入加倍只会使树高增加一个常数。此属性赋予树结构巨大的力量。因此，即使树的确切高度的表达式更复杂(如果您的二叉树不完整，它看起来仍然会更复杂)，它相对于 n 具有对数复杂度。
关于algorithm - 平衡二叉树高度的大O，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66631088/