平均的时间复杂度在O(logn)到O(n)之间。
因为二叉排序树是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
因此二叉排序树插入时间复杂度最大为O(n)。若是二叉排序树比较平衡，其时间复杂度下降，最小的时间复杂度为O(logn)。
扩展资料
算法实现
性能分析
每个结点的C(i)为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为其平均查找长度(n+1)/2(和顺序查找相同），
最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比。
参考资料来源：百度百科-二叉排序树
温馨提示：答案为网友推荐，仅供参考
相似回答