二叉排序树查找时间复杂度 假设有一颗二叉排序树, 总结点数是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
