平衡二叉树的高度

Question

为什么在平衡的二叉树中到达元素的最大时间是log，而在现实中，完全平衡的树有1、3、7、15元素(即比2的倍数少1)。Why is the height of a balanced binary search tree log(n)? (Proof)给出的答案是，假设我们有2^N节点(倍数为2)

但是，如果我们用这些奇数的对数，我们就不会得到一个关于高度的整数！

问题：

它真的是日志(n+1)，但是我们放弃了+1，因为它在巨大的n处可以忽略不计？

Answer 1

这是最低的上限，这意味着它是对一些n。注意，平凡的树的根只有一个高度定义为0，而不是你可能假设的1。例如，具有3个元素的完全平衡树具有高度1，而具有4个元素的树具有高度2，即log(4)。

Answer 2

常数从O(..)表示法中删除，除非它们很重要。在您的示例中，添加+ 1不影响运行时，因此我们将讨论O(log n)而不是O(log n + 1)。

在任何情况下，在平衡二叉树中查找元素都是O(log n)，因为在每一步中，您都要将仍然需要搜索的树的大小减半。随着n的增长，这个大的O符号表示了算法的运行时，它不是用来计算您将要执行的操作数的方法(因为可能需要一些额外的操作等等)。

请注意，您所链接的问题讨论的是2 ^ N叶节点，因此一个具有2 ^ 2 = 4叶节点的平衡二叉树将有7个总节点。N在另一个问题中的含义与这个问题中的n不一样。