请问如何计算一个BST建立用时？

iolop

BST的查询插入都是logn，但是从0开始建立一个BST用时是多少呢？（假设这个BST是比较平衡的）



--------------------------------------------谢谢能够解惑的各位：）  ---------------------------

iolop

问题已解决，根据排序算法处理n个结点，必有n！个排列可能，建立判定树，则层数为log(n!)=nlogn

lxyscls

O(nlgn) 应该是个上界吧，或者说是一个不太“紧”的上界

因为假设是完全二叉树，h = lgn + 1也只有在n/2 + 1 个元素被插入后才出现

nlgn，等于假设（n/2 - 1）个元素是最差情况

不过，假设插入第一层 代价 = 1，第二层 代价 = 2，依此类推

那么总代价 =  1 * 1 + 2 * 2 + 3 * 4 + 4 * 8 + 5 * 16 + ... + (lgn + 1) * 2(lgn) (没办法给上标了) =  ... + n(lgn + 1)