说明

N个结点的二叉搜索树，高度是 log2(N) + 1 （取整数，丢弃小数，不是四舍五入）

计算过程

1个根节点的二叉搜索树高度

高度为1，计算过程：

第一步：
log2(1)=0

第二步：
0+1=1

2个结点的二叉搜索树高度

高度为2，计算过程：

第一步：
log2(2)=1

第二步：
1+1=2

3个结点的二叉搜索树高度

高度为2，计算过程：

第一步：
log2(3)=1.58，取整是 1

第二步：
1+1=2

7个结点的二叉搜索树高度

高度为3，计算过程：

第一步：
log2(7) = 2.80，取整是 2

第二步：
2+1=3

结论

N个结点的二叉搜索树，高度是[log2(N)]+1。[]表示取整。

退化成链表

当数据，按照 顺序存放 时，如下：

存放 2、3、5、7、8

会退化成 链表 ，如下：

此时，5个节点，高度是 5

 先说说最好情况，最好情况就是，要查找的那个数刚好是根节点，只需要查找1次。最坏情况，要查找到树的最深节点，查找次数是树的高度。根据上面所讲，树的高度就是[log2(n)]+1。
 我们平常所说的时间复杂度，是指最坏时间复杂度。因为平均时间复杂度和最坏时间复杂度很接近，所以就直接考虑最坏时间复杂度。对这一点有疑问，参考:算法（一）时间复杂度。
 由此，我们可以确定O(n)=[log2(n)]+1

参考

https://blog.csdn.net/zhangjin1120/article/details/121237377