二叉搜索树的平均查找长度

二叉搜索树的平均查找长度要怎么算？星辉小编来告诉大家。

假设有一颗二叉排序树, 总结点数是n, 高度是h, 根结点的高度是1,

假设也是满二叉树, n与h的关系, 有公式: n = (2^h) - 1

也就是: h = log2(n+1)

对于高度为2,总结点数是3的二叉排序树(满二叉树),查找成功的平均查找长度为:

ASL = (1*1 + 2*2) / 3

对于高度为3,总结点数是7的二叉排序树(满二叉树),查找成功的平均查找长度为:

ASL = (1*1 + 2*2 + 3*4) / 7

对于高度为h,总结点数是n的二叉排序树(满二叉树),查找成功的平均查找长度为:

ASL = ( 1*1 + 2*2 + 3*4 + ... + h*2^(h-1) ) / n [等式1]

对于[等式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)

其总和:

S = 1*2^0 + 2*2^1 + 3*2^2 + ... + h*2^(h-1) [等式2]

等式两边同乘以2,有:

2*S = 1*2^1 + 2*2^2 + 3*2^3 + ... + (h-1)*2^(h-1) + h*2^h [等式3]

用[等式3]减去[等式2]有:

S = h*2^h - (2^0 + 2^1 + 2^2 + 2^3 + ... + 2(h-1)) [等式4]

其中(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1))是等比数列求和,设:

M = (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]有:

S = h * 2^h - (2^h - 1) = (h-1) * 2^h + 1 [等式5]

因为 h = log2(n+1),将h代入[等式5],有:

S = [ log2(n+1) - 1 ] * 2^[log2(n+1)] + 1
= [ log2(n+1) - 1 ] * (n+1) + 1
= (n+1) * log2(n+1) - n

也就是

S = ( 1*1 + 2*2 + 3*4 + ... + h*2^(h-1) ) = (n+1) * log2(n+1) - n

将上述S代入[等式1],有:

ASL = [(n+1) * log2(n+1) - n] / n
= [(n+1)/n] * log2(n+1) - 1

所以,二叉排序树查找成功的平均查找长度为:

ASL = [(n+1)/n] * log2(n+1) - 1 [公式1]

其时间复杂度是: O(log2(n))

假设有一颗平衡的二叉排序树,高度h=4,总结点数n=11,不是满二叉树:

          36
      /        \
     24        52
    / \       /  \
  10   30    41  90
  / \       /    /
 8  12     38   61

根据[公式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,是满二叉树:

           36
      /           \
     24            52
    /  \         /    \
  10    30      41     90
 / \    / \    /  \    / \
8  12  28  31 38  42  61  91

根据[公式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星辉在线学习，里面的课程内容从入门到精通，细致全面，很适合没有基础的小伙伴学习，希望对大家能够有所帮助哦。