第19讲 动态查找表(6)

插入次序分别为：40,24,12,37,55 40 24 55 37 12,24,37,40,55

1224

37 40

12

55 显然，第i 层结点需比较 i 次。在等概率的前提下， 上述两图的平均查找长度为：

pci 1 n

n

i i

(1 2 2 3 2) / 5 2.2(左图) (1 2 3 4 5) / 5 3(右图)

pci 1

i i