构建n个元素的二叉查找树的时间复杂度？
《算法导论》已经证明了构建堆的复杂度为O(n)，所以我猜想构建二叉查找树时是否也能在O(n)中完成。
下面证明过程：
在最好的情况下，每次插入时树都是完全二叉树，这样能保证树的高度最低。
在插入第i个元素时(i>1)，树里已经有了i-1个元素，所以此时树的高度为floor(lg(i-1))。所以n次插入操作的总运行时间为：
O(T(n)) = floor(lg(2-1)) + floor(lg(3-1)) + ... + floor(lg(i-1)) + ... + floor(lg(n-1))
<= lg(1) + lg(2) + ... + lg(i-1) + lg(n-1)
= lg(1*2*...*(i-1)*...*(n-1))
= lg(n!)
<= lg(n^n)
= n*lg(n)
O(n*lg(n))是我能得到的上界，这是一个紧确上界吗？如果是，那它和堆的区别是什么？
希望各位大牛指点！
[解决办法]
顶你啦
[解决办法]
我一直对树这些东西很迷惑。。。
[解决办法]
构建堆块呀,但是堆一般是指固定长度的.
