数据结构：二叉搜索树的高度 作者：马育民 • 2022-07-06 10:23 • 阅读：10134 # 说明 N个结点的二叉搜索树，高度是 `log2(N) + 1` （取整数，丢弃小数，不是四舍五入） [](/upload/0/0/1IX3cKBTAb4J.png) # 计算过程 ### 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 ``` 会退化成 **链表** ，如下： [](/upload/0/0/1IX3ctMvE3FP.png) 此时，5个节点，高度是 5 先说说最好情况，最好情况就是，要查找的那个数刚好是根节点，只需要查找1次。最坏情况，要查找到树的最深节点，查找次数是树的高度。根据上面所讲，树的高度就是[log2(n)]+1。 我们平常所说的时间复杂度，是指最坏时间复杂度。因为平均时间复杂度和最坏时间复杂度很接近，所以就直接考虑最坏时间复杂度。对这一点有疑问，参考:算法（一）时间复杂度。 由此，我们可以确定O(n)=[log2(n)]+1 #### 参考 https://blog.csdn.net/zhangjin1120/article/details/121237377 原文出处：http://malaoshi.top/show_1IX3ctTefutk.html