二进制搜索树的高度，而不构建它

Question

我有几百万连续的数字，例如{3，1，2，...}。按照与它们相同的顺序，将数字插入二进制搜索树中。我需要找到树的高度。

是否有任何方法来确定树的高度，而无需构建整棵树？

Answer 1

如果作为构建的一部分进行平衡，则为log （n）其中n是数字的个数。否则，这是最好的情况，最坏的情况是n。

Answer 2

我不知道任何算法。快速的想法是，它可以沿线 - 第一个元素是根，树高为1，然后检查下两个元素，并根据它们是什么高度h = 2或3，然后检查接下来的4个元素，并根据它们是什么h = h +（1或2或3或4）然后检查接下来的8个元素，并且h = h +（f（元素） - 函数返回这些元素增加树高度的多少）等等...这只是非常简单的例子我会试图追求什么。甚至不知道它是否会比简单地构建树和保存高度信息更快，但是至少如果你准备写这个函数，它会被执行。顺便说一句，这是个有趣的问题