说明
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