二叉查找（搜索）树的时间复杂度是什么？

二叉查找（搜索）树的时间复杂度是什么？
二叉排序树的性能分析

二叉查找树中查找的运行时间与树T的高度成正比。因为有n个结点的树的高度小则为O(logn)，大则为O(n).；

对于有n个关键字元素的数据项，高度为h的二叉查找树T，空间复杂度为O(n)；其中，查找元素，插入元素，删除元素的时间复杂度均为O(h)；

二叉排序树的查找过程与二分法相似，也是一个逐步缩小查找范围的过程。若查找成功，则走了一条从根结点到待查结点的路径；若失败，则是走了一条根结点到某个叶子结点的路径。因而，查找过程中和关键字的比较次数不超过树的深度。

由于含有n个结点的二叉排序树不唯一，因而有n个结点的二叉排序树的平均查找长度为树的形态有关；

最好的情况：二叉排序树和二叉判定树形态相同；

最坏的情况：二叉排序树为单支树，这时平均查找长度与顺序查找时相同；

就平均性能而言，二叉排序树上的查找与二分查找相差不大，且二叉排序树上的插入和删除结点十分方便，不用大量移动结点。