二叉平衡树的平均查找长度_遍历二叉树口诀

二叉平衡树的平均查找长度_遍历二叉树口诀二叉搜索树的平均查找长度二叉搜索树的平均查找长度要怎么算?动力节点小编来告诉大家。假设有一颗二叉排序树, 总结点数是n, 高度是h, 根结点的高度是1,假设也是满二叉树, n与h的关系, 有公式: n = (2^h) –

二叉搜索树的平均查找长度   二叉搜索树的平均查找长度要怎么算?动力节点小编来告诉大家。   假设有一颗二叉排序树, 总结点数是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   以上就是关于“二叉搜索树的平均查找长度”介绍,大家如果想了解更多相关知识,可以一下动力节点的Java在线学习,里面的课程内容从入门到精通,细致全面,很适合没有基础的小伙伴学习,希望对大家能够有所帮助哦。

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

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

(0)
上一篇 2024年 8月 5日 下午8:26
下一篇 2024年 8月 5日 下午8:32

相关推荐

关注微信