构建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))是我能得到的上界，这是一个紧确上界吗？如果是，那它和堆的区别是什么？

希望各位大牛指点！

顶你啦

我一直对树这些东西很迷惑。。。