二叉搜索树的平均查找长度及时间复杂度
发布网友
发布时间：2023-01-03 23:04
共1个回答
热心网友
时间：2023-10-12 12:44
假设有一颗二叉排序树, 总结点数是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
