二叉排序树查找结点的时间复杂度为_二叉排序树查找一个结点的时间复杂度

二叉排序树查找结点的时间复杂度为_二叉排序树查找一个结点的时间复杂度二叉排序树查找时间复杂度假设有一颗二叉排序树, 总结点数是n, 高度是h, 根结点的高度是1,假设也是满二叉树, n与h的关系, 有公式: n = (2^h) – 1也就是: h = log2(n+1)对于高度为2,总结点数是3的二叉排序树(满二叉树),查找成功的平均查找长度为:对

二叉排序树查找时间复杂度   假设有一颗二叉排序树, 总结点数是n, 高度是h, 根结点的高度是1,   假设也是满二叉树, n与h的关系, 有公式: n = (2^h) – 1   也就是: h = log2(n+1)   对于高度为2,总结点数是3的二叉排序树(满二叉树),查找成功的平均查找长度为:   对于高度为3,总结点数是7的二叉排序树(满二叉树),查找成功的平均查找长度为:   对于高度为h,总结点数是n的二叉排序树(满二叉树),查找成功的平均查找长度为:   对于[等式1]里的1*1 + 2*2 + 3*4 + … + h*2^(h-1)   该数列有h项: 1*2^0, 2*2^1, 3*2^2, … , h*2^(h-1)   其总和:   等式两边同乘以2,有:   用[等式3]减去[等式2]有:   其中(2^0 + 2^1 + 2^2 + 2^3 + … + 2^(h-1))是等比数列求和,设:   等式两边同乘以2,有: 2*M = (2^1 + 2^2 + 2^3 + … + 2^h)   两个等式相减,有: M = 2^h – 1   将M代入[等式4]有:   因为 h = log2(n+1),将h代入[等式5],有:   也就是   将上述S代入[等式1],有:   所以,二叉排序树查找成功的平均查找长度为:   其时间复杂度是: O(log2(n))   假设有一颗平衡的二叉排序树,高度h=4,总结点数n=11,不是满二叉树:   根据[公式1],查找成功的平均查找长度为:   ASL = [(n+1)/n] * log2(n+1) – 1 = [(11+1)/11] * log2(11+1) – 1 约等于 2.91   逐个结点计数,平均查找长度为:   ASL = (1*1 + 2*2 + 3*4 + 4*4) / 11 = 33 / 11 = 3   假设有一颗平衡的二叉排序树,高度h=4,总结点数n=15,是满二叉树:   根据[公式1],查找成功的平均查找长度为:   ASL = [(n+1)/n] * log2(n+1) – 1 = [(15+1)/15] * log2(15+1) – 1 = 49/15   逐个结点计数,平均查找长度为:   ASL = (1*1 + 2*2 + 3*4 + 4*8) / 15 = 49/15

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/88328.html

(0)
上一篇 2024年 6月 22日
下一篇 2024年 6月 22日

相关推荐

关注微信