假設有一顆二叉排序樹, 總結點數是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