最好的情况。每次插完都是一个完全二叉树，因此当插入第i个元素时，此时数中已经有i-1个元素，输的高度为 log(i-1)。 因此
T >= O(lg(2-1)) + O(lg(3-1)) + ... + O(lg(i-1)) + ... + O(lg(n-1))
=O (lg（1*2*3*···*n-1）
= O(lgn!)
最差的情况。每次查完都在一条线上，构成一个左偏树或右偏树。此时
T <= O(1+2+3+···+n-1)
= O(n^2)
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024